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