门格尔定理

在圖論中，**門格爾定理（英：Menger's Theorem）** 指在有限圖中，最小割集的大小等於任意在所有頂點對之間可以找到的不相交路徑的最大數量。這一定理的證明由卡爾・門格爾於 1927 年發表。這被認為是圖論中最重要且經典的定理之一。該定理刻畫了連通性的性質，增加了邊的權重可推廣成最大流量小割定理，而最大流量小割定理是線性規劃的強對偶性定理的直接推論。

## 邊連通度

門格爾定理的邊連通度版本敘述為：

> 設 G 是個有限簡單圖，x 和 y 是其中兩個不相鄰的頂點。則 x 和 y 之間的最小邊割集元素個數等於從 x 到 y 兩兩邊獨立的路徑的最多個數。其中一個 x 和 y 之間的邊割集是一些邊的集合，使得 G 扣除這些邊會使 x 和 y 不連通。
> 延伸至所有點對：G 是 k - 邊連通若且唯若 G 中任兩點之間都可以找到 k 條兩兩邊獨立的路徑。
> 
> 

## 點連通度

門格爾定理的點連通度版本敘述為：

> 設 G 是個有限簡單圖，x 和 y 是其中兩個不同的頂點。則 x 和 y 之間的最小點割集元素個數等於從 x 到 y 兩兩端點外點獨立的路徑的最多個數。其中一個 x 和 y 之間的點割集是蒐集一些點，使得 G 扣除這些點會使 x 和 y 不連通。
> 延伸至所有點對：G 是 k - 連通若且唯若 G 中任兩點之間都可以找到 k 條兩兩端點外點獨立的路徑。
> 
> 

## 有限有向圖

上述兩版本對於 G 是有向有向圖的情況仍然成立，唯獨路徑將修改成有向路徑。

## 定義

**x,y - 點割集**(x,y-separator or x,y-cut)：給定一個圖 _G_ 和 $x,y\in V(G)$ ，一個點集 $S\subseteq V(G)$ ，如果 G-S 中無 x 到 y 的路徑，則稱 S 是 x,y - 點割集。

**x,y - 邊割集**(x,y-edge-separator or x,y-edge-cut)：給定一個圖 _G_ 和 $x,y\in V(G)$ ，一個邊集 $S\subseteq E(G)$ ，如果 G-S 中無 x 到 y 的路徑，則稱 S 是 x,y - 邊割集。

**X,Y - 路徑**(X,Y-Path)：給定一個圖 _G_ 和兩個點集 $X,Y\subseteq V(G)$ ，X,Y - 路徑是指一條起點在 X 中，終點在 Y 中，中間點均不在 $X\cup Y$ 中的路徑。

**內部不相交路徑**(internally disjoint path) 是指除端點外其他點互不相交的路徑。

## 證明

下面我們給出門格爾定理的一個歸納證明。

**門格爾定理**：如果 x,y 是圖 _G_ 的兩個頂點，且 $xy\notin E(G)$ ，那麼最小 x,y - 點割集的大小等於內部不相交的 x,y - 路徑的條數。

證明：記最小 x,y - 點割集的大小為 $\kappa (x,y)$ ，內部不相交的 x,y - 路徑的條數為 $\lambda (x,y)$ 。

因為 x,y - 點割集必須包含任意一條 x,y - 路徑上的一點，而共有 $\lambda (x,y)$ 條內部不相交的 x,y - 路徑，所以 $\kappa (x,y)\geq \kappa (x,y)$ 。下面我們證明二者相等。

我們對圖的階數進行歸納。當 n (G)=2，因為 $xy\notin E(G)$ ，所以 $\kappa (x,y)=\lambda (x,y)=0$ ，成立。

令 $k=\kappa (x,y)$ ，我們下面證明可以找到 k 條內部不相交的 x,y - 路徑。

情況 1：當 _G_ 有一個最小 x,y - 點割集 S，S 既不是 N (x) 也不是 N (y)，其中 N (x)，N (y) 分別是 x 和 y 的鄰點。

令 $V_{1}$ 為所有 x,S - 路徑上的點， $V_{2}$ 為所有 S,y - 路徑上的點。根據 S 的最小性，任意 $v\in S$ ，都有一條 x,y - 路徑 xPy 經過 v，且 $P\cap S=v$ ，因此 $v\in V_{1}\cup V_{2}$ 。反過來，任意 $v\in V_{1}\cup V_{2}$ ，必有 $v\in S$ ，否則 x,y 在 G-S 中通過 v 連通。因此， $S=V_{1}\cup V_{2}$ 。

構造一個新的圖 $H$ ，使得 $H_{1}$ 是 G 的 $V_{1}$ - 導出子圖再加上一個新的點 y′，使得 y′與 S 中所有點相連。因為 G 中每一條 x,y - 路徑都從 x 開始經過 S，所以 H 中的 x,y′- 點割集也是 G 中的 x,y - 點割集。又因為 S 是 H 的 x,y′- 點割集，所以 $\kappa _{H}(x,y)=k$ 。又因為 | N (y)-S|>0，所以 H 比 G 的階數小，根據歸納假設，H 中有 k 條內部不相交的 x,y′- 路徑，即 G 中有 k 條內部不相交的 x,S - 路徑。同理，G 中有 k 條內部不相交的 S,y - 路徑，把它們合起來得到 k 條內部互不相交的 x,y - 路徑。

情況 2：_G_ 的最小 x,y - 點割集不是 N (x) 就是 N (y)。

如果存在一點 $v\in G\backslash \{x\cup y\cup N(x)\cup N(y)\}$ ，那麼 v 不在 G 的任意一個最小 x,y - 點割集中，因此 $\kappa _{G-v}(x,y)=k$ 。根據歸納假設，可以在 G-v 中找到 k 條內部不相交的 x,y - 路徑，它們也是 G 中 k 條內部不相交的 x,y - 路徑。

如果存在一點 $u\in N(x)\cap N(y)$ ，那麼 $\kappa _{G-u}(x,y)=k-1$ 。根據歸納假設，可以在 G-u 中找到 k-1 條內部不相交的 x,y - 路徑，再加上 xuy，得到 G 中 k 條內部不相交的 x,y - 路徑。

否則，N (x) 和 N (y) 是 $V(G)-\{x,y\}$ 的一個分劃（partition）。令 G′是由 N (x) 和 N (y) 以及它們之間的邊 [N (x),N (y)] 構成的二部圖。x,y - 點割集實際上對應了一個 G′中的點覆蓋 (vertex cover)，根據 Kőnig 定理，G′的最小點覆蓋等於最大匹配。因此 G′包含一個大小為 k 的匹配，即找到了 G 中 k 條內部不相交的 x,y - 路徑。證畢。

## 參見

* Gammoid
* k - 頂點連通圖
* k - 邊連通圖

## 參考文獻

## 延伸閱讀

* Menger, Karl. Zur allgemeinen Kurventheorie. Fund. Math. 1927, **10**: 96–115.
* Aharoni, Ron; Berger, Eli. Menger's theorem for infinite graphs. Inventiones mathematicae. 2008, **176**: 1. Bibcode:2009InMat.176....1A. arXiv:math/0509397 . doi:10.1007/s00222-008-0157-3.
* Halin, R. A note on Menger's theorem for infinite locally finite graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 1974, **40**: 111. doi:10.1007/BF02993589.

## 外部連結

* 門格爾定理的證明 （頁面存檔備份，存於網際網路檔案館）
* 門格爾定理，並最大流最小割定理 （頁面存檔備份，存於網際網路檔案館）
* 網絡流程
* Max Flow Min Cut