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