什麼是根切割節點，橋樑切割節點，父切割節點在尋找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頂點？

回答

相關問題