graph - 什么是根切割节点，桥切割节点，父切割节点在寻找关节顶点？

Question

什么是根切割节点，桥切割节点，父切割节点在寻找关节顶点？有人可以用例子解释一下吗？我特别对桥接节点感到困惑。它的定义说

如果从 v 中最早可达的顶点是 v，则删除单边 (parent[v], v) 断开图

v 最早可达的顶点怎么可能是 v ？

Answer 1

不知道你是否还在乎，但我现在正在阅读相同的文本

根切节点

我认为根切割节点非常明显

桥切节点

记住要改变v的reachable_ancestor必须满足以下三个条件：

• 有一条边 (v, y) 是后边
• 对于边 (v, y)，y 不是 v 的父级
• y的entry_time在v的reachable_ancestor的entry_time之前

因此，如果您查看本书的图 5.13，您会看到，因为一个（树上较低的）桥切节点没有不是 y 的父节点，所以它的reachable_ancestor 永远不会从最初的reachable_ancestor [v ] = v。这又使它成为桥切节点的父节点，并且（仅因为它不是叶子）使该节点也成为桥切节点。

父切割节点

图 5.13 中 v 的 parent 是 parent cut-node（而不是 bridge cut-node）的原因是因为 bridges 必须满足以下条件：

• 边缘是树边缘
• 没有后边缘从 v 或以下连接到 y 或以上

很明显，在图中，v 的子节点连接回它的父节点 (y) 及以上，使得 v 和 y 之间的边不是桥，但使 y 仍然是切割节点。

希望有帮助！