明蒂定理

明蒂定理(Minty theorem)是反映图的内在基本组合结构的一个定理。若对于有向图D的弧以黑、绿、红三色着色，其中一弧a指定着黑色，其他弧任意着色，则至少以下两情况之一必发生：或者存在一个包含a弧的由黑、红两色弧组成的圈C，且C上的黑色弧方向相同；或者存在一个包含a弧由黑、绿两色弧组成的上圈B，且B上黑色弧方向相同，这就是明蒂定理。明蒂定理在最大流最小割理论中有用，若对于无向图的明蒂定理为：对于无向图G的边以黑、绿、红三色任意着色，其中只有一边指定着黑色，则至少以下两情况之一必然发生：或者有一个只有黑、红两色边组成的圈；或者有一个只有黑、绿两色边组成的上圈，这个定理可推广到拟阵上。