Department of Computer Science and Technology,Nanjing University Hal定理 (2)存在V的一个真子集A',N(A'川 =A'.记B'=N(A'). 据归纳假设，存在A'到B'的完备匹配. 二部图H=G-A'-B'满足归纳假设条件 否则，存在CsV1-A'.N(C)K|C. ING(CUA)I INH(C)+B'<JCH+IB'=CH+IA'ICUA'L 矛盾. 据归纳假设，存在V1-A'到V2-B'的完备匹配. 合并上述两个匹配得到一个V到V,的完备匹配.得证 June 2016 11
June 2016 11 Department of Computer Science and Technology, Nanjing University Hall定理 (2)存在 V1的一个真子集A', |N(A')| =|A' |. 记B'= N(A'). 据归纳假设,存在A'到B' 的完备匹配. 二部图H=G-A'-B' 满足归纳假设条件. A' B' 否则, 存在C V1 -A'. |NH(C)|<|C|. |NG(CA')| |NH(C)|+|B'|<|C|+|B'|=|C|+|A'|= |CA'|. 矛盾. 据归纳假设,存在V1 -A'到V2 -B'的完备匹配. 合并上述两个匹配得到一个V1到V2的完备匹配. 得证
Department of Computer Science and Technology,Nanjing University Hall定理的推论 ·设二部图G是一个k-正则的(k≥1)，则G有完美匹配. 证明.不妨设G=<A,B,E>,kA=kB,所以A=BL, 下证G有A到B的完备匹配. 对任一S∈A,S与NS)之间总共有kS条边，而与 N(S)相关的边总共有kN(S)条边。 '.kS≤kNS)川 ∴.N(S)川≥ISI 根据Ha定理，G有A到B的完备匹配，因A=B, 该匹配是完美匹配。 June 2016 12
June 2016 12 Department of Computer Science and Technology, Nanjing University Hall定理的推论 设二部图G是一个k-正则的(k 1), 则G有完美匹配. 证明. 不妨设G= < A, B, E>,k |A| =k |B| , 所以|A| =|B|. 下证G有A到B的完备匹配. 对任一S A，S与N(S)之间总共有k|S| 条边，而与 N(S)相关的边总共有k|N(S)| 条边。 ∴ k|S| k|N(S)| ∴ |N(S)| |S| 根据Hall定理，G有A到B的完备匹配，因 |A| = |B|， 该匹配是完美匹配