A Vi-A V,V2) 中关于 M交 T=T(A) v2-T 匹配, 图8.18 由定理8.8可知U是Z中仅有的未被M饱和 的顶点集合,如图818所示。定理 8.13(科尼格定理)：在二分图G(V1,V2) 中, 有1(G)=0(G)。 证明：设M*是G的最大匹配, U是V1中关于 M*未饱和点集合。 又设Z表示与U中每一个顶点有关于M*交 错路相连的顶点集合, 因为M*是最大匹配， 所以G中不包含关于M*的增广路， 由定理8.8可知U是Z中仅有的未被M*饱和 的顶点集合, 如图 8.18 所示