點/邊連通度
定義
以下內容的定義，請參見 圖論相關概念：
- 邊連通度、邊割集；
- 點連通度、點割集；
- 團。
性質
Whitney 不等式
Whitney 不等式（1932）給出了點連通度 \(\lambda\)、邊連通度 \(\kappa\) 和最小度 \(\delta\) 之間的關係：
證明
直覺上，如果有一個大小為 \(\lambda\) 的邊割集，其中每一條邊任選一個端點，就可以得到一個大小為 \(\lambda\) 的點割集，所以第一個不等式成立。
與度最小的結點（如有多個，任選一個）相鄰的所有邊構成大小為 \(\delta\) 的邊割集，所以第二個不等式也成立。
這個不等式不能改進；換言之，對每個滿足它的三元組，均可以找出滿足這個三元組的圖。
構造
把兩個大小為 \(\delta + 1\) 的團用 \(\lambda\) 條邊連起來，使兩個團分別有 \(\lambda\) 和 \(\kappa\) 個不同的結點被連在這些邊上。
Menger 定理
由 最大流最小割定理（又名 Ford–Fulkerson 定理）可推出，兩點間的不相交（指兩兩沒有公共邊）路徑的最大數量等於割集的最小大小（這個推論又叫 Menger 定理——譯者注）。
計算
以下圖的邊權均為 \(1\)。
用最大流計算邊連通度
枚舉點對 \((s, t)\)，以 \(s\) 為源點，\(t\) 為匯點跑邊權為 \(1\) 的最大流。需要 \(O(n^2)\) 次最大流，如果使用 Edmonds–Karp 算法，複雜度為 \(O(|V|^3 |E|^2)\)。使用 Dinic 算法可以更優，複雜度為 \(O(|V|^2 |E| \min(|V|^{2/3}, |E|^{1/2}))\)。
全局最小割
使用 Stoer–Wagner 算法 只需跑一次無源匯最小割即可。複雜度為 \(O(|V||E| + |V|^{2}\log|V|)\)，一般可近似看作 \(O(|V|^3)\)。
點連通度
仍然枚舉點對，這次把每個非源匯的點 \(x\) 拆成兩個點 \(x_1\) 和 \(x_2\)，並連邊 \((x_1, x_2)\)。把原圖中所有邊 \((u, v)\) 換成兩條邊 \((u_2, v_1)\) 和 \((v_2, u_1)\)。此時最大流等於 \(s\)、\(t\) 之間的最小點割集大小（又稱局部點連通度）。複雜度與用最大流計算邊連通度相同。
本頁面譯自博文 Рёберная связность. Свойства и нахождение、Вершинная связность. Свойства и нахождение 與其英文翻譯版 Edge connectivity/Vertex connectivity。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。
延伸閲讀
- 論文 Connectivity Algorithms 介紹了近年來連通度計算算法的進展。感興趣的讀者可以自行瀏覽。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：jifbt
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用