安可林文章网新闻资讯
明蒂定理
明蒂定理(Minty theorem)是反映图的内在基本组合结构的一个定理。若对于有向图D的弧以黑、绿、红三色着色，其中一弧a指定着黑色，其他弧任意着色，则至少以下两情况之一必发生：或者存在一个包含a弧的由黑、红两色弧组成的圈C，且C上的黑色弧方向相同；或者存在一个包含a弧由黑、绿两色弧组成的上圈B，且B上黑色弧方向相同，这就是明蒂定理。明蒂定理在最大流最小割理论中有用，若对于无向图的明蒂定理为：对于无向图G的边以黑、绿、红三色任意着色，其中只有一边指定着黑色，则至少以下两情况之一必然发生：或者有一个只有黑、红两色边组成的圈；或者有一个只有黑、绿两色边组成的上圈，这个定理可推广到拟阵上。
基本介绍
- 中文名：明蒂定理
- 外文名：Minty theorem
- 别称：Minty定理
- 所属学科：数学
- 所属问题：组合学(图与超图)
基本介绍
定理1 (明蒂(Minty)定理，1960) 给定一个有向图
，用红、蓝、绿三种颜色给E中的弧染色，已知
是红色弧，则如下论断有且仅有一个成立：
(1)弧包含在一个圈C中，C是由红、蓝色弧构成的(简称红蓝圈)，并且C上所有的红色弧都属于C+(或都属于C-)，这里的C+(C-)表示给定C的一个定向后，由所有和定向同向(反向)的弧构成的集合；
(2)弧包含在一个反圈v(由
中的弧构成的集合)中，v是由红、绿色弧构成的(简称红绿反圈)，并且所有的红色弧都属于v+(或都属于v-)，这里的v+(v-)表示给定v的一个定向后，由所有和定向同向(反向)的弧构成的集合。
明蒂定理的证明
证明首先证明(1)和(2)不会同时成立。若不然，设
是(1)中的红蓝圈，
是(2)中的红绿反圈。不妨
设
，设
是路
上第一个不属于X的节点
，即
，这样的是存在的，以a表示C上以勘
和为端点的弧，因为
，故a必定是红色弧，由(1)知，
，这是矛盾的。
下面用反圈法构造性地证明(1)和(2)中一定有一个成立。
开始时令
，一般地，设已经有
。按照如下原则在
中选弧：选中的蓝色弧或
中的红色弧，这里表示中与的定向同向的弧的集合。把被选上的弧的端点放入
，得到
。重複这个过程，进行到某一阶段时必出现下列情况之一：(A)
；(B)
，而中无边可选。易见，情形(A)发生时，就得到了使论断(1)成立的红蓝圈C；情形(B)出现时，就得到了使论断(2)成立的反圈v，证毕。
相关结论
利用明蒂定理，我们还可以得到下述定理．
定理1 设D是连通有向图，则如下各结论等价：
(1)D是强连通图；
(2)D中每一条弧都在某一个有向圈中；
(3)D不含反迴路(即反圈
，所有的弧方向一致，从X到
)。
定理2 如果一个有向图是强连通的，那幺它的基础图一定是2-边连通图。
定理3 如果一个有向图中有一条长度为k的u-v链，那幺它一定有一条长度不超过k的u-v路。
下面的结论给出了一个有向图成为强连通图的充分必要条件。
定理4 有向图D是强连通图的充分必要条件是D含有一个封闭的支撑链。
一个包含所有有向边的封闭链称为一个欧拉迴路，而此时有向图为欧拉有向图。
定理5 非平凡连通有向图是欧拉有向图的充分必要条件是对于每一个节点x，
。
下面我们介绍罗宾斯定理(读者可以直接用归纳法进行证明)。
定理6 (罗宾斯定理，1939) 若且唯若非平凡连通图是2-边连通图时，它有一个强连通定向。