![偶图的匹配与覆盖.ppt_第1页](http://file.renrendoc.com/FileRoot1/2019-2/3/8747509a-500c-4f9b-971f-4061346f2c34/8747509a-500c-4f9b-971f-4061346f2c341.gif)
![偶图的匹配与覆盖.ppt_第2页](http://file.renrendoc.com/FileRoot1/2019-2/3/8747509a-500c-4f9b-971f-4061346f2c34/8747509a-500c-4f9b-971f-4061346f2c342.gif)
![偶图的匹配与覆盖.ppt_第3页](http://file.renrendoc.com/FileRoot1/2019-2/3/8747509a-500c-4f9b-971f-4061346f2c34/8747509a-500c-4f9b-971f-4061346f2c343.gif)
![偶图的匹配与覆盖.ppt_第4页](http://file.renrendoc.com/FileRoot1/2019-2/3/8747509a-500c-4f9b-971f-4061346f2c34/8747509a-500c-4f9b-971f-4061346f2c344.gif)
![偶图的匹配与覆盖.ppt_第5页](http://file.renrendoc.com/FileRoot1/2019-2/3/8747509a-500c-4f9b-971f-4061346f2c34/8747509a-500c-4f9b-971f-4061346f2c345.gif)
已阅读5页,还剩5页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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 在
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 个人定制门窗简易合同书
- 全新收款服务三方协议
- 毕业生个人自我鉴定6篇
- 版租赁合同解除协议
- 常州交通工具租赁合同
- 机械买卖简单合同范本
- 全新红砖砖购销合同
- 鱼塘承包合同书范文
- 木工模板施工承包合同范本
- 收购股权协议书范本
- 2024年版全国助理社会工作师《社会工作实务》考试典型题题库及参考答案1套
- 2022-2023学年浙江省绍兴市柯桥区人教版五年级下册期末学业评价测试数学试卷
- 材料力学(山东联盟-中国石油大学(华东))知到章节答案智慧树2023年
- (WORD版可修改)JGJ59-2023建筑施工安全检查标准
- 场地平整安全应急方案
- 《初中英语阅读》PPT课件.ppt
- 心血管内科病例讨论一.ppt
- 上海静安区2016-2017学年八年级第二学期期终试卷(含答案)
- 关于购置格力空调 “双级压缩机”空调供暖系统策划书——CNBE.doc
- 一种触发式汇率期权定价的数学模型_徐承龙.pdf
评论
0/150
提交评论