iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
Software Development

圖論與演算法之間的相互應用系列 第 8

圖的連通 (2)

8.3 找出雙連通元件

圖 G 上面的雙連通元件 (Biconnected Component) 是指,一個極大的子圖,使得該子圖內不存在關節點。
經過一些有趣的證明以後,可以知道圖 G 上的每一條邊,至多屬於一個雙連通元件。
但是,同一個點可能分屬多個雙連通元件。因此,如果要找出雙連通元件,得把邊分成很多等價類來下手。

https://ithelp.ithome.com.tw/upload/images/20210922/20112376mNr1STOJjB.png

由於每一個點可能屬於許多雙連通元件,我們可以用一個點來代表雙連通元件、而將雙連通元件與接觸到的割點以邊連起來。連起來以後可以證明它會形成一棵樹,而這樣的樹我們稱為 BC樹 (Block-Cut Tree)。

要怎麼找出雙連通元件呢?一個可行的演算法如下:首先找一棵生成樹,接著,對於每一條不是樹上的邊 (u, v),都可以在樹上找一條路徑,形成一個環,這個環通常稱為 fundamental cycle。簡單來說,這個環上所有的邊,都屬於同一個雙連通元件。因此,我們可以用併查集(或甚至是全部記錄下來以後跑一次 DFS) 把雙連通元件裡面的邊都合併起來,就能得到要得結果啦。

8.4 耳分解 Ear Decomposition

還有另外一種建構雙連通圖的方式:從一個圈開始,然後每一次挑兩個點,額外增加一條路徑。如果這兩個點允許是同一個點,那麼這個耳分解生出來的圖是 2-邊連通的(即拿掉一條邊,圖仍然是連通的,但可能拿掉點就會不連通了)。如果每次挑選的兩個點都是相異的點,那這個耳分解又被稱為開耳分解 (open ear decomposition)。


上一篇
圖的連通 (1)
下一篇
圖的連通 (3)
系列文
圖論與演算法之間的相互應用30

尚未有邦友留言

立即登入留言