茶年 · 中文维基百科

门格尔定理

Wikipedia · 2026-07-31 维基百科 👁 1 阅读

在图论中，门格尔定理（）指在有限图中，最小的大小等于任意在所有顶点对之间可以找到的不相交路径的最大数量。这一定理的证明由卡尔·门格尔于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\lambda(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}\cap V_{2}。反过来，任意v\in V_{1}\cap V_{2}，必有v\in S，否则x, y在G-S中通过v连通。因此，S=V_{1}\cap V_{2}。

构造一个新的图H，使得H_{1}是G的V_{1}-导出子图再加上一个新的点y′，并且将这个新的点y′与S中所有点相连。因为G中每一条x, y-路径都从x开始经过S，所以H中的x, y′-点割集也是G中的x, y-点割集，所以\kappa_{H}(x, y')\geq k。又因为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, y\}\cup N(x)\cup N(y))，那么v不在G的任意一个最小x, y-点割集中，所以G的最小x, y-点割集是G-v的点割集且不能更小，因此\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)，根据，G′的最小点覆盖等于最大匹配。因此G′包含一个大小为k的匹配，即找到了G中k条内部不相交的x, y-路径。证毕。

参见

  • Gammoid

*k-顶点连通图
*k-边连通图

参考文献
延伸阅读
*
*
*

外部链接

#图论定理

评论 (0)

  • 还没有评论，来抢沙发吧。