伊莉討論區
標題:
Biconnected components是什麼東西?
[打印本頁]
作者:
otome5969
時間:
2011-3-28 05:51 PM
標題:
Biconnected components是什麼東西?
提示:
作者被禁止或刪除 內容自動屏蔽
作者:
ponchi96
時間:
2011-3-28 08:31 PM
回復
1#
otome5969
重連通份量 (Biconnected Component)
在無向連通圖G中,當且僅當刪去G中的頂點 v及所有依附於v的所有邊後,可將圖分割成兩個或兩個以上的連通份量,則稱頂點v為關節點。
沒有關節點的連通圖叫做重連通圖。在重連通圖上, 任何一對頂點之間至少存在有兩條路徑, 在刪去某個頂點及與該頂點相關聯的邊時, 也不破壞圖的連通性。
一個連通圖G如果不是重連通圖,那麼它可以包括幾個重連通份量。在一個無向連通圖G中, 重連通份量可以利用深度優先生成樹找到。
http://www.cnblogs.com/bless/archive/2008/09/28/1256875.html
由於這個我沒學過,只能幫你找資料
作者:
cornhoilio
時間:
2011-4-1 12:39 PM
首先是你要知道biconnected graph的概念。
任意刪掉一個Edge,依然可以在任兩端點中找到simple path。
這樣的圖我們叫他biconnected graph。
biconnected component 的話,就是你要將一個無向圖分成多個connected component
而且那些component又符合biconnected graph的特性。
這樣這些component就稱為biconnected component。
學弟其實你不懂可以去lab問助教,在E689,我想學長會很樂意教你的。哈哈哈~
歡迎光臨 伊莉討論區 (http://a401.file-static.com/)
Powered by Discuz!