如果添加了一条新边，一个图的强连通分量数量如何改变？

Question

练习：22.5-1 CLRS
如果添加了一条新边，图的强连通分量数量会如何改变？

某处 给出的答案是，如果添加一个新的边，则可能发生以下两种情况：
1）如果新的边连接两个属于强连通分量的顶点，则强连通分量的数量将保持不变。
2）相反，如果边连接两个强连通分量，并且该边与现有路径的方向相反，则会形成一个新的强连通分量，从而增加了分量的数目。

我认为第二点是错误的。 假设我们有两个强连通分量C和C'
a）如果它们之间不存在边或边缘C->C'，并且新的边缘连接为C->C'，则什么也不会发生。
b）如果它们之间存在边缘C->C'，并且新的边缘连接为C'->C，则C'将合并到C中，将强连通分量的数量减少1，因为每个顶点都可以互相到达。

如果我错了，请纠正我。

- Amitesh

---

这个问题似乎不适合讨论，因为它涉及到数学。 - user85109

我同意引用的答案。假设您有两个强连通分量，即 C 和 C'。现在，在无向图中添加一条新边D。只有从 C 到 D 的边。在这种情况下，无法从 D 中到达任何其他顶点。因此，D 成为一个独立的强连通分量。现在，该图的总强连通分量为 3，即C、C'和D。如果我错了，请纠正我 :) - GAURI MNIT

@GAURIMNIT 我认为SCC只适用于有向图。如果是无向图，则意味着所有边都是双向的，因此如果您能从C到达D，则可以暗示您也可以从D到达C。 - Amitesh

Answer 1

您说得非常正确。您引用的答案在描述上是错误的：添加边仅会减少强连通分量的数量。一旦添加了所有可能的边，就只剩下一个强连通分量 - 整个图。

- Timothy Shields