2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
1回答
引理1:如果H是图G的子图，则dist_G(u，v)<= dist_H(u，v)。证明
dist_H(x，y) <= dist_H(a，b
浏览 3提问于2016-07-08得票数 0
3回答
组合优化
、、、
假设我们有一个连通的无向图: G=(V，E)。我们有一个定义在连通集上的任意函数F，即给定一个任意连通集CS，F(CS)将给我们一个实数值。如果两个连通集的并不是连通集，则称它们是不相交的。
图中红色、黑色、绿色点集都是有效的<e
浏览 1提问于2010-10-13得票数 7
1回答
可能重复：
你什么时候会用Kruskal算法而不是Prim算法找到最小生成树？哪种输入图和节点更适合每种类型？在什么情况下，当涉及到空间和时间时，使用其中之一更有效？
浏览 3提问于2012-12-11得票数 2
1回答
连通无向无圈图与树
、、、
当我在麻省理工学院的“算法概论”中学习图论的时候，我被介绍了一些关于图和树的定义。在麻省理工学院对算法第三版书的介绍中，附录树一章向我展示了定理B.2，“自由树的特性”
从理论上讲，如果有一个无向无圈图，它满足了一个条件，那就可以作为例子了吗？
如果有一个例子满足这个条件，你能给我看一下吗？
浏览 4提问于2015-11-17得票数 4
回答已采纳
1回答
给出了一个有向加权图，它是强连通的。我需要从这个图中找到一个强连通子图，使得最大和最小权边之间的差是最小。更清楚地说，我需要去除边，这样在去除它们之后，图仍然是强连通的，而最大边和最小权边之间的差是最小。第一行是图的N个节点数和M个边。下一条M线表示这个图的边。3 6
2 1 27
浏览 9提问于2021-07-24得票数 2
回答已采纳
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
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
我知道对于一个有n个顶点的无向图，它连通的最小边数是n- 1。然而，如果一个图有n个顶点和n-1条边，它总是连通的吗？
浏览 2提问于2015-12-11得票数 1
2回答
寻找不含负圈的强连通子图
、、、、
是否有解决以下决策问题的算法：G的强连通生成子图是G的一个强连通子图，它与G具有相同的顶点。您可以在此中查找强连通生成子图的定义。本文给出了最小强连通子图问题的一个近似解。解决这个问题的一种天真的方法是使用福特-贝尔曼或弗洛伊德-沃肖尔算法找到图的负圈，从
浏览 5提问于2019-12-31得票数 5
1回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助
浏览 36提问于2019-06-12得票数 1
回答已采纳
2回答
问题要构建这个连通图，我首先想到的是计算完整的图，但是(205000*(205000-1)/2约有190亿个边，我无法处理。选项
然后我想到了Delaunay三角剖分:如果我构建这个"Delauney图“，它包含一个子图，它是
浏览 5提问于2022-11-22得票数 3
回答已采纳
我希望能够将我的图分成子组件，这样删除任何单个节点都不会创建更多的子组件(不包括单个节点)。作为示例，请参见下面的两个图像。
浏览 13提问于2019-03-27得票数 0
回答已采纳
1回答
如果我有一个有一个节点而没有边的图。连通分量的数目= 1，对吗？如果我有一个有两个节点和一个边的图。连通分量的数目= 1，对吗？
浏览 2提问于2014-11-18得票数 1
回答已采纳
1回答
考虑一个连通加权有向图G = (V, E, w)。路径P的胖度是P中任何边的最大权重。
如何找到图的最小可能的胖度？Dijkstra的算法能用来找出最小的脂肪吗？
浏览 0提问于2017-10-04得票数 1
回答已采纳
2回答
给定一个连通的无向图，寻找具有最小最大度的生成树的问题已经得到了很好的研究(M.F¨urer，B.Rahvachari，“近似最小度生成树到最优度的1以内”，ACM-SIAM离散算法研讨会(SODA)，我对以下问题感兴趣-给定一个连通无向图G= (V1，V2，E)，找出所有内部节点(非叶子节点)上具有最大最小度的生成树。有人能告诉我这个问题是否被研究过吗?它是NP难的吗?此外，为了方便起见，可以将该图视为二部图。
浏览 1提问于2013-03-18得票数 3
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
