什么是根切割节点，桥梁切割节点，父切割节点在寻找aritculation顶点？

什么是根切割节点，桥梁切割节点，父节点在寻找顶点的顶点？有人可以用例子来解释一下。特别是我对桥切节点感到困惑。其认定中说什么是根切割节点，桥梁切割节点，父切割节点在寻找aritculation顶点？

如果从V最早到达顶点为v，则删除单个边缘（父[V]，V）断开图表

如何可以在最早到达顶点从v是v？

来源

2012-12-15 jairaj

你从哪里得到这个定义？ – Origin

我正在阅读它的形式skiena的算法设计手册。它初始化每个节点的最早可到达的顶点到自己，并在图形遍历后使用dfs，如果它保持不变，那么它是一个网桥节点。 – jairaj

不知道你还在乎，但现在我在读同一文本

根切除节点

我觉得根切除节点是很明显的

桥切除节点

记住更改五世的reachable_ancestor以下三个条件必须满足：

存在边缘（V，Y），该后边缘
对于边缘（V，Y）中，y不是V的父
entry_time y分别为v程序的的entry_time之前reachable_ancestor

所以，如果你看一下这本书的图5.13，你会看到，因为一个（在树中较低）断桥节点没有父母，是不是Y，它永远不会有它的reachable_ancestor从初始的reachable_ancestor [v] = v改变，这又使得它的父节点成为桥切节点，并且（仅仅因为它不是叶子）使得该节点也是桥切节点。

父切除节点

在图5.13的原因是五世的父母是父母切除节点（相对于一个断桥节点），是因为桥梁必须满足以下条件：

边缘是树边缘
否后边缘从v或低于连接到y或以上

显然在图中，v的孩子连接到它的父母（y）和以上，使得v和y之间的边不是一座桥，而是使y仍然是一个切割节点。

希望有帮助！

来源

2013-05-10 14:48:02 gonzofish

谢谢你的澄清@gonzofish – Eddie

这是一个非常古老的问题，但我想确保一件事。它说，“如果v最早的可到达顶点是v的父亲......”。但是，在书中给出的例子中，v的可达顶点是v的父亲？（图5.13）。要发生这种情况，必须有从v后面的边缘，没有。我在卡住process_edge如何设置v可以作为它的父母的可达祖先。请赐教。 – Javidan

什么是根切割节点，桥梁切割节点，父切割节点在寻找aritculation顶点？

回答

相关问题