Let
G(V,E)
, an undirected, connected graph with no bridges at all. Describe an algorithm which direct the edges, so the new graph is an SCC.
我推荐的算法
所以我们从任意顶点运行 DFS。我们注意到,由于它是一个无向图,因此只有树边和后边(对吗?)。我们相应地连接边(树边将指向“向下”,后边将指向“向上”)。
证明的开始
我们注意到该图没有桥。因此,每条边都是某个循环的一部分。因此,某个循环中最后被发现的边一定是后边。
现在,我认为其余的证明需要证明我们总是可以“爬”到根,因此该图是一个 SCC。
如果你能帮我连接点(或顶点 XD),我会很高兴
谢谢
最佳答案
您正在寻找的是 Robbins' Theorem 的证明.
有关更正式的证明,您可以查看 this paper (见定理 2 的证明)。
以下不是正式的证明,但这是您可以想到的一种方式:
正如您已经提到的,由于没有桥,每条边都是某个循环的一部分。由于您希望输出图为 SCC,因此此输出图(来自任何顶点)上的 DFS 必须仅具有back-edges 和tree-edges。它不能有forward-edges 或cross-edges。
假设我们有一条从s
到t
的forward-edge。这意味着在我们为了构建图形而运行的 DFS 中,t
是在 s
的子 DFS(递归调用)中发现的,并且没有其他灰色或白色相邻的。但这不是真的,因为每当我们在 DFS 中发现 t
时,我们仍然会有灰色相邻。
假设我们有一条从 s
到 t
的交叉边。这意味着 t
的子 DFS 在 s
被发现之前已经结束。同样,这在我们的 DFS 中不会发生,因为当首先发现 t
时,我们会在其子 DFS 或相反方向发现 s
。
这是一个简单的图表,可以帮助您了解这些情况。
关于algorithm - 使无向图成为强连通分量(SCC),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39545803/