Wikipedia上的论述实际上是Diestel书中的Corollary 3.3.5.,只是一个corollary,太坑爹了。正经的Menger’s Theorem是Diestel书中的Theorem 3.3.1.,证明羞愧地没有看懂……好在找到一个7页的插图版证明搞定了,顺便贴到Wikipedia上去了。

有一些文字上的细微之处需要搞清楚。书上Theorem 3.3.1.的disjoint A-B path中的disjoint是指完全不相交,包括端点也不能相同。A-B path的定义可以见那个7页的证明,注意“除起点和终点外中间不能有A或B中的点”这个要求。这样那个7页证明就容易懂了。而Corollary 3.3.5.中的independent a-b path是指从a到b的internally vertex-disjoint path,即除a, b外的中间节点不相交(不然最多只有一条了)。证明里的N(a)指顶点a的所有邻点,E(a)指顶点a的所有邻边,line graph of G(下称G’)中每个顶点对应G中一条边,G’中两个顶点相邻当且仅当G中对应的两条边相邻,这些都是在前面章节里给出的。Theorem 3.3.6.中的independent path与Corollary 3.3.5.中类似。

Menger’s Theorem可以弄出一些很漂亮的结论。比如说,下面两个命题是等价的:

  1. 图G中任意不相邻两点间的node-disjoint-path的个数大于等于k;
  2. 图G中任意两点间的node-disjoint-path的个数大于等于k。

2到1是显然的。1到2可以这么证:如果1成立,那么图G一定是(k-1)个点不可分割的,即最小分割点集的元素个数大于等于k。根据Menger’s Theorem,任意两点间的node-disjoint-path的个数都大于等于k。

再比如,下面4个命题是等价的:

  1. 图G中任意不相邻两点间的node-disjoint-path的个数大于等于2;
  2. 图G中无割点;
  3. 图G中任意两条边共环;
  4. 图G中任意两点间的node-disjoint-path的个数大于等于2。

由上面的分析知,1和4是等价的(取k=2)。而1到2,3到2是显然的。3到1也好证。2到4可以用Menger’s Theorem,这样2和1也等价了。还剩一个2到3,我们不妨证NOT 3到NOT 2。证明如下:

因为边共环是一个等价类,若图G中有两边不共环,必然可以找到顶点v, a, b使得边va和vb不共环。那么所有a, b之间的路都经过v。所以v就是个割点。

Menger’s Theorem果然是个神奇的对偶定理。

BTW,Diestel真是个好人,居然提供了最新版的全书pdf下载,说是low-quality,其实也不错了。只是不能搜索,找前面的定义费劲了。

Links: