門格爾定理

在圖論中，門格爾定理（英：Menger's Theorem）指在有限圖中，最小割集（英語：cut set）的大小等於任意在所有頂點對之間可以找到的不相交路徑的最大數量。這一定理的證明由卡爾·門格爾於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和${\displaystyle x,y\in V(G)}$，一個點集${\displaystyle S\subseteq V(G)}$，如果G-S中無x到y的路徑，則稱S是x,y-點割集。

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

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

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

證明

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

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

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

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

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

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

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

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

構造一個新的圖${\displaystyle H}$，使得${\displaystyle H_{1}}$是G的${\displaystyle V_{1}}$-導出子圖再加上一個新的點y′，使得y′與S中所有點相連。因為G中每一條x,y-路徑都從x開始經過S，所以H中的x,y′-點割集也是G中的x,y-點割集。又因為S是H的x,y′-點割集，所以${\displaystyle \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)。

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

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

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

參見

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

參考文獻

1. West, Douglas Brent. Introduction to Graph Theory (PDF) 2. 1996: 167–168 [2020-12-23]. （原始內容存檔 (PDF)於2020-11-11）.
2. Menger, Karl. Zur allgemeinen Kurventheorie. Fund. Math. 1927, 10: 96–115.

延伸閱讀

• 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^{[永久失效連結]}