Biconnected components是什麼東西?

演算法出了個作業  輸入一個Adjacency Matrix的無向圖利用演算法來找出所有Biconnected components
但老師解釋的有點模糊  我聽不太懂定義
誰可以跟我解釋一下Biconnected components到底是什麼嗎

ponchi96

回復

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

otome5969

重連通份量 (Biconnected Component)

     在無向連通圖G中，當且僅當刪去G中的頂點 v及所有依附於v的所有邊後，可將圖分割成兩個或兩個以上的連通份量，則稱頂點v為關節點。
...

瀏覽完整內容，請先 註冊 或 登入會員

cornhoilio

首先是你要知道biconnected graph的概念。
任意刪掉一個Edge，依然可以在任兩端點中找到simple path。
這樣的圖我們叫他biconnected graph。

biconnected component 的話，就是你要將一個無向圖分成多個connected component
而且那些component又符合biconnected graph的特性。
這樣這些component就稱為biconnected component。

學弟其實你不懂可以去lab問助教，在E689，我想學長會很樂意教你的。哈哈哈～...

瀏覽完整內容，請先 註冊 或 登入會員