伊莉討論區

標題: 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!