在解决一些算法问题时，遇到了一个使用一些双连接组件属性的问题。
假设顶点A和B在相同的双连通分量中。在那个分量中有边E(u，v)。那么，对于任何一对A、B、E(都在相同的双组件中)，总是可以有一条从A到B
浏览 14提问于2017-12-19得票数 1
回答已采纳
我有一个无向图G(V，E)。我要解决的问题分为两部分：
第1部分:给定图和图中的一对顶点，找到包含在这对节点之间的所有路径中的边。第2部分:给定图，找出所有这样的边，使每个边沿着图中任意两个顶点之间的所有路径存在。第2部分的一个示例:让图有节点，{a, b, c, d, e,
浏览 5提问于2017-03-03得票数 1
回答已采纳
1回答
寻找一些定义澄清一个简单的问题。考虑图a-B，其中A和B是顶点，它们之间有一条边。它们之间的边会被认为是“切边”，因为它的删除断开了图形的连接吗？还是“边缘”需要增加连接组件的数量，而不仅仅是组件？
浏览 10提问于2016-05-02得票数 1
回答已采纳
3回答
单连通图是一个有向图，它最多有1条路从u到v∀u，v。
现在再次运行DFS，但这次从顶点开始，以减少完成时间。只对某些以前的DFS中未访问的顶点运行此DFS。如果我们在同一分量中找到一个交叉边或一个前向边，那么它就不是单连通的</
浏览 3提问于2013-11-12得票数 2
没有任何限制，你必须跨越每条边，只有一次，或每一个顶点。图中是否有这样一条路径存在的必要条件和充分性(如欧拉路径存在的节点度)，还是证明有或没有这样一条路径的已知算法(也许从起始路径的所有边求出最小路径)？我已经考虑了几种可能性，其中最强的是将强连接的组件折叠成单个超级节点，然后检查生成<em
浏览 1提问于2013-03-20得票数 2
1回答
此图中的SCC为{a，b，e}，{d，g}和{c，d，h}。但是这个图中的循环是相同的成分，对吗？
那么，SCCs和有向循环到底有什么区别呢？它们只在具体情况下有所不同吗？
浏览 2提问于2022-11-12得票数 0
回答已采纳
1回答
我有一个图，其中每个节点都是一个3D点，边表示3D空间中这些点之间的距离。图不是完全连通的。这意味着在A点和B点之间，可能有一条直接的路可走，也可能有多个阶段的路(例如A->C->D->E->B)。我想找到通过给定的一组点的最短封闭路径(所有的点都应该位于路径<
浏览 2提问于2019-11-07得票数 1
回答已采纳
1回答
删除属于两个单独的强连接组件的两个顶点之间的边不会修改总数。但是，删除属于同一强连接分量的两个顶点之间的边会如何影响该数字？它应该将其增加1，但是如果这两个节点之间有多条路径怎么办？或者只存在唯一的路径，该路径将被删除更改？
浏览 3提问于2015-01-09得票数 1
22.3-13 *有向图G是单连通的，如果u -> v意味着对于所有顶点V，G至多包含一条从u到v的简单路径。给出了一个判定有向图是否为单连通的有效算法。但我
浏览 1提问于2013-05-20得票数 0
1回答
我希望找到一组从开始节点到结束节点的路径，以便这些路径共同包含尽可能多的图的边。或者更准确地说:给定一个可能包含圈的有向图，以及两个顶点u和v，我想找一个从u到v的有限路径集P，使得对于u和v之间不在P中的任何路径q，<e
浏览 47提问于2021-07-26得票数 0
1回答
这听起来可能很傻，但是否有可能出现这样的情况，即图的边连通分量的数目大于图中的顶点数？
我认为这是不可能的，而且可以用小图快速验证。这是一个基本的逻辑尝试，为什么这是不可能从直觉，如果我们继续添加边，一个图，希望它将增加比内连接组件的数量，相反，它将减少组件的数量，因为它将连接更多的组件，以前没有连接。这样，就可以从像结构化图这
浏览 2提问于2019-11-06得票数 0
我正在做一个任务，其中一个问题要求导出一个算法来检查有向图G=( V，E)是否是单连通的(对于V的所有不同的顶点u，v，至多有一条从u到v的简单路径)。当然你可以暴力检查它，这就是我现在正在做的，但我想知道是否有更有效的方法。有谁能给我指个方向吗？
浏览 0提问于2010-03-25得票数 13
回答已采纳
2回答
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能有指数型的简单路径数。但是，如果我们只对两端顶点之间至少有一条简单路径的顶点感兴趣呢？即：给出了一个无向图和两个不同的顶点，是否有一个多项式时间算法，在这两个顶点之间至少找到一个
浏览 2提问于2012-05-30得票数 15
回答已采纳
1回答
如何以最少的步骤删除一个图？
、、、、
给定有向图，如何找到删除最小节点数以删除整个图所需的顺序？我假设如果一个节点被删除，连接到它的所有外部节点(任意程度)也会被删除。例如，在二进制搜索树中，删除树中所有节点的最快方法(给定假设)是删除根节点。然而，给定任何一个图表，如何才能确定要删除哪些节点？我的想法(很慢)：
重复，直到没有剩馀的节点。为什么这是一个很好的问题：假设我们得到了一
浏览 1提问于2015-09-07得票数 3
UniqueVertices: Path和UniqueVertices: Global有什么区别？ path“-保证不存在重复顶点返回的路径。“全局”--保证每个顶点在遍历过程中最多被访问一次，无论从起始顶点到这个顶点有多少条路径。如果以最小深度>1时开始，则可能根本不返回在最小深度之前找到的顶点(它可能仍然是路径的一部分)。注意:使用此配置，结果不
浏览 1提问于2021-01-23得票数 0
1回答
在解决有关DFS的问题时，我注意到了一些东西，我无法正式证明或找到一个自相矛盾的例子。u，v在同一SCC (强连接分量)当且仅当u，v在同一DFS树中运行。我的要求正确吗？
浏览 2提问于2021-05-07得票数 1
回答已采纳
有一个二部图B(E，V1，V2)使得e= ( v1，v2)，对于E，V1，V1，V2，v2，e∈E，∈∈。B中的边是定向的。我想做一个图G(E -∪E'，V2 V2)，使得图G是强连通分支，有最小尺寸(E‘)。(sizeof(A)是集合A中元素的个数) E‘不必是V
浏览 0提问于2012-06-28得票数 0
2回答
我想把一个有向无圈图分解成最小数目的分量，这样在每个分量中，下列性质都成立--对于一个分量中的所有对顶点( u，v)，都有从u到v或从v到u的路径。
这有什么算法吗？我知道，在这种情况下，当or被和替换时，这与查找强连接组件的数量(使用DFS是可能的)是一样的</em
浏览 4提问于2015-11-09得票数 2
回答已采纳
云服务器
ICP备案
对象存储
腾讯会议
云直播
腾讯云开发者
