门格尔定理

在图论中，门格尔定理（英：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