如果添加新边,图表中强连接组件的数量如何变化

Question

练习:22.5-1 CLRS
如果添加新边,图表中强连接组件的数量如何变化？

给出答案的地方是如果添加新边缘,可能会发生以下两种情况之一.
1)如果新边连接属于强连接组件的两个顶点,则强连接组件的数量将保持不变.
2)相反,如果边缘连接两个强连接的组件,并且边缘处于两个组件之间的现有路径的反方向,则将形成新的强连接组件,从而增加组件的数量.

我认为第二点是不正确的. 假设我们有两个强连接的组件C 和C'a
)如果它们之间不存在边缘或边缘C-> C',并且新边连接为C-> C' 则不会发生任何事情.
b)如果 它们之间存在边 C-> C'并且新边连接为C' - > C, 则C'将合并为C,将强连通分量的数量减少1,因为每个顶点可以彼此相连.

如果我错了,请纠正我.

Answer 1

你完全正确.你引用的答案在描述中是错误的:添加边缘只会减少强连接组件的数量.一旦添加了所有可能的边,就只剩下一个强连接的组件 - 整个图.