图中的关节点和桥梁

Question

今天，我学习了关于图中的关节点和桥梁（基本上是无向的）。

从我读（书由史蒂芬 - 哈利姆）经文说

当我们在顶点u和v是它的邻居，那么如果dfs_low(v) >= dfs_num(u)然后u是割点。

然而，

条件变为dfs_low(v) > dfs_num(u)同时检查 桥梁。

但我无法弄清楚为什么平等从第二种情况（桥梁）中消失。 请帮我这个。

PS：dfs_num(i)如在dfs中看到的那样编号顶点。

dfs_low(i)告诉编号最小的顶点可以从其父节点以外的其他节点到达。

Answer 1

假设在这种情况下，认为你是一个关节点，但u-v不是一座桥。那么除了通过u-v链接之外，将存在从v到u的路径;因此从包含u的双连通分量转移到含v的双连通分量的DFS最终会再次到达u，在dfs_low(v) >= dfs_num(u)中提供相等性。 （由于u是关节点，所以不等式的大于部分发生，因此v的路径无法通过u到达较低编号的顶点，并且DFS不会回溯这些路径。）

但是，如果uv也是一座桥梁，v和u之间不会有任何其他途径比通过桥梁uv。所以DFS永远不会再次到达你;并且在DFS达到v之后的所有dfs_num值将严格大于dfs_num(u)。