偶图的匹配与覆盖.ppt

《偶图的匹配与覆盖.ppt》由会员分享，可在线阅读，更多相关《偶图的匹配与覆盖.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解偶图的匹配与覆盖 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解TH 若若G为为k正则偶图，则正则偶图，则G有完美匹配有完美匹配补充补充 G为二部图，为二部图，(X,Y)为其二分类，证为其二分类，证明明G有完美匹配的充要条件是有完美匹配的充要条件是|N(S)|S|,对所有对所有SV成立成立匹匹匹匹 配配配配 与与与与 因因因因 子

2、子子子 分分分分 解解解解例题例题1 1 某大学计算机系有某大学计算机系有3 3个课外学习小组：网络组、个课外学习小组：网络组、网页制作组和数据库组。今有张、王、李、赵、陈网页制作组和数据库组。今有张、王、李、赵、陈5 5名同学。若已知：名同学。若已知：(1)(1)张、王为网络组成员，张、李、赵为网页制作张、王为网络组成员，张、李、赵为网页制作组成员，李、赵、陈为数据库组成员；组成员，李、赵、陈为数据库组成员；(2)(2)张为网络组成员，王、李、赵为网页制作组成张为网络组成员，王、李、赵为网页制作组成员，王、李、赵、陈为数据库组成员；员，王、李、赵、陈为数据库组成员；(3)(3)张为网络组和网

3、页制作组成员，王、李、赵、张为网络组和网页制作组成员，王、李、赵、陈为数据库组成员。陈为数据库组成员。问以上问以上3 3种情况下能否各选出种情况下能否各选出3 3名不兼职的组长？名不兼职的组长？匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解证明不能用证明不能用12的方格覆盖上图的方格覆盖上图例例题题2匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解定义定义2 2 图图G的一个的一个覆盖覆盖是指是指V(G)的一个子集的一

4、个子集K，使得，使得G中中每一条边至少有一个端点每一条边至少有一个端点在在 K中。中。若若G中没有覆盖中没有覆盖K使得使得|K|K|则称则称K为为最小最小覆盖覆盖。匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解匹配与覆盖的关系是什么呢？匹配与覆盖的关系是什么呢？匹配匹配-M覆盖覆盖-K|M|K|等号等号成立时会有哪些结论成立时会有哪些结论?匹匹匹匹 配配配配 与与与与 因因因因 子子子子 分分分分 解解解解TH 设设M为匹配，为匹配，K为覆盖，若为覆盖，若|M|K|则则M为最大匹配，为最大匹配，K为最小覆盖为最小覆盖TH 在偶图中设在偶图中设M为最大匹配，为最大匹配，K为最小为最小覆盖，则覆盖，则|M|K|