最大匹配与最小边覆盖 定理3.(定理的描述内容见上页) 证明:由“M为最大匹配”可知,M=B1于是G中含有n2B1个M非 饱和点由“边覆盖的定义”可知,W=MUN为G中的边覆盖,且 =M|+N|=β1+n-2阝1=n-β 由“W1是最小边覆盖”可知,W1中每条边的两个端点不可能都 与W1中的其它边相关联,因此,在由W构造M1时(注意到构造出来 的M1显然是匹配),每移去相邻两条边中的一条时,产生且只产生 个M非饱和点所以,|N=-M=M1的非饱和点数=n- 2M整理后,得W=a1=n-|M 又因为M是匹配,W是边覆盖,所以,M4≤阝1W≥a1 通过比较可得a1=nM≥n-B1=|W≥α1显然上式中 各等号成立,所以,M1=B1W=a1且α1+β1=n。由此可知, M1是最大匹配,W是最小边覆盖,且结论(3)成立 1212 最大匹配与最小边覆盖 由“M为最大匹配”可知, |M| = β1. 于是G中含有n-2β1个M-非 饱和点.由“边覆盖的定义”可知, W = M∪N为G中的边覆盖, 且 |W| = |M|+|N| = β1 + n - 2β1 = n - β1 由“W1是最小边覆盖”可知, W1中每条边的两个端点不可能都 与W1中的其它边相关联, 因此, 在由W1构造M1时(注意到构造出来 的M1显然是匹配), 每移去相邻两条边中的一条时, 产生且只产生 一个M-非饱和点.所以, |N1| = |W1| - |M1| = M1的非饱和点数 = n - 2|M1|. 整理后, 得 |W1| = α1 = n - |M1| 又因为M1是匹配, W是边覆盖, 所以, |M1| ≤ β1, |W| ≥ α1。 通过比较可得 α1 = n-|M1| ≥ n - β1 = |W| ≥ α1。显然上式中 各等号成立, 所以, |M1| = β1, |W| = α1, 且α1+ β1 = n。由此可知, M1是最大匹配, W是最小边覆盖, 且结论(3)成立。 定理3. (定理的描述内容见上页) 证明: