連通性 (圖論)

在數學與計算機科學中，連通性是圖論的一個基本概念：它是需要移除的元素（節點或邊）的最小數量，使得剩餘的節點分離成兩個或多個獨立的子圖。^[1]它與網絡流問題的理論密切相關。圖的連通性是衡量其作為網絡的韌性的重要標準。

連通節點和連通圖

在無向圖 $G$ 中，如果 $G$ 包含一條從 $u$ 到 $v$ 的路徑，則兩個頂點 $u$ 和 $v$ 被稱為是連通的。否則，它們被稱為是非連通的。如果這兩個頂點由一條長度為 $1$ 的路徑連接，即由一條邊連接，則這兩個頂點被稱為是相鄰的。

如果圖中的每一對頂點都是連通的，則稱該圖為連通的。這意味着，每一對頂點之間都有一條路徑。因此，如果一個無向圖 $G$ 中存在兩個頂點，使得 $G$ 中沒有任何路徑以這兩個頂點為端點，那麼這個無向圖就是非連通的。只有一個頂點的圖是連通的。有兩個或更多頂點的無邊圖是非連通的。

如果將一個有向圖的所有有向邊替換成無向邊，會產生一個連通（無向）圖，那麼這個有向圖被稱為是弱連通的。如果對於每一對頂點 $u$ 和 $v$ ，它包含一條從 $u$ 到 $v$ 的有向路徑，或者從 $v$ 到 $u$ 的有向路徑，那麼它就是單向連通的（也稱為半連通）。^[2]如果對於每一對頂點 $u$ 和 $v$ ，它都包含一條從 $u$ 到 $v$ 的有向路徑和一條從 $v$ 到 $u$ 的有向路徑，那它就是強連通的。

分量與割

連通分量是無向圖的極大連通子圖。每個頂點和每條邊都僅屬於一個連通分量。當且僅當一個圖有且僅有一個連通分量時，原圖就是連通的。

強連通分量是有向圖的極大強連通子圖。

連通圖 $G$ 的點割集（英語：Cut (graph theory)）是一組頂點，除去這些頂點會使 $G$ 變得不連通。點連通度（英語：k-vertex-connected graph） $κ(G)$ （其中 $G$ 不是完全圖）是最小點割集的大小。如果一個圖的點連通度為 $k$ 或更大，則該圖被稱為 $k$ -點連通的。

更確切地說，任何圖 $G$ （無論是否完全）如果至少包含 $k+1$ 個頂點，但不包含一個由 $k-1$ 個頂點組成的集合，使得移除該集合的點會使圖不連通，則稱其為 $k$ -點連通的；而 $κ(G)$ 的定義是使 $G$ 是 $k$ -點連通的最大的k。特別的，一個有 $n$ 個頂點的完整圖，表示為 $K n$ ，根本沒有點割集，但 $κ (K n) = n - 1$ 。

對兩個頂點u和v， $u$ 到 $v$ 的點割集是一個頂點的集合，從圖中移除這些頂點會使 $u$ 和 $v$ 不連通。局部點連通度 $κ (u, v)$ 是 $u$ 到 $v$ 的最小點割集的大小。對於無向圖來說，局部點連通度是對稱的；也就是說， $κ (u, v) = κ (v, u)$ 。此外，除了完全圖， $κ(G)$ 等於在所有不相鄰的頂點對 $u$ 到 $v$ 上 $κ (u, v)$ 的最小值。

$2$ -點連通也被稱為點雙連通。一個連通但不是 $2$ -點連通的圖 $G$ 有時被稱為可分離的。

類似地，以上概念可以被定義為邊的概念。在簡單情況下，切割一條特定的邊會使圖不連通，這條邊被稱為橋。更一般地， $G$ 的邊割集是一組邊，去除這些邊會使圖不連通。邊連通度（英語：k-edge-connected graph） $λ (G)$ 是最小的邊割集的大小，兩個頂點 $u$ 到 $v$ 的局部邊連通度 $λ (u, v)$ 是 $u$ 到 $v$ 最小的邊割集的大小，同樣，局部邊連通度是對稱的。如果一個圖的邊連通度為 $k$ 或更大，則稱該圖為 $k$ -邊連通的。

如果一個圖的點連通性等於其最小度數，則稱該圖為最大點連通的。如果一個圖的邊連通性等於其最小度數，則稱該圖為最大邊連通的。^[3]

參考資料

^ Diestel, R. Graph Theory, Electronic Edition: 12. 2005 [2022-08-25]. （原始內容存檔於2019-12-16）.
^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition (PDF). [2022-08-25]. （原始內容存檔 (PDF)於2020-01-10）.
^ Gross, Jonathan L.; Yellen, Jay. Handbook of graph theory. CRC Press. 2004: 335 [2022-08-25]. ISBN 978-1-58488-090-5. （原始內容存檔於2021-08-14）.

參見

代數連通度

[1] Diestel, R. Graph Theory, Electronic Edition: 12. 2005 [2022-08-25]. （原始內容存檔於2019-12-16）.

[2] Chapter 11: Digraphs: Principle of duality for digraphs: Definition (PDF). [2022-08-25]. （原始內容存檔 (PDF)於2020-01-10）.

[3] Gross, Jonathan L.; Yellen, Jay. Handbook of graph theory. CRC Press. 2004: 335 [2022-08-25]. ISBN 978-1-58488-090-5. （原始內容存檔於2021-08-14）.

[1]

[2]

[3]