2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
2回答
寻找不含负圈的强连通子图
、、、、
是否有解决以下决策问题的算法：G的强连通生成子图是G的一个强连通子图，它与G具有相同的顶点。您可以在此中查找强连通生成子图的定义。本文给出了最小强连通子图问题的一个近似解。解决这个问题的一种天真的方法是使用福特-贝尔曼或弗洛伊德-沃肖尔算法</em
浏览 5提问于2019-12-31得票数 5
2回答
给定一个连通的无向图，寻找具有最小最大度的生成树的问题已经得到了很好的研究(M.F¨urer，B.Rahvachari，“近似最小度生成树到最优度的1以内”，ACM-SIAM离散算法研讨会(SODA)，这个问题是NP难的，文献中已经描述了一种近似算法。
我对以下问题感兴趣-给定一个连通无向图G= (V1，V2，E)，找出所有内部节点(非叶子节点)上具有最大最小度的生成树。或者有一个多项式时间的算法来解决它吗？此外，为
浏览 1提问于2013-03-18得票数 3
1回答
将无向连通图分解为两个分量
、、、、
是否有任何算法将连通的无向图分解为，确切地说是通过删除最小顶点数()，将连接的组件分解为2连通组件。示例1:边列表1-2，2-3，3-4，这里我们可以删除顶点2或顶点数3，将图分解成两个连通的组件。示例2:边列表1-2，2-5，2-3，3-4，这里我们不能删除顶点2，因为它将图分解成3个连通的组件(我们不想要)，但是我们可以删除顶点号3，将图分解成两个连通的组件。
浏览 5提问于2019-12-13得票数 1
2回答
问题要构建这个连通图，我首先想到的是计算完整的图，但是(205000*(205000-1)/2约有190亿个边，我无法处理。选项
然后我想到了Delaunay三角剖分:如果我构建这个"Delauney图“，它包含一个子
浏览 5提问于2022-11-22得票数 3
回答已采纳
1回答
考虑一个连通加权有向图G = (V, E, w)。路径P的胖度是P中任何边的最大权重。
如何找到图的最小可能的胖度？Dijkstra的算法能用来找出最小的脂肪吗？
浏览 0提问于2017-10-04得票数 1
回答已采纳
2回答
有没有一种算法，当给定一个图时，计算该图的顶点连通性(为了将该图分成两个连接的图而要删除的最小顶点数)。(请注意，该图可能已断开连接)。谢谢!
浏览 1提问于2013-04-14得票数 2
回答已采纳
3回答
组合优化
、、、
假设我们有一个连通的无向图: G=(V，E)。我们有一个定义在连通集上的任意函数F，即给定一个任意连通集CS，F(CS)将给我们一个实数值。如果两个连通集的并不是连通集，则称它们是不相交的。
图中红色、黑色、绿色点集都是有效的<e
浏览 1提问于2010-10-13得票数 7
Prim和Kruskal的算法用于寻找连通和无向图的最小生成树。为什么不能在有向图上使用它们呢？
浏览 1提问于2014-03-26得票数 23
回答已采纳
1回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助
浏览 36提问于2019-06-12得票数 1
回答已采纳
1回答
我知道这与max-flow算法有关，但我很乐意给你一个提示：我认为生成树是一种完美的匹配。但如何使其最小化，使其包含e和适当数量的其他边？
浏览 4提问于2013-07-08得票数 2
回答已采纳
2回答
以下是一个完整的问题：
首先，运行强连接组件算法。现在我们有了强连通的成分。这将使每个SCC内的边缘最小化。我的两个问题是：(1
浏览 1提问于2013-02-19得票数 3
1回答
如果删除边缘，更新最小生成树
、、、、
我对以下问题有困难：从G中删除一个边以生成一个新的图，这样新的图仍然是连通的。给出了一种使用T在O(|E|)时间内为新图寻找最小生成树的算法。
浏览 1提问于2015-06-17得票数 1
回答已采纳
1回答
这是一个连通的无向加权图。我如何想出一种算法，以n = |V|时间复杂度计算图的最小均方误差。
我在考虑Kruskal的算法，但它不能满足时间复杂度的要求。
浏览 0提问于2020-04-06得票数 1
回答已采纳
1回答
边缘连通性是将图划分为2个或更多个组件时要删除的最小边数。到目前为止，我已经找到了一种边界连通性的算法，而不考虑顶点：。如果在图G中切割任何边/边，则生成两个分量G1 & G2。
这里( v1∈G1和v2∈G2 ) OR ( v2∈G1和v1∈G2 )
浏览 1提问于2015-05-09得票数 1
回答已采纳
1回答
把图划分成组的算法
、、、、
我正在寻找一种算法，将一个图划分成最大大小为n的顶点组(如果每个顶点都是自己的图，则每个顶点是连通的)，同时保持最小的组数。我需要这个算法将delaunay三角剖分划分成每个区域的顶点数相等的区域。
浏览 2提问于2013-11-27得票数 3
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
实时音视频活动推荐
腾讯云开发者
