门格尔定理

Template:Expand language 在图论中，门格尔定理（英：Menger's Theorem）指在有限图中，最小Template:Tsl的大小等于任意在所有顶点对之间可以找到的不相交路径的最大数量。这一定理的证明由卡尔·门格尔于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)\ge \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\mathrm{\setminus }\{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)，根据Template:Translink，G′的最小点覆盖等于最大匹配。因此G′包含一个大小为k的匹配，即找到了G中k条内部不相交的x,y-路径。证毕。

参见

• Gammoid
• k-顶点连通图
• k-边连通图

延伸阅读

• Template:Cite journal
• Template:Cite journal
• Template:Cite journal

外部链接

• 门格尔定理的证明 Template:Wayback
• 门格尔定理，并最大流最小割定理 Template:Wayback
• 网络流程Template:Dead link
• Max Flow Min CutTemplate:Dead link