5

练习:22.5-1 CLRS
如果添加新边,图的强连通分量的数量如何变化?


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

我认为第二点是不正确的。 假设我们有两个强连通分量CC'
a) 如果它们之间不存在边或边C->C'并且新边连接为C->C' 那么什么都不会发生。
b) 如果它们之间存在边 C->C' ,并且新边连接为C'->C ,则 C' 将合并到 C,将强连通分量的数量减少 1,因为每个顶点都可以相互访问。

如果我错了,请纠正我。

4

1 回答 1

5

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

于 2013-08-31T06:59:00.737 回答