iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
Software Development

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

圖的連通 (1)

8 割點、橋、雙連通元件

現在讓我們回到無向圖的演算法。給一張圖,要判斷這張圖是否為連通圖相當簡單:只要做一次 BFS 或 DFS 就可以了。但是,如果我們想知道當某個點壞掉、或是某條邊壞掉的時候,這張圖是否仍然連通,那麼問題就會變得有趣許多。

如果去掉一個點(同時失去所有其相鄰的邊),就會讓整張圖斷開的話,我們稱這個點為割點 (cut-vertex)、或者稱為關節點 (articulation point)。如果去掉一條邊,就會讓整張圖斷開,那麼我們稱這條邊為一座橋。

8.1 尋找關節點的 Tarjan 演算法

Robert Tarjan 可以說是 DFS 演算法的開疆始祖。許多與 DFS 有關的演算法都以 Tarjan 為名。包含了前一節描述的強連通元件演算法,也有一個線性版本是 Tarjan 發表的(可以參考 Tarjan 在 1972 年的論文)。以今天的關節點問題來說,Tarjan 描述了一個使用 DFS 能找到所有關節點的演算法:
第一步:首先,找出一個 DFS 樹,樹上每個節點都有一個深度 depth(x)。
第二步:對於每一個節點 x,計算 lowpt(x),什麼是 lowpt(x) 呢?就是 x 這個點的所有子孫節點(包含 x 自身) 能夠透過非樹邊 (也就是回溯邊 back edges) 能夠抵達的最淺深度。這一步可以在線性時間內算完。

因此,對於一個節點 x 來說,如果其所有子孫能夠有一條回溯邊,到得了其祖先節點,那麼 x 一定不是關節點。反之,如果這個節點某個子孫節點 c 其 lowpt(c) >= depth(x),那麼代表拿掉 x 以後,可以將 x 的祖先與 x 的子孫分開。因此, x 在這個情形下一定是關節點。

8.2 判斷圖是否為雙連通

如果整張圖都不存在關節點,那麼我們便稱這張圖為雙連通的。因此我們知道存在一個線性 O(V+E) 時間的演算法,判斷這張圖是否為雙連通。

8.X 冷笑話

台北的捷運路網是否存在關節點呢?其實不存在,因為可以有雙連站,因此台北捷運是雙連通的,直通雙連。

參考資料

https://codeforces.com/blog/entry/71146
Tarjan 最早描述 DFS 的論文:https://epubs.siam.org/doi/10.1137/0201010

今天好混QQ


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

尚未有邦友留言

立即登入留言