热门问题
时间线
聊天
视角

雙連通圖

移除少於兩點依然連通之圖 来自维基百科,自由的百科全书

Remove ads


圖論中,一個點雙連通圖是一個連通且「不可分離」的,意思是如果任何一個頂點被去除,圖仍是連通的。所以這樣一個雙連通圖就沒有割點英語Biconnected component2-點連通英語k-vertex-connected graph的性質和點雙連通是幾乎等價的,除了一條邊連接兩個點構成的圖,它是點雙連通的,但不是2-點連通的。

這個性質在維護一個有2度冗餘的圖中特別有用,為了防止去除一條(或連接)之後的不連通。

由於冗餘的這種特性,雙連通圖的使用在網絡領域非常重要(參見網絡流)。

定義

一個雙連通無向圖是一個連通圖,不會因為刪除任一個節點(和它的附帶邊)而變得不連通。

一個雙連通有向圖中,對於任何兩個頂點vw,都有兩條從vw的有向路徑,且除了vw以外沒有其他公共頂點。

更多資訊 頂點, 可能性數量 ...
Remove ads

參見

參考

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads