什么是根切割节点,桥梁切割节点,父切割节点在寻找aritculation顶点?
问题描述:
什么是根切割节点,桥梁切割节点,父节点在寻找顶点的顶点? 有人可以用例子来解释一下。 特别是我对桥切节点感到困惑。 其认定中说什么是根切割节点,桥梁切割节点,父切割节点在寻找aritculation顶点?
如果从V最早到达顶点为v,则删除单个 边缘(父[V],V)断开图表
如何可以在最早到达顶点从v是v?
答
不知道你还在乎,但现在我在读同一文本
根切除节点
我觉得根切除节点是很明显的
桥切除节点
记住更改五世的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仍然是一个切割节点。
希望有帮助!
你从哪里得到这个定义? – Origin
我正在阅读它的形式skiena的算法设计手册。它初始化每个节点的最早可到达的顶点到自己,并在图形遍历后使用dfs,如果它保持不变,那么它是一个网桥节点。 – jairaj