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

Question

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

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

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

Answer 1

不知道你是否还在乎,但我现在正在读相同的文字

Root Cut-Node

我认为root cut-node非常明显

桥切节点

请记住更改v的reachable_ancestor必须满足以下三个条件:

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

因此,如果你看一下本书的图5.13,你会看到,因为桥接节点中的一个(在树上较低)没有不是y的父节点,它将永远不会从初始的reachable_ancestor [v]更改它的reachable_ancestor ] = v.这又使它的父节点成为桥接节点并且(仅因为它不是叶子)使该节点也成为桥接节点.

父剪切节点

图5.13中v的父节点是父节点(与网桥节点相对)的原因是因为网桥必须满足以下条件:

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

很明显,在图中,v的子节点连接到它的父节点(y)和上面,使得v和y之间的边缘不是桥接,但是使y仍然是切割节点.

希望有所帮助!