iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
Software Development

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

圖的連通 (4)

9 三連通圖

如果一圖 G 有至少 k 個點、並且拿掉任何 k-1 個點以後都還是保持連通的,那麼我們就說這個圖是 k-點連通的。

9.1 判斷 k 連通圖的演算法

如果拿掉 k-1 個點會讓整張圖變得不連通,那麼就會有兩個點 s, t,它們之間的 s-t 連通度不超過 k-1。因此,我們可以枚舉任兩點對,並且利用最小割(Minimum vertex s-t cut) 的演算法,我們可以在 O(n^2 * FindMinCut) 的時間判斷這個圖是不是 k 連通的。

從 Tarjan 在 1972 年發表了 DFS 演算法並且拿它在線性時間 O(m) 來判斷一個圖是否為雙連通以後,也僅有 Hopcroft 與 Tarjan 在隔年 1973 延伸了 DFS 演算法並且聲稱在 O(m) 時間判斷一個圖是否為 3-連通。但是對於 k >= 3 以後,有將近 35 年的時間,大家並不知道是否存在線性時間或幾乎線性時間的演算法,判斷一張圖是否為 k(k>=4) 連通的。

直到在 2019 年這個問題,由 Nanongkai, Saranurak, Yingchareonthawornchai 等人得到了重大突破。他們設計出了一個能在 ~O(m + nk^3) 時間判斷一張圖是否為 k 連通的演算法。想法非常有趣,大家可以參考下面這個影片由 Saranurak 介紹與講述:

https://www.youtube.com/watch?v=V1kq1filhjk


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

尚未有邦友留言

立即登入留言