連通性與 Menger 定理

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

本篇會來介紹點割 (vertex cut)、邊割 (edge cut) 與連通性 (connectivity)。最後會來介紹 Menger 定理，說明點割、邊割與路徑乃至於整張圖的關係。Menger 定理在圖論是個極為重要的存在，因為它的效力與許多不同的定理等價，像是 Hall 定理、 Kőnig 定理等都能使用 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$

點連通性 Vertex Connectivity

定義

一張圖

$G$ 的點連通性寫作

$\kappa (G)$，為一張圖中最小

$S$ 的元素個數，使

$G-S$ 不連通或只剩一個節點。若一張圖是的點連通性最少為

$k$，則稱圖是

$k$-connected

可以將點連通性寫作

$\kappa (G)=mi{n}_{x,y\in V(G)}\kappa (x,y)$

舉例

$K_n$ 的點連通性

不難看出，因為所有節點都彼此相鄰，完全圖

$K_n$ 的點連通性

$\kappa (K_n)=n-1$，且

$G-S$ 只會剩下一個節點。可以推出，若一張圖

$G=(V,E)$ 不是完全圖，則

$\kappa (G)\le |V|-2$。可以自己比較看看以下兩張圖的點連通性分別為何

邊割與分割集 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,\overline{S}]$。其中，
  $S\subset V(G)$ 且
  $\overline{S}=V(G)-S$
• 若
  $F$ 為邊集合，
  ${\kappa }^{\prime }(x,y)$ 為最小
  $F$ 的元素個數，使
  $G-F$ 沒有路徑可以從
  $x$ 到
  $y$

舉例

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

分割集 vs 邊割

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

邊連通性 Edge Connectivity

定義

一張圖

$G$ 的邊連通性寫作

${\kappa }^{\prime }(G)$，為最小分割集的元素個數。若一張圖是

$k$-邊連通，則每個分割集都需要至少有

$k$ 條邊

可以將邊連通性寫作

${\kappa }^{\prime }(G)=mi{n}_{x,y\in V(G)}{\kappa }^{\prime }(x,y)$

$\kappa \le {\kappa }^{\prime }\le \delta$

定理 (Whitney[1932])

若

$G=(V,E)$ 是一個 simple graph，則

$\kappa (G)\le {\kappa }^{\prime }(G)\le \delta (G)$。其中，

$\delta (G)$ 為

$G$ 中度數 (degree) 最少的節點度數

證明

${\kappa }^{\prime }(G)\le \delta (G)$ : 我們可以刪去度數最小的節點相連的所有邊來找到

${\kappa }^{\prime }(G)$ 的上限

$\kappa (G)\le {\kappa }^{\prime }(G)$ : 根據點連通性的例子，可以得到

$\kappa (G)\le |V|-1$。考慮一個邊割

$[S,\overline{S}]$，若所有

$S$ 中的節點都與所有

$\overline{S}$ 中的節點都相鄰，則

$|[S,\overline{S}]|=|S||\overline{S}|\ge |V|-1\ge \kappa (G)$ 滿足度等式。若所有

$S$ 中的節點並沒有與所有

$\overline{S}$ 中的節點都相鄰，我們可以來找找看不相鄰的兩點

$x\in S$ 與

$y\in \overline{S}$。令

$T$ 裡裝著所有

$x$ 在

$\overline{S}$ 的鄰居以及所有

$S-x$ 且在

$\overline{S}$ 有鄰居的節點。可以觀察出

$T$ 是一個點割。我們可以再挑從

$x$ 到

$T\cap \overline{S}$ 的邊與每個

$T\cap S$ 中的節點任選一條到

$\overline{S}$ ，如此一來就會有

$|T|$ 條不同的邊在

$[S,\overline{S}]$ 中。因此

${\kappa }^{\prime }(G)=|[S,\overline{S}]|\ge |T|\ge \kappa (G)$

3-regular 特例

若

$G$ 是 3-regular，即

$G$ 中所有節點

$v$ 的度數皆為

$3$，則

$\kappa (G)={\kappa }^{\prime }(G)$。這是一個顯然的例子，也很好證。這裡就交給讀者自己找找看是否有反例存在

$$
如上圖，若是要把

$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 }^{\prime }(x,y)$

定理 1 (Menger[1927])

若

$x,y\in V(G)$ 且

$xy\notin E(G)$，則

$\kappa (x,y)=\lambda (x,y)$

證明定理 1

透過觀察，我們不難發現，由於內部不相交路徑中彼此節點不共用，因此

$\kappa (x,y)\ge \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$

$$
接下來我們把圖拆成

$H_1,H_2$ 兩張圖，使

$V_1$ 的所有節點放入

$H_1$，使

$V_2$ 的所有節點放入

$H_2$，並在

$H_1$ 的

$S$ 連上

$y^{\prime }$、

$H_2$ 的

$S$ 連上

$x^{\prime }$。因

$y^{\prime }$ 與

$S$ 直接相連，

${\kappa }_{H_1}(x,y^{\prime })=k$。相同地在

$H_2$ 中，

${\kappa }_{H_2}(x^{\prime },y)=k$

$$
因

$V_1$ 忽略

$N(y)-S$，且

$V_2$ 忽略

$N(x)-S$，

$H_1$ 跟

$H_2$ 與相似於

$G$。因此歸納假設可以推出

${\kappa }_{H_1}(x,y^{\prime })=k={\kappa }_{H_2}(x^{\prime },y)$。我們將

$x^{\prime },y^{\prime }$ 刪除之後接起來變成原來的圖

$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^{\prime }$ 為
   $N(x),N(y)$ 的二分圖，其中邊集合就是邊割
   $[N(x),N(y)]$。如此一來，
   $G$ 中的
   $x,y$ 點割就是
   $G^{\prime }$ 的點覆蓋。根據 Kőnig 定理，最大匹配數等於最小點覆蓋數，因此我們可以得到
   $k$ 條長度為
   $3$ 的內部不相交路徑，符合歸納假設

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

線圖 Line Graph

一張圖

$G$ 的線圖寫作

$L(G)$，其中在

$G$ 中的所有邊都是

$L(G)$ 中的節點
如下圖，

$e,f\in E(G)$，

$e,f\in V(L(G))$

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

定理 2 (Ford and Fulkerson[1956])

若

$x,y$ 為

$G$ 中不同的節點，則

${\kappa }^{\prime }(x,y)={\lambda }^{\prime }(x,y)$

證明定理 2

將圖

$G$ 加上兩節點

$s,t$ 與邊

$sx,yt$ 形成新的圖

$G^{\prime }$，這樣不影響

${\kappa }^{\prime }(x,y)$ 與

${\lambda }^{\prime }(x,y)$ 的答案。接下來我們變個魔法把

$G$ 轉化為線圖

$L(G)$，則

${\kappa }_G^{\prime }(x,y)={\kappa }_{L(G^{\prime })}(sx,ty)$，且

${\lambda }_G^{\prime }(x,y)={\lambda }_{L(G^{\prime })}(sx,yt)$。根據 Menger 定理的定理 1，可得

${\kappa }_G^{\prime }(x,y)={\kappa }_{L(G^{\prime })}(sx,ty)={\lambda }_{L(G^{\prime })}(sx,yt)={\lambda }_G^{\prime }(x,y)$

Hall 定理轉換成 Menger 定理

其實 Menger 定理與 Hall 定理邏輯等價，兩者可以互相推出來。這邊就示範如何使用 Hall 定理轉換成 Menger 定理

Hall 定理

$X,Y$-二分圖中有一匹配使

$X$ 的節點都能被匹配，若且為若對於所有

$S\subseteq X$，

$|N(S)|\ge |S|$

定理 : Hall 定理轉換成 Menger 定理

設

$X,Y$-二分圖

$G$。我們可以再加上兩個特別的節點

$a,b$，並將

$a$ 與

$X$ 的所有節點建邊，

$b$ 與

$Y$ 的所有節點建邊，如此一來就形成了另一張圖

$G^{\prime }$

令

$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|\le |N(X-A)|\le |B|$。所以推得

$|S|=|A|+|B|\ge |A|+|X-A|=|X|=k$，而所得到的

$G^{\prime }$ 就是 Menger 定理的圖

$$
註 :

$N(X-A)$ 是指

$X-A$ 的鄰居集合

為什麼 Menger 定理很重要 ?

1. Menger 定理的效力等價於 Hall 定理，因此 Menger 定理也可以證出 Kőnig-Egerváry 定理
2. Menger 定理可以證出最大流-最小割定理，最大流-最小割定理也可以證出 Menger 定理
3. 最大流-最小割定理可以證出 Kőnig-Egerváry 定理

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

備註

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

---

參考資料

• D.B.West - Introduction to Graph Theory 2/e
• Hall's marriage theorem - Wikipedia
• Howard Wang - 圖形理論

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2025/3/23