在图中添加一条边对强连通分量的影响

Question

3

以下问题来自Skiena:

向有向图中添加单个有向边可以减少弱连接组件的数量，但最多可减少多少个组件？强连接组件数量呢？

这里是我的解决方案。这正确吗？

假设一个图G'使用一个顶点来表示有向图G的一个强/弱连接分量(SCC/WCC)。那么G'是一个DAG。

如果我们添加的有向边在图中形成一个循环，则该循环中所有顶点都位于一个SCC中，因此我们将其缩减为一个顶点。

减少的SCC数目是n-1，其中n是循环中的顶点数。

- Mougart

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Answer 1

你做得很好。为了使这个严谨，你需要展示一个具体的图例，其中有n个强连通分量，添加单个边缘将所有内容减少到单个强连通分量。

一种方法是形成一个由n个节点组成的链，链接在路径中，如下所示：

v₁ → v₂ → v₃ → ... v_n

有n个强连通分量，每个分量都由单个节点组成。

然而，如果将边缘（v_n，v₁）添加到图中，则会形成一个循环，并且所有节点都将位于单个强连通分量中，将数量从n减少到1个，仅通过添加单个边缘。

弱连通分量的情况不同。给定一个有向图，它的弱连通分量是该图的无向版本的连通分量。向无向图中添加一条边只能将连通分量的数量减少一个，因为如果你非常幸运，边的端点将在不同的连通分量中，然后统一成一个单独的连通分量。因此，添加一条边只能将弱连通分量的数量减少一个。