algorithm - 图表中的连接点和桥梁

Question

今天我了解了图中的连接点和桥(基本上是无向的)。

我读到的文字(史蒂文哈利姆的书)说

When we are in vertex u and v is its neighbor, then if dfs_low(v) >= dfs_num(u) then u is a cut vertex.

鉴于，

The condition becomes dfs_low(v) > dfs_num(u) while checking for bridges.

但我无法弄清楚为什么第二种情况(在桥梁中)平等性消失了。 请帮我解决这个问题。

PS:dfs_num(i) 对 dfs 中看到的顶点进行编号。

dfs_low(i) 告诉除了其父级之外的 i 可到达的最低编号顶点。

Answer 1

假设在所考虑的情况下，u 是一个接合点，但 u-v 不是一座桥。那么除了通过 u-v 链路之外，还会存在一条从 v 到 u 的路径；因此，从包含 u 的双连通分量传递到包含 v 的双连通分量的 DFS 最终将再次到达 u，从而在 dfs_low(v) >= dfs_num(u) 中提供相等性。 (出现不等式的大于部分是因为 u 是一个关节点，因此从 v 开始的路径如果不经过 u 就无法到达编号较小的顶点，并且 DFS 不会回溯此类路径。)

但是，如果 u-v 也是一座桥，则除了通过桥 u-v 之外，v 和 u 之间不存在任何其他路径。所以DFS永远不会再到达u；并且 DFS 达到 v 后的所有 dfs_num 值都将严格大于 dfs_num(u)。