《偶图的匹配与覆盖.ppt》由会员分享，可在线阅读，更多相关《偶图的匹配与覆盖.ppt（10页珍藏版）》请在三一办公上搜索。
5.2 偶图的匹配与覆盖,定义1 顶点集S的邻集N(S),TH G为偶图，(X,Y)为其二分类，则G包 含饱和X的每个顶点的匹配当且仅当|N(S)|S|,对所有 S X 成立,TH 若G为k正则偶图，则G有完美匹配,补充 G为二部图，(X,Y)为其二分类，证明G有完美匹配的充要条件是|N(S)|S|,对所有SV成立,例题1 某大学计算机系有3个课外学习小组：网络组、网页制作组和数据库组。今有张、王、李、赵、陈5名同学。若已知：(1)张、王为网络组成员，张、李、赵为网页制作组成员，李、赵、陈为数据库组成员；(2)张为网络组成员，王、李、赵为网页制作组成员，王、李、赵、陈为数据库组成员；(3)张为网络组和网页制作组成员，王、李、赵、陈为数据库组成员。问以上3种情况下能否各选出3名不兼职的组长？,证明不能用12的方格覆盖上图,例题2,定义2 图G的一个覆盖是指V(G)的一个子集K，使得G中每一条边至少有一个端点在 K中。,若G中没有覆盖K使得|K|K|则称K为最小覆盖。,匹配与覆盖的关系是什么呢？,匹配-M,覆盖-K,|M|K|,等号成立时会有哪些结论?,TH 设M为匹配，K为覆盖，若|M|K|则M为最大匹配，K为最小覆盖,TH 在偶图中设M为最大匹配，K为最小覆盖，则|M|K|,
