如果添加了新边，图的强连通组件的数量如何变化？ [英] How can the number of strongly connected components of a graph change if a new edge is added

问题描述

练习：22.5-1 CLRS

如果添加新的
边缘，图形中强连通分量的数量如何变化？

某处给出的答案是如果一个新的边缘被添加，两件事情之一可能会发生。

1）如果新边连接属于强连接组件的两个顶点，强连接组件的数量将保持不变。
）2）如果边缘连接两个强连通的组件，并且边沿与两个组件之间现有路径的反方向，则将建立一个新的强连通组件，增加组件的数量。


我认为第二点是不正确的。
假设我们有两个强连通的组件 C 和 C'
a）如果它们之间不存在边缘或边缘 C-> C'，并且新边缘以 C-> C' 然后什么都不会发生。
）b）如果它们之间存在边 C-> C'，并且新边连接为 C' - > C ，则C'将被合并到C将强连通分量的数量减1，因为每个顶点都可以彼此到达。


如果我错了，请纠正我。 你完全正确。你所引用的答案在其描述中是错误的：添加边只会减少强连接组件的数量。一旦添加了所有可能的边界，只剩下一个强连通的组件 - 整个图表。

Exercise: 22.5-1 CLRS
How can the number of strongly connected components of a graph change if a new edge is added?

Somewhere the answer given is If a new edge is added, one of two things could happen.
1) If the new edge connects two vertices that belong to a strongly connected component, the number of strongly connected components will remain the same.
2) If, instead, the edge connects two strongly connected components, and the edge is in the reverse direction of an existing path between the two components, then a new strongly connected component will be made, increasing the number of components.

I think the second point is incorrect. Lets say we have two strongly connected component C and C'
a) If no edge or edge C->C' exists between them and new edge connects as C->C' then nothing will happen.
b) If edge C->C' exists between them and new edge connects as C'->C then C' will be merged to C decreasing the number of strongly connected component by 1 as every vertex will be reachable from each other.

Please correct me if i am wrong.

解决方案

You're exactly correct. The answer you quoted is wrong in its description: adding edges is only ever going to decrease the number of strongly connected components. Once all possible edges have been added, there's just a single strongly connected component left - the entire graph.

这篇关于如果添加了新边，图的强连通组件的数量如何变化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！