《组合最优化》对集算法1对集(匹配)理论.doc

第十二章 对集(匹配)理论 对集(匹配) *设G=(V,E,ME,若M中任何两条边均不相邻,则称M为G中的边独立集,也称M为G中的对集(匹配.若在M中再加入G中任意一条边后,所得的集合都不是对集了,则称M为极大对集.边数最多的对集称为最大对集,其边数称为边独立数或最大对集的边数,记作,简记为. e6 e7 e1 e3 e5 e2 e4 e6 e7 e1 e3 e5 e2 e4 e6 e7 e1 e