匹配与边覆盖 推论设G是n阶无孤立点的图,M为G中的匹配W是G中的边覆盖, 则M|≤|W;当等号成立时,M为G中完美匹配,W为G中最小边 覆盖 证明: 由定理3中的(1)可知β1≤a1 又由定义可知,M|≤β1≤α1≤W 所以,圃M≤W成立.当等号成立时,说明M是最大匹配,W是 最小边覆盖。 由定理3中(3)可知,a1+B1=2B1=n,显然,G中无M非饱和点 所以,M必为G中完美匹配13 匹配与边覆盖 由定理3中的(1)可知 β1 ≤ α1. 又由定义可知, |M| ≤ β1 ≤ α1 ≤ |W|. 所以, |M| ≤ |W|成立. 当等号成立时, 说明 M是最大匹配, W是 最小边覆盖。 由定理3中(3)可知, α1 + β1 = 2β1 = n, 显然, G中无M-非饱和点. 所以, M必为G中完美匹配. 推论 设G是n阶无孤立点的图, M为G中的匹配, W是G中的边覆盖, 则|M| ≤ |W|; 当等号成立时, M为G中完美匹配, W为G中最小边 覆盖. 证明: