無向圖的關節點

當關於無向圖的入口點（根節點）發生變化時，關節點的類型和數量是否會發生變化？無向圖的關節點

如果它改變，那麼爲什麼會發生這種情況？

我明白，點可能會有所不同，但爲什麼點數有所不同？

這裏是我的圖： -

Graph

2016-10-31 ddwivedy

把'！'標記放在'[Graph] [1]'這樣的'之前''[Graph] [1]' – surajsn

正如Wiki article規定，鉸接點爲頂點，例如，如果它比的連接部件數量增加，刪除。這裏沒有關於入口點和DFS的信息：定義僅取決於圖本身。

因此，您的問題的答案是：不，如果您從不同節點遍歷圖形，則不應改變關節點。

如果您使用標準的基於DFS的算法來查找關節點，很可能您有一個錯誤。

2016-10-31 21:36:41

我在關節點中無法理解的是根節點應該有兩個獨立的子節點。在上面所述的圖中，爲什麼A（根）不被視爲切割頂點/關節點。 – ddwivedy

@IvanSmirnov已經很清楚地回答了這個問題。刪除A（連同其入射邊緣）不會影響連接組件的數量，因此它不是一個關節點。關節點與圖根無關或缺乏關係。 – Gene

回答