强连通图的最小增量

Question

我有一组节点和它们之间的有向边集。这些边没有权重。

如何找到最小数量的需要添加的边，使得图强连通（即每个节点都能到达所有其他节点）？这个问题有一个名称吗？

- Jan Langer

Answer 1

这是一个非常经典的图论问题。

1. 运行像Tarjan-SCC算法这样的算法，以查找所有强连通分量(SCCs)。将每个SCC视为新节点，根据原始图连接它们之间的边缘，我们可以得到一个新的图形。显然，新图是一个有向无环图(DAG)。
2. 在DAG中，找到所有入度为0的顶点，我们将它们定义为{X}; 找到所有出度为0的顶点，我们将它们定义为{Y}。
3. 如果DAG只有一个节点，则答案为0; 否则，答案为max(|X|, |Y|)。

- Jun HU

---

我不确定我理解这个解决方案。考虑边为 (a,b),(b,e),(e,b),(a,c),(c,f),(f,c),(b,d),(c,d) 的图表。结果的 DAG 是 (A,B),(A,C),(B,D),(C,D)，其中 B={b,e} 和 C={c,f}。因此 X=Y={B,C}，因此 |X|=|Y|=2。然而，显然，我们只需要添加单条边 (d,a) 到原始图形即可使其强连通。 - mitchus

当入度设置为0时，该算法在以下图形中失败：(a,b),(b,d),(d,b),(a,c),(c,e),(e,c)，结果为DAG (A,B),(A,C)。在这里，max(|X|,|Y|)=1，但我们需要两条边来使图形强连通。 - mitchus

在新的DAG中，@mitchus的入度为0，B和C的出度为0。因此，|X|=1，|Y|=2，答案为2。 - Jun HU

我们如何找到所需的最小边缘（如果可能的话）？ - Sanjit Prasad

有人能解释一下为什么 max(|x|, |y|) 可以得出答案吗？ - router

我上面评论的一个答案是：试着把DAG看作是一个拓扑排序，其中起始节点具有入度==0，最后节点具有出度= =0。现在尝试将它们连接起来。 - router

Answer 2

就我个人而言，似乎最简单（边数最少）使有向图强连通的方法是只有涉及所有节点的循环; 因此，最小边数将仅为N，其中N是节点数。如果已经存在边，则可以执行以下操作：将最长的现有有向路径连接到下一个不与当前路径重叠的最长路径，直到形成完整的循环（一旦您的路径包含所有节点，请连接端点以形成循环。）

不确定是否有更正式的定义，但对我来说似乎是合乎逻辑的。

- Josh Buell

Answer 3

我将找到所有弱连接的组件，并将它们绑在一个循环中。

编辑：

更明确地说，我的想法是如果你有WCCs W(1),...,W(n)，使得W(i%n + 1)可以从W(i)的任何节点到达，对于i=1 to n。

- mitchus

---

这是不正确的。考虑有向图 a -> b。它有两个强连通分量，但只有一个弱连通分量，所以你的算法什么也做不了。 - Fred Foo

在这种情况下，它会将单个WCC绑定在一个循环中，即添加边缘b->a。我会添加更多细节以使其更明确。 - mitchus

抱歉，我不是很明白你的意思。 - Fred Foo

@larsmans，您对答案的某个特定部分持有不同意见吗？无论如何，Jun HU 的回答更好 :) - mitchus