2回答
寻找不含负圈的强连通子图
、、、、
是否有解决以下决策问题的算法：G的强连通生成子图是G的一个强连通子图，它与G具有相同的顶点。您可以在此中查找强连通生成子图的定义。本文给出了最小强连通子图问题的一个近似解。解决这个问题
浏览 5提问于2019-12-31得票数 5
1回答
我要解决的场景是一个最大化问题，在这个问题中，连通的无向图中的每个顶点都有一个值。然而，每个边和顶点也有一个成本。给定一个起始顶点和一个成本预算，是否有一种建议的算法或方法来找到最大顶点值(包括起始顶点)的连通子图？
浏览 1提问于2017-09-09得票数 0
回答已采纳
1回答
有效地找到所有连通导出子图
、、、、
是否有一个有效的(*)算法来寻找一个连通的无向顶点标号图的所有连通(诱导)子图？(*)我理解，在一般情况下，任何这样的算法都可能有O( 2^n )的复杂度，因为对于一个团(Kn)，有2^n个连通子图。但是，我通常处理的图的连通子图要少得多，所以我正在寻找一种方法来生成它们，而不必考虑所有2^n个子图并丢弃那些不连通</e
浏览 3提问于2013-03-27得票数 12
回答已采纳
是的，正如标题所说，我在neo4j中存储了一个社交图，大约一百万个节点和两千万个关系，我想获得最大的连接子图，这样我就可以继续我的工作了。现在我写了一个程序来做这件事，我使用DFS()来找到它所能找到的最大的连接subgraph.If，我删除那些没有连接的节点。但这需要3个hours.....So，我的问题是:有没有更有效的算法来寻找最大的连通子图？任何建议都会很有帮助~谢谢！
浏览 18提问于2013-04-02得票数 2
1回答
在图形工具中，有没有一种只绘制最大连通子图的方法？我现在有一个大连通子图和几个我不感兴趣的小连通子图。在绘制这些子图之前，我不知道如何找到它们，所以如果有graph_tool提供的方法，我会感兴趣的。
如果有帮助，这就是来源：
浏览 2提问于2018-07-05得票数 1
回答已采纳
给定一个连通图，每个节点都有一个整数(正或负)，如何找出节点值之和为最大值的子图？
在一个简化的例子中，如果这个图是一个线性链表，那么问题就变成了“在一维数组中返回子数组，其中子数组的和是最大的”。我看过一些图形算法，但还没有找到确切的解决方案。
浏览 1提问于2013-09-28得票数 2
2回答
我想把有向图中的一个单连通分支定义为一个子图，其中对于每一对节点u和v，存在一条从u到v或从v到u的路径。它还应该具有这样的性质，即它不是另一个单连通分支的子图。
浏览 2提问于2013-07-21得票数 0
回答已采纳
1回答
我已经搜索了有关子图枚举的相关问题。但是，它们不符合我的要求(*)。(如果我误解了什么，请告诉我。)(*)我已经搜索了和，但它们都分别针对顶点标记的诱导子图和完全子<
浏览 1提问于2015-04-30得票数 4
2回答
来自
上面的图是连通的，当所有有向边都被无向edges.But替换时，B到D或D到B之间没有路径，这违反了弱类型的property..Am I，对吗？
浏览 2提问于2013-09-06得票数 4
回答已采纳
2回答
在无向图中，我想要找到最大连通分量。我阅读了networkX的API文档，找到了这个函数nx.connected_component_subgraphs()。但是我不知道如何使用它，因为它的返回值是一个生成器，我不能导出最大连通组件的子图。
它和一个一样。但是图是有向的。我想找出有向图的最大弱连通分量。如何利用networkX中的内建函数求出无向图中最大连通分量和有向图中<em
浏览 8提问于2014-10-07得票数 8
回答已采纳
1回答
我试图实现Tarjan的强连通图算法()，这是我的代码，我很困惑为什么顶点4和顶点5也输出为强连通组件？
我使用的是一个非常简单的图表，只有5个节点需要测试。我的代码是用Python2.7编写的。
浏览 6提问于2017-01-07得票数 1
回答已采纳
我有一个有一百万个节点的图。其中有许多不连通的子图。我想知道最大的不连通子图是什么。例如，在这个图的例子中，我们得到了三个断开连接的子图，所以对于这个例子，输出将是7。
浏览 7提问于2017-01-12得票数 3
回答已采纳
3回答
组合优化
、、、
假设我们有一个连通的无向图: G=(V，E)。我们有一个定义在连通集上的任意函数F，即给定一个任意连通集CS，F(CS)将给我们一个实数值。现在的问题是:我们想从G中找到一组不相交的连通集，这样：(1)每个连通集
浏览 1提问于2010-10-13得票数 7
2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
我希望能够将我的图分成子组件，这样删除任何单个节点都不会创建更多的子组件(不包括单个节点)。作为示例，请参见下面的两个图像。
浏览 13提问于2019-03-27得票数 0
回答已采纳
2回答
给定一个连通的无向图，寻找具有最小最大度的生成树的问题已经得到了很好的研究(M.F¨urer，B.Rahvachari，“近似最小度生成树到最优度的1以内”，ACM-SIAM离散算法研讨会(SODA)，这个问题是NP难的，文献中已经描述了一种近似算法。
我对以下问题感兴趣-给定一个连通无向图G= (V1，V2，E)，找出所有内部节点(非叶子节点)上具有最大最小度的生成树。或者有一个多项式时间的算法来解决它吗？此外，为了方便起见，可以将
浏览 1提问于2013-03-18得票数 3
3回答
子图枚举
、
枚举父图的所有子图的有效算法是什么？在我的特殊情况下，父图是一个分子图，因此它将是连接的，并且通常包含少于100个顶点。
编辑:我只对连通子图感兴趣。
浏览 4提问于2011-05-13得票数 10
回答已采纳
1回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助
浏览 36提问于2019-06-12得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
