查看“︁门格尔定理”︁的源代码

{{expand language|1=en|page=Menger's theorem|time=2019-04-23T16:51:09+00:00}}
在[[图论]]中，'''门格尔定理（英：Menger's Theorem）'''指在[[图 (数学)|有限图]]中，最小{{Tsl|en|cut set|割集}}的大小等于任意在所有[[顶点 (图论)|顶点]]对之间可以找到的不相交[[路径]]的最大数量。这一定理的证明由[[卡尔·门格尔 (数学家)|卡尔·门格尔]]于1927年发表。这被认为是图论中最重要且经典的定理之一。该定理刻畫了[[连通图|连通性]]的性质，增加了邊的權重可推廣成[[最大流最小割定理|最大流量小割定理]]，而[[最大流最小割定理|最大流量小割定理]]是線性規劃的[[线性规划#对偶|强对偶性定理]]的直接推論。

== 邊連通度 ==
門格爾定理的邊連通度版本敘述為：<blockquote>設 G 是個有限簡單圖，x 和 y 是其中兩個不相鄰的頂點。則 x 和 y 之間的最小邊割集元素個數等於從 x 到 y 兩兩邊獨立的路徑的最多個數。其中一個 x 和 y 之間的邊割集是一些邊的集合，使得 G 扣除這些邊會使 x 和 y 不連通。

延伸至所有點對：G 是 [[圖論術語#连通图／连通性|k-邊連通]]若且唯若 G 中任兩點之間都可以找到 k 條兩兩邊獨立的路徑。</blockquote>

== 點連通度 ==
門格爾定理的點連通度版本敘述為：<blockquote>設 G 是個有限簡單圖，x 和 y 是其中兩個不同的頂點。則 x 和 y 之間的最小點割集元素個數等於從 x 到 y 兩兩端點外點獨立的路徑的最多個數。其中一個 x 和 y 之間的點割集是蒐集一些點，使得 G 扣除這些點會使 x 和 y 不連通。

延伸至所有點對：G 是 [[圖論術語#连通图／连通性|k-連通]]若且唯若 G 中任兩點之間都可以找到 k 條兩兩端點外點獨立的路徑。</blockquote>

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

==定义==
'''x,y-点割集'''(x,y-separator or x,y-cut)：给定一个图''G''和<math>x,y\in V(G)</math>，一个点集<math>S\subseteq V(G)</math>，如果G-S中无x到y的路径，则称S是x,y-点割集。

'''x,y-边割集'''(x,y-edge-separator or x,y-edge-cut)：给定一个图''G''和<math>x,y\in V(G)</math>，一个边集<math>S\subseteq E(G)</math>，如果G-S中无x到y的路径，则称S是x,y-边割集。

'''X,Y-路径'''(X,Y-Path)：给定一个图''G''和两个点集<math>X,Y\subseteq V(G)</math>，X,Y-路径是指一条起点在X中，终点在Y中，中间点均不在<math>X\cup Y</math>中的路径。

'''内部不相交路径'''(internally disjoint path)是指除端点外其他点互不相交的路径。
==证明==
下面我们给出门格尔定理的一个归纳证明。<ref>{{cite book |author1=West, Douglas Brent |title=Introduction to Graph Theory |date=1996 |pages=167-168 |edition=2 |url=http://docshare01.docshare.tips/files/26167/261678089.pdf |access-date=2020-12-23 |archive-date=2020-11-11 |archive-url=https://web.archive.org/web/20201111210023/http://docshare01.docshare.tips/files/26167/261678089.pdf |dead-url=no }}</ref>

'''门格尔定理'''<ref>{{cite journal
  | author = Menger, Karl
  | title = Zur allgemeinen Kurventheorie
  | journal = Fund. Math.
  | volume = 10
  | pages = 96–115
  | year = 1927}}</ref>：如果x,y是图''G''的两个顶点，且<math>xy\notin E(G)</math>，那么最小x,y-点割集的大小等于内部不相交的x,y-路径的条数。

证明：记最小x,y-点割集的大小为<math>\kappa(x,y)</math>，内部不相交的x,y-路径的条数为<math>\lambda(x,y)</math>。

因为x,y-点割集必须包含任意一条x,y-路径上的一点，而共有<math>\lambda(x,y)</math>条内部不相交的x,y-路径，所以<math>\kappa(x,y)\geq\kappa(x,y)</math>。下面我们证明二者相等。

我们对图的阶数进行归纳。当n(G)=2，因为<math>xy\notin E(G)</math>，所以<math>\kappa(x,y)=\lambda(x,y)=0</math>，成立。

令<math>k=\kappa(x,y)</math>，我们下面证明可以找到k条内部不相交的x,y-路径。

情况1：当''G''有一个最小x,y-点割集S，S既不是N(x)也不是N(y)，其中N(x)，N(y)分别是x和y的邻点。

令<math>V_{1}</math>为所有x,S-路径上的点，<math>V_{2}</math>为所有S,y-路径上的点。根据S的最小性，任意<math>v\in S</math>，都有一条x,y-路径xPy经过v，且<math>P\cap S=v</math>，因此<math>v\in V_{1}\cup V_{2}</math>。反过来，任意<math>v\in V_{1}\cup V_{2}</math>，必有<math>v\in S</math>，否则x,y在G-S中通过v连通。因此，<math>S=V_{1}\cup V_{2}</math>。

构造一个新的图<math>H</math>，使得<math>H_{1}</math>是G的<math>V_{1}</math>-[[导出子图]]再加上一个新的点y′，使得y′与S中所有点相连。因为G中每一条x,y-路径都从x开始经过S，所以H中的x,y′-点割集也是G中的x,y-点割集。又因为S是H的x,y′-点割集，所以<math>\kappa_{H}(x,y)=k</math>。又因为|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)。

如果存在一点<math>v\in G\backslash \{x\cup y\cup N(x)\cup N(y)\}</math>，那么v不在G的任意一个最小x,y-点割集中，因此<math>\kappa_{G-v}(x,y)=k</math>。根据归纳假设，可以在G-v中找到k条内部不相交的x,y-路径，它们也是G中k条内部不相交的x,y-路径。

如果存在一点<math>u\in N(x)\cap N(y)</math>，那么<math>\kappa_{G-u}(x,y)=k-1</math>。根据归纳假设，可以在G-u中找到k-1条内部不相交的x,y-路径，再加上xuy，得到G中k条内部不相交的x,y-路径。

否则，N(x)和N(y)是<math>V(G)-\{x,y\}</math>的一个分划（partition）。令G′是由N(x)和N(y)以及它们之间的边[N(x),N(y)]构成的[[二部图]]。x,y-点割集实际上对应了一个G′中的[[覆盖 (图论)|点覆盖]](vertex cover)，根据{{Translink|en|Kőnig's theorem (graph theory)|Kőnig定理}}，G′的最小点覆盖等于最大[[匹配 (图论)|匹配]]。因此G′包含一个大小为k的匹配，即找到了G中k条内部不相交的x,y-路径。证毕。

== 参见 ==
* [[Gammoid]]
*[[k-顶点连通图]]
*[[k-边连通图]]

== 参考文献 ==
<references group="" responsive="1"></references>

== 延伸阅读 ==
* {{Cite journal|title=Zur allgemeinen Kurventheorie|last=Menger, Karl|journal=Fund. Math.|year=1927|volume=10|pages=96–115}}
* {{Cite journal|title=Menger's theorem for infinite graphs|last=Aharoni|first=Ron|last2=Berger|first2=Eli|journal=Inventiones mathematicae|doi=10.1007/s00222-008-0157-3|year=2008|volume=176|pages=1|arxiv=math/0509397|bibcode=2009InMat.176....1A}}
* {{Cite journal|title=A note on Menger's theorem for infinite locally finite graphs|last=Halin|first=R.|journal=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg|doi=10.1007/BF02993589|year=1974|volume=40|pages=111}}

== 外部链接 ==
* [http://www.math.unm.edu/~loring/links/graph_s05/Menger.pdf 门格尔定理的证明] {{Wayback|url=http://www.math.unm.edu/~loring/links/graph_s05/Menger.pdf |date=20210507004622 }}
* [http://brain.math.fau.edu/locke/Menger.htm 门格尔定理，并最大流最小割定理] {{Wayback|url=http://brain.math.fau.edu/locke/Menger.htm |date=20160304161949 }}
* [http://gepard.bioinformatik.uni-saarland.de/teaching/ws-2008-09/bioinformatik-3/lectures/V12-NetworkFlow.pdf 网络流程]{{Dead link|date=2019年7月 |bot=InternetArchiveBot |fix-attempted=yes }}
* [http://gepard.bioinformatik.uni-saarland.de/teaching/ws-2008-09/bioinformatik-3/lectures/V13-MaxFlowMinCut.pdf Max Flow Min Cut]{{Dead link|date=2019年7月 |bot=InternetArchiveBot |fix-attempted=yes }}

[[Category:图论]]