最大匹配与最小边覆盖 定理3.设n阶图G中无孤立点 (1)设M为G的一个最大匹配,对于G中每个M非饱和点均取 条与其关联的边,组成边集N,则W=MUN为G中最小边覆盖; (2)设W为G中的一个最小边覆盖,若W1中存在相邻的边就移 去其中的一条,设移去的边集为N1则M1=W1-N1为G中一个最 大匹配; (3)G中边覆盖数α1与匹配数β1满足α1+B1=n11 最大匹配与最小边覆盖 (1) 设M为G的一个最大匹配, 对于G中每个M-非饱和点均取一 条与其关联的边, 组成边集N, 则W = M∪N为G中最小边覆盖; (2) 设W1为G中的一个最小边覆盖, 若W1中存在相邻的边就移 去其中的一条, 设移去的边集为N1, 则M1 = W1 - N1为G中一个最 大匹配; (3) G中边覆盖数α1与匹配数β1, 满足 α1+ β1 = n. 定理3. 设n阶图G中无孤立点