algorithm - 向图形添加边对 SCC 的影响

Question

以下问题来自Skiena:

Adding a single directed edge to a directed graph can reduce the number of weakly connected components, but by at most how many components? What about the number of strongly connected components?

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

Suppose a graph G' use one vertex to represent a strongly/weakly connected component (SCC/WCC) of a directed graph G. Then G' is a DAG.

If the directed edge we add makes a cycle in the graph then all the vertices in that cycle are in a SCC so we reduce it to one vertex.

The number of SCCs reduced is n-1, where n is the number of vertices in the cycle.

Answer 1

您走在正确的轨道上。为了使其严格，您需要展示一个图的具体示例，该图具有 n 个强连通分量，其中添加一条边会将所有内容简化为单个强连通分量。

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

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

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

但是，如果你在图中加上边(v_n, v₁)，那么你就会形成一个循环，所有的节点都在一个单个强连接组件，在单个边添加中将数量从 n 减少到 1。

弱连通分量的情况不同。给定一个有向图，它的弱连通分量是图的无向版本的 CC。将边添加到无向图中只能将 CC 的数量减少一个，因为如果你尽可能幸运，边的端点将在不同的 CC 中，然后统一到一个 CC 中。所以增加一条边只能使弱连通分量的个数减少一个。