2回答
给定一个连通的无向图，寻找具有最小最大度的生成树的问题已经得到了很好的研究(M.F¨urer，B.Rahvachari，“近似最小度生成树到最优度的1以内”，ACM-SIAM离散算法研讨会(SODA)，这个问题是NP难的，文献中已经描述了一种近似算法。
我对以下问题感兴趣-给定一个连通无向图G= (V1，V2，E)，找出所有内部节点(非叶子节点)上具有最大最小度的生成树。或者有一个多项式时间的算法来解决它吗？此外，为了方便起见，可以将
浏览 1提问于2013-03-18得票数 3
1回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助
浏览 36提问于2019-06-12得票数 1
回答已采纳
1回答
Prim的算法在Python2.7中实现了选择优先级队列的可能性。可以在二项式堆和二进制堆之间进行选择。数据结构为图形(.txt文件)。如果图不是连通的，则Prim的算法必须在图的最大连通分支上进行。一切都设置得很好，连接组件工作得很好(用很少的图测试)，但当二项式堆是优先级队列时，MST结果与二进制堆结果(非连接图)不同。当使用连通图时，结果是相同的。Prim的算法有没有可能在同
浏览 0提问于2015-08-27得票数 0
1回答
我要解决的场景是一个最大化问题，在这个问题中，连通的无向图中的每个顶点都有一个值。然而，每个边和顶点也有一个成本。给定一个起始顶点和一个成本预算，是否有一种建议的算法或方法来找到最大顶点值(包括起始顶点)的连通子图？
浏览 1提问于2017-09-09得票数 0
回答已采纳
1回答
考虑一个连通加权有向图G = (V, E, w)。路径P的胖度是P中任何边的最大权重。
如何找到图的最小可能的胖度？Dijkstra的算法能用来找出最小的脂肪吗？
浏览 0提问于2017-10-04得票数 1
回答已采纳
1回答
我想使用最大流算法(Edmond Karp / Ford-Fulkerson算法)找出无向图的边连通性(即，要移除以断开图的最小边数)， } }}
但我希望使用|V| flow网络(运行最大流算法仅运行
浏览 4提问于2013-05-05得票数 6
回答已采纳
2回答
寻找不含负圈的强连通子图
、、、、
是否有解决以下决策问题的算法：G的强连通生成子图是G的一个强连通子图，它与G具有相同的顶点。您可以在此中查找强连通生成子图的定义。本文给出了最小强连通子图问题的一个近似解。解决这个问题的一种天真的方法是使用福特-贝尔曼或弗洛伊德-沃肖尔算法找到图<
浏览 5提问于2019-12-31得票数 5
1回答
最小权路径
、、、
给定一个连通的无向加权图，求出从s到t的路径中边的最大权重，其中路径中的边的最大权重最小。
这似乎是一个弗洛伊德-沃尔算法问题。有比O(V^3)更快的方法吗？
浏览 0提问于2015-10-03得票数 1
回答已采纳
3回答
组合优化
、、、
假设我们有一个连通的无向图: G=(V，E)。我们有一个定义在连通集上的任意函数F，即给定一个任意连通集CS，F(CS)将给我们一个实数值。现在的问题是:我们想从G中找到一组不相交的连通集，这样：(1)每个连通集至少有K个点。(K
浏览 1提问于2010-10-13得票数 7
1回答
把图划分成组的算法
、、、、
我正在寻找一种算法，将一个图划分成最大大小为n的顶点组(如果每个顶点都是自己的图，则每个顶点是连通的)，同时保持最小的组数。我需要这个算法将delaunay三角剖分划分成每个区域的顶点数相等的区域。
浏览 2提问于2013-11-27得票数 3
回答已采纳
考虑以下策略，将具有负边权的图转换为没有负边权的图。设图中的最大幅值负边权为-k。然后，对于具有权重w的图中的每个边，将权重更新为w+k+1。为了解决原图中的最短路径问题，我们可以在修改后的图上运行Dijkstra算法，减去增加的权重，得到原图。这一说法对所有图都是正确的。
对于连通无圈图，这一说法是正确的。对于具有圈的连通图，这一说法一般不成立。
浏览 0提问于2017-02-20得票数 0
回答已采纳
2回答
来自
上面的图是连通的，当所有有向边都被无向edges.But替换时，B到D或D到B之间没有路径，这违反了弱类型的property..Am I，对吗？
浏览 2提问于2013-09-06得票数 4
回答已采纳
我正在寻找算法(链接/名称就足够了)将图划分为k(在我的例子中是2-4)非空块，这样总边权之和(每个块的和权)是最大的。我知道这个问题可能在NP类中，但是我有少量的顶点(8-15)，图是稠密且连通的。
浏览 0提问于2014-10-23得票数 0
回答已采纳
2回答
在无向图中，我想要找到最大连通分量。我阅读了networkX的API文档，找到了这个函数nx.connected_component_subgraphs()。但是我不知道如何使用它，因为它的返回值是一个生成器，我不能导出最大连通组件的子图。
它和一个一样。但是图是有向的。我想找出有向图的最大弱连通分量。如何利用networkX中的内建函数求出无向图中最大连通分量和有向图中最大弱
浏览 8提问于2014-10-07得票数 8
回答已采纳
是的，正如标题所说，我在neo4j中存储了一个社交图，大约一百万个节点和两千万个关系，我想获得最大的连接子图，这样我就可以继续我的工作了。现在我写了一个程序来做这件事，我使用DFS()来找到它所能找到的最大的连接subgraph.If，我删除那些没有连接的节点。但这需要3个hours.....So，我的问题是:有没有更有效的算法来寻找最大的连通子图？任何建议都会很有帮助~谢谢！
浏览 18提问于2013-04-02得票数 2
1回答
在图中查找不需要的顶点
、、、
对于给定的连通图，G是否有一个已知的算法:由顶点列表V定义的G和边E分解列表，这些顶点可以被删除，而图仍然是连通的。
算法复杂性是一个问题。
浏览 2提问于2014-11-03得票数 0
回答已采纳
云服务器
ICP备案
对象存储
云直播
腾讯会议
腾讯云开发者
