# 連通性與 Menger 定理
雖然這篇被歸類在網路流量問題之中，但是為了銜接下一篇最大流量-最小割定理，我會暫時離題並討論一下什麼是「割 (cut)」。一般討論割的目的是為了瞭解一張圖 (graph) 是否足夠穩固，或至少要移除多少節點或邊才能使整張圖分為兩個連通塊 (component)。可以想像要是在一個公路的路網，被摧毀幾條公路就會使兩地之間無法溝通。顯然這是一個很重要的問題

本篇會來介紹點割 (vertex cut)、邊割 (edge cut) 與連通性 (connectivity)。最後會來介紹 Menger 定理，說明點割、邊割與路徑乃至於整張圖的關係。Menger 定理在圖論是個極為重要的存在，因為它的效力與許多不同的定理等價，像是 [Hall 定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)、 [Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)等都能使用 Menger 定理互相推出來

## 點割 Vertex Cut
### 定義
- 在一張圖 $G$ 中，若存在集合 $S\subseteq V(G)$ 使 $G-S$ 有多於一個連通塊，則 $S$ 是一個**點割 (vertex cut)**
- 給定 $x, y\in V(G)$，若存在集合 $S\subseteq V(G) - \{x, y\}$ 使 $G-S$ 沒有從 $x$ 到 $y$ 的路徑，則 $S$ 被稱為 **$x, y$ 點割 ($x, y$-cut)**
- $\kappa(x, y)$ 為最小 $S$ 的元素個數，即最小 $x, y$-cut 的大小

### 舉例
如下圖 $G$ 可以找到一個最小的 $x, y$-cut $S=\{b, c, d\}$，使 $\kappa(x, y)=3$

<img src="https://hackmd.io/_uploads/SkRNfljnJx.png" style="margin: 0 auto; display: block; width: 600px">

## 點連通性 Vertex Connectivity
### 定義
一張圖 $G$ 的點連通性寫作 $\kappa(G)$，為一張圖中最小 $S$ 的元素個數，使 $G-S$ 不連通或只剩一個節點。若一張圖是的點連通性最少為 $k$，則稱圖是 $k$-connected

可以將點連通性寫作 $\kappa(G)=min_{x, y\in V(G)}~\kappa(x, y)$

### 舉例
#### $K_n$ 的點連通性
不難看出，因為所有節點都彼此相鄰，完全圖 $K_n$ 的點連通性 $\kappa(K_n)=n-1$，且 $G-S$ 只會剩下一個節點。可以推出，若一張圖 $G=(V, E)$ 不是完全圖，則 $\kappa(G)\leq |V|-2$。可以自己比較看看以下兩張圖的點連通性分別為何

<center class = "half">
<img src="https://hackmd.io/_uploads/BJks01j21g.png" style="width: 307px">
<img src="https://hackmd.io/_uploads/SkLAAJihJe.png" style="width: 300px">
</center>

## 邊割與分割集 Edge Cut and Disconnecting Set
### 定義
- 在一張圖 $G$ 中，若存在集合 $F\subseteq E(G)$ 使 $G-F$ 有多於一個連通塊，則 $F$ 是一個**分割集 (disconnecting set)**
- 給定 $S, T\subseteq V(G)$，$[S, T]$ 為一個兩終點分別在 $S$ 與 $T$ 的邊集合
- **邊割 (edge cut)** 是一個邊集，寫作 $[S, \bar{S}]$。其中， $S\subset V(G)$ 且 $\bar{S}=V(G)-S$
- 若 $F$ 為邊集合，$\kappa'(x, y)$ 為最小 $F$ 的元素個數，使 $G-F$ 沒有路徑可以從 $x$ 到 $y$

### 舉例
如下左圖紅邊為分割集，右圖為邊割

<center class = "half">
<img src="https://hackmd.io/_uploads/SyMj9go3Jg.png" style="width: 300px">
<img src="https://hackmd.io/_uploads/Ske7oli2kl.png" style="width: 302px">
</center>

### 分割集 vs 邊割
所有邊割必為分割集，但分割集不必然是邊割。僅極小 (minimal) 的分割集是割邊

## 邊連通性 Edge Connectivity
### 定義
一張圖 $G$ 的邊連通性寫作 $\kappa'(G)$，為最小分割集的元素個數。若一張圖是 $k$-邊連通，則每個分割集都需要至少有 $k$ 條邊

可以將邊連通性寫作 $\kappa'(G)=min_{x, y\in V(G)}~\kappa'(x, y)$

## $\kappa\leq\kappa'\leq\delta$
### 定理 (Whitney[1932])
若 $G=(V, E)$ 是一個 simple graph，則 $\kappa(G)\leq\kappa'(G)\leq\delta(G)$。其中，$\delta(G)$ 為 $G$ 中度數 (degree) 最少的節點度數

### 證明
$\kappa'(G)\leq\delta(G)$ : 我們可以刪去度數最小的節點相連的所有邊來找到 $\kappa'(G)$ 的上限
$\kappa(G)\leq\kappa'(G)$ : 根據點連通性的例子，可以得到 $\kappa(G)\leq |V|-1$。考慮一個邊割 $[S, \bar{S}]$，若所有 $S$ 中的節點都與所有 $\bar{S}$ 中的節點都相鄰，則 $|[S, \bar{S}]|=|S||\bar{S}| \geq |V| - 1\geq \kappa(G)$ 滿足度等式。若所有 $S$ 中的節點並沒有與所有 $\bar{S}$ 中的節點都相鄰，我們可以來找找看不相鄰的兩點 $x\in S$ 與 $y\in \bar{S}$。令 $T$ 裡裝著所有 $x$ 在 $\bar{S}$ 的鄰居以及所有 $S-{x}$ 且在 $\bar{S}$ 有鄰居的節點。可以觀察出 $T$ 是一個點割。我們可以再挑從 $x$ 到 $T\cap\bar{S}$ 的邊與每個 $T\cap S$ 中的節點任選一條到 $\bar{S}$ ，如此一來就會有 $|T|$ 條不同的邊在 $[S, \bar{S}]$ 中。因此 $\kappa'(G)=|[S, \bar{S}]|\geq|T|\geq\kappa(G)$

<img src="https://hackmd.io/_uploads/H10t8Zj3kx.png" style="margin: 0 auto; display: block; width: 450px">

### 3-regular 特例
若 $G$ 是 3-regular，即 $G$ 中所有節點 $v$ 的度數皆為 $3$，則 $\kappa(G)=\kappa'(G)$。這是一個顯然的例子，也很好證。這裡就交給讀者自己找找看是否有反例存在

<img src="https://hackmd.io/_uploads/S1B6Cs5h1g.png" style="margin: 0 auto; display: block; width: 500px">

$~$
如上圖，若是要把 $x,y$ 切開來，可以選擇刪除 $3$ 個點 $a, b, c$，也可以選擇刪除 $3$ 條邊 $xa, xb, xc$，使 $x$ 孤立。當然也有其他選擇，但刪去的邊數與點數皆會保持相同

## Menger 定理
Menger 定理主要可以拆成兩部分，在此以定理 $1$ 與定理 $2$ 來分別說明
### 內部不相交路徑 Internally Disjoint Paths
- 若兩條從 $x$ 到 $y$ 的路徑裡面並沒有共用的節點，則稱為內部不相交路徑
- $x, y$ 的最大內部不相交路徑數量寫作 $\lambda(x, y)$
- 若兩條從 $x$ 到 $y$ 的路徑裡面並沒有共用邊，則稱為內部不相交邊路徑
- $x, y$ 的最大內部不相交邊路徑數量寫作 $\lambda'(x, y)$

### 定理 1 (Menger[1927])
若 $x,y\in V(G)$ 且 $xy \notin E(G)$，則 $\kappa(x, y)=\lambda(x, y)$

### 證明定理 1
透過觀察，我們不難發現，由於內部不相交路徑中彼此節點不共用，因此 $\kappa(x, y)\geq\lambda(x, y)$。為了證明等式，我們對 $n(G)$ 使用歸納法
- Basis step : $n(G) = 2$，因 $xy \notin E(G)$，$\kappa(x, y)=\lambda(x, y)=0$
- Induction step : $n(G) > 2$。令 $k=\kappa_G(x, y)$。我們可以建構出 $k$ 條內部不相交路徑，以下將拆成兩個狀況來討論

#### Case 1 : 最小 $x, y$-cut 的節點至少有一個不是 $N(x)$ 或 $N(y)$ 的節點
為了建出 $k$ 條路徑 (根據歸納假設)，我們可以建構出下圖，其中 $V_1$ 是 $x,S$-路徑上的節點，$V_2$ 是 $S, y$ 路徑上的節點

我們可以證明 $S=V_1\cap V_2$，因為 $S$ 上的節點都會在路徑上，所以 $S\subseteq V_1\cap V_2$。若存在 $v\in (V_1\cap V_2)-S$，則存在一條路徑包含 $v$ 的同時又迴避 $S$，顯然這是不可能的，因此 $S=V_1\cap V_2$ 得證。相同地，$V_1$ 忽略 $N(y)-S$，且 $V_2$ 忽略 $N(x)-S$

<img src="https://hackmd.io/_uploads/S18Qh3s2yx.png" style="margin: 0 auto; display: block; width: 450px">

$~$
接下來我們把圖拆成 $H_1, H_2$ 兩張圖，使 $V_1$ 的所有節點放入 $H_1$，使 $V_2$ 的所有節點放入 $H_2$，並在 $H_1$ 的 $S$ 連上 $y'$、$H_2$ 的 $S$ 連上 $x'$。因 $y'$ 與 $S$ 直接相連，$\kappa_{H_1}(x, y')=k$。相同地在 $H_2$ 中，$\kappa_{H_2}(x', y)=k$

<img src="https://hackmd.io/_uploads/BJ-XWashyl.png" style="margin: 0 auto; display: block; width: 600px">

$~$
因 $V_1$ 忽略 $N(y)-S$，且 $V_2$ 忽略 $N(x)-S$，$H_1$ 跟 $H_2$ 與相似於 $G$。因此歸納假設可以推出 $\kappa_{H_1}(x, y')=k=\kappa_{H_2}(x', y)$。我們將 $x', y'$ 刪除之後接起來變成原來的圖 $G$，就可以知道 $G$ 有 $k$ 條內部不相交路徑

#### Case 2 : 最小 $x, y$-cut 的節點都是 $N(x)$ 或 $N(y)$ 的節點
我們一樣使用建構法建出 $k$ 條路徑。由於並非所有圖都是類似二分圖的樣子，因此以下的 1. 與 2. 可以將圖處理成 3. 的狀況，也就是類似二分圖的模樣
1. 若有一節點 $v\notin \{x\}\cup N(x)\cup N(y)\cup \{y\}$，則 $\kappa_{G-v}(x, y)=k$，如此一來就可以得到歸納假設中的 $x, y$-路徑
2. 若存在 $u\in N(x)\cap N(y)$，則 $u$ 必會出現在每條 $x, y$-路徑中，將其刪掉會得到 $\kappa_{G-u}(x, y)=k-1$。如此一來就可以得到歸納假設中對於 $G-v$ 有 $k-1$ 條 $x, y$-路徑
3. 若 $N(x)$ 與 $N(y)$ 會把 $G-\{x, y\}$ 切成兩份，令 $G'$ 為 $N(x), N(y)$ 的二分圖，其中邊集合就是邊割 $[N(x), N(y)]$。如此一來， $G$ 中的 $x, y$ 點割就是 $G'$ 的點覆蓋。根據 [Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)，最大匹配數等於最小點覆蓋數，因此我們可以得到 $k$ 條長度為 $3$ 的內部不相交路徑，符合歸納假設

<img src="https://hackmd.io/_uploads/r1Efs6s3yx.png" style="margin: 0 auto; display: block; width: 400px">

$~$
註 : 以上圖的實線皆為內部不相交路徑

### 線圖 Line Graph
一張圖 $G$ 的線圖寫作 $L(G)$，其中在 $G$ 中的所有邊都是 $L(G)$ 中的節點
如下圖，$e, f\in E(G)$，$e, f\in V(L(G))$

<img src="https://hackmd.io/_uploads/ByRSCpj3Jg.png" style="margin: 0 auto; display: block; width: 550px">

$~$
註 : 此定義在有向圖也適用

### 定理 2 (Ford and Fulkerson[1956])
若 $x, y$ 為 $G$ 中不同的節點，則 $\kappa'(x, y)=\lambda'(x, y)$

### 證明定理 2
將圖 $G$ 加上兩節點 $s, t$ 與邊 $sx, yt$ 形成新的圖 $G'$，這樣不影響 $\kappa'(x, y)$ 與 $\lambda'(x, y)$ 的答案。接下來我們變個魔法把 $G$ 轉化為線圖 $L(G)$，則 $\kappa_G'(x, y)=\kappa_{L(G')}(sx, ty)$，且 $\lambda_G'(x, y)=\lambda_{L(G')}(sx, yt)$。根據 Menger 定理的定理 1，可得 $\kappa_G'(x, y)=\kappa_{L(G')}(sx, ty)=\lambda_{L(G')}(sx, yt)=\lambda_G'(x, y)$

## Hall 定理轉換成 Menger 定理
其實 Menger 定理與 Hall 定理邏輯等價，兩者可以互相推出來。這邊就示範如何使用 Hall 定理轉換成 Menger 定理
### Hall 定理
$X, Y$-二分圖中有一匹配使 $X$ 的節點都能被匹配，若且唯若對於所有 $S\subseteq X$，$|N(S)| \geq |S|$

### 定理 : Hall 定理轉換成 Menger 定理
設 $X, Y$-二分圖 $G$。我們可以再加上兩個特別的節點 $a, b$，並將 $a$ 與 $X$ 的所有節點建邊，$b$ 與 $Y$ 的所有節點建邊，如此一來就形成了另一張圖 $G'$

令 $k=|X|$，我們可以宣稱，所有 $a, b$-cut 都最少有 $k$ 個節點。設 $S=A\cup B$ 是一個 $a, b$-cut，$A\subset X$，$B\subset Y$。因 $S$ 是一個點割，沒有有一條邊能連接 $X-A$ 的節點與 $Y-B$ 的節點，且 $N(X-A)\subseteq B$。根據 Hall 定理，可以得到 $|X-A|\leq|N(X-A)|\leq |B|$。所以推得 $|S|=|A|+|B|\geq |A|+|X−A|=|X|=k$，而所得到的 $G'$ 就是 Menger 定理的圖

<img src="https://hackmd.io/_uploads/Skg0J_qo21e.png" style="margin: 0 auto; display: block; width: 500px">

$~$
註 : $N(X-A)$ 是指 $X-A$ 的鄰居集合

## 為什麼 Menger 定理很重要 ?
1. Menger 定理的效力等價於 [Hall 定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)，因此 Menger 定理也可以[證出 Kőnig-Egerváry 定理](https://hackmd.io/@ShanC/konig-theorem)
2. Menger 定理可以證出最大流-最小割定理，最大流-最小割定理也可以證出 Menger 定理
3. 最大流-最小割定理可以證出 [Kőnig-Egerváry 定理](https://hackmd.io/@ShanC/konig-theorem)

以上三點意味著，二分圖中最大匹配問題、最小點覆蓋問題、最大獨立集問題、最小邊覆蓋問題、最小邊/點割問題、最大互斥邊/點路徑問題與最大流量問題都可以互相轉換。除此之外，許多相關的問題也都是可以互相轉換的，~~這或許也是為什麼競程中的 flow 題會那麼難看出來的原因~~

## 備註
- Menger 定理的證明有超過 $15$ 個版本
- Menger 定理的最初版本其實有些瑕疵，最後是被 Kőnig 修正

----

## 參考資料

- D.B.West - Introduction to Graph Theory 2/e
- [Hall's marriage theorem - Wikipedia](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem)
- [Howard Wang - 圖形理論](https://hackmd.io/@HowWang/rkts6dUMo#Ch4-Connectivity-and-Paths)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/3/23