欢迎来到乐乐文库,课件爱好者! | 帮助中心 精品ppt课件,ppt课件精品!
乐乐文库,课件爱好者
首页 乐乐文库,课件爱好者 > 资源分类 > PPT文档下载

10.4二分图.ppt

  • 资源大小:339.00KB        全文页数:8页
  • 资源格式: PPT        下载权限:游客/注册会员/VIP会员    下载费用:15金币 【人民币15元】
游客快捷下载 游客一键下载
会员登录下载
下载资源需要15金币 【人民币15元】

邮箱/手机:
温馨提示:

支付成功后,系统会根据您填写的邮箱或者手机号作为您下次登录的用户名和密码(如填写的是手机,那登陆用户名和密码就是手机号),方便下次登录下载和查询订单;
特别说明:
请自助下载,系统不会自动发送文件的哦;
支付方式: 支付宝   
验证码:   换一换

 
友情提示
2、本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

10.4二分图.ppt

1,10.4 二分图,二分图 完全二分图 匹配 极大匹配 最大匹配 匹配数 完备匹配,2,二分图,定义 设无向图 G, 若能将V 分成V1 和 V2 V1V2V, V1V2, 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二分图, 记为, 称V1和V2为互补顶点子集. 又若G 是简单图, 且V1中每个顶点均与V2中每个顶点都相 邻, 则称G为完全二分图, 记为Kr,s, 其中r|V1|, s|V2|. 注意 n 阶零图为二分图.,3,二分图的判别法,定理 非平凡无向图G是二分图当且仅当G中无奇数长度的回路 例 下述各图都是二分图,4,匹配,设G, 匹配边独立集 任2条边均不相邻的边子集 极大匹配 添加任一条边后都不再是匹配的匹配 最大匹配 边数最多的匹配 匹配数 最大匹配中的边数, 记为1 例 3个图的匹配数 依次为3, 3, 4.,5,匹配 续,设M为G中一个匹配 vi与vj被M匹配 vi,vjM v为M饱和点 M中有边与v关联 v为M非饱和点 M中没有边与v关联 M为完美匹配 G的每个顶点都是M饱和点 例 关于M1, a,b,e,d是饱和点 f,c是非饱和点 M1不是完美匹配 M2是完美匹配,6,二分图中的匹配,定义 设G为二部图, |V1||V2|, M是G中最 大匹配, 若V1中顶点全是M饱和点, 则称M为G中V1 到V2的完全匹配. 当|V1||V2|时, 完备匹配变成完美 匹配.,,7,Hall定理,定理Hall定理 设二分图G中,|V1||V2|. G中存 在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与V2 中的k个顶点相邻k1,2,,|V1|. 由Hall定理不难证明, 上一页图2没有完备匹配. 定理 设二部图G中, 如果存在t1, 使得V1中每个 顶点至少关联 t 条边, 而V2中每个顶点至多关联t条边,则G 中存在V1到V2的完备匹配. Hall定理中的条件称为“相异性条件”, 第二个定理中的条件 称为 t 条件. 满足 t 条件的二部图一定满足相异性条件.,8,一个应用实例,例 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、香港去开会. 已知a只想去上海,b只想去广州,c, d, e都表示想去广州或香港. 问该课题组在满足个人要求的条件下,共有几种派遣方案 解 令G, 其中V1{s, g, x}, V2{a, b, c, d, e}, E{u,v | uV1, vV2, v想去u}, 其中s, g, x分别表示上海、广州和香港. G如图所示. G 满足相异性条件,因而可给 出派遣方案,共有9种派遣方案 请给出这9种方案.,,

注意事项

本文(10.4二分图.ppt)为本站会员(w89153)主动上传,乐乐文库,课件爱好者仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知乐乐文库,课件爱好者(发送邮件至1748365562@qq.com或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

站长联系QQ:1748365562
工信部备案号: 鄂ICP备17024083号                 公安局备案号:42118102000213

收起
展开