圖論/k-連通圖

連通性的定義

設 u 和 v 是圖 $G$ 的頂點。

• 如果在 $G$ 中存在一條 $u-v$ 路徑，則稱 $u$ 和 $v$ 是連通的。
  
• 如果對於 $G$ 中的每一對頂點 $u$ 和 $v$ 都存在一條 $u-v$ 路徑，則稱 $G$ 是連通的，或稱連通圖。

邊連通度

從圖 $G$ 中刪除使其斷開的邊數的最小值 lambda($G$)，也稱為線連通度。斷開圖的邊連通度為 0，而具有圖橋的連通圖的邊連通度為 1。

頂點連通度

從圖 $G$ 中刪除使其斷開的頂點數的最小值 kappa($G$)。

設 lambda($G$) 是圖 $G$ 的邊連通度，delta($G$) 是其最小度，那麼對於任何圖，
kappa($G$) ≤ lambda($G$) ≤ delta($G$)

k-連通圖

• k-邊連通圖
  

如果一個圖的最小割集包含k條邊，並且刪除這些邊會導致圖斷開連線，那麼該圖的邊連通度為k。

• k-頂點連通圖
  

如果一個圖的最小割集包含k個頂點，並且刪除這些頂點會導致圖斷開連線，那麼該圖的頂點連通度為k。
1-連通圖被稱為連通圖；2-連通圖被稱為雙連通圖；3-連通圖被稱為三連通圖。

門格爾定理

• 邊連通度

對於$u$和$v$，最小邊割集的大小（即刪除最少數量的邊會導致$u$和$v$斷開連線）等於從$u$到$v$的成對邊不相交路徑的最大數量。

• 頂點連通度

對於$u$和$v$，最小頂點割集的大小（即刪除最少數量的頂點會導致$u$和$v$斷開連線）等於從$u$到$v$的成對頂點不相交路徑的最大數量。
（邊割集是指刪除這些邊會導致圖斷開的邊集；頂點割集或分離集是指刪除這些頂點會導致圖斷開的頂點集。）

最大流 (maximum flow) 最小割 (minimum cut) 定理

圖$G$中頂點$u$和$v$之間的最大流量，恰好等於斷開$G$連線並使$u$和$v$位於不同連通分量的最小邊集的權重。

• 最大流：圖$G$中頂點$u$和$v$之間的最大流量
• 最小割集：斷開 $G$ 中 $u$ 和 $v$ 所在的不同連通分量的最小邊集。