在删除边缘后查找图形是否仍然强烈连接

Question

强连通有向图是有向图,其中对于每两个顶点,并且存在从...到的直接路径以及从到的直接路径.令=(,)是强连通的有向图,并且let =(,)∈是图中的边.设计一种有效的算法,决定是否'=(,∖{}),没有边缘的图是强连接的.解释其正确性并分析其运行时间.

所以我所做的就是运行BFS并对标签求和,一次在原始图形上,然后再在G'中没有边缘(再次从)然后:如果第二个总和(在G'中)<原始总和(在G中)那么图表没有强烈连接.

PS这是我考试中的一个问题,我只得到3/13分,我想知道我是否应该上诉...

Answer 1

正如 Sneftel 指出的那样，距离标签只会增加。如果u不再有通往 的路径v，那么我猜v的标签将是无限的，因此标签的总和将从有限变为无限。然而，总和可以增加，而图表不会失去强大的连接性，例如，

u<----->v
 \     /|
  \|  /
    w

v由于通过 的间接路径，其中 的标签从 1 增加到2 w。