《偶图的匹配与覆盖.ppt》由会员分享，可在线阅读，更多相关《偶图的匹配与覆盖.ppt（10页珍藏版）》请在三一文库上搜索。
1、匹匹 配配 与与 因因 子子 分分 解解 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、、王为网络组成员，张、李、赵为网页制作 组成员，李、赵、陈为数据库组成员； (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|