[工学]图论-的配对问题课件.ppt

上传人（卖家）：晟晟文业

文档编号：5102254

上传时间：2023-02-11

格式：PPT

页数：102

大小：1.51MB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

29 文币

交易提醒：下载本文档，相应价格的文币将全额进入上传人（卖家）的账号。立即下载优惠套餐（点此详情）

【下载声明】
1. 本站全部试题类文档，若标题没写含答案，则无答案；标题注明含答案的文档，主观题也可能无答案。请谨慎下单，一旦售出，不予退换。
2. 本站全部PPT文档均不含视频和音频，PPT中出现的音频或视频标识（或文字）仅表示流程，实际无音频或视频文件。请谨慎下单，一旦售出，不予退换。
3. 本页资料《[工学]图论-的配对问题课件.ppt》由用户（晟晟文业）主动上传，其收益全归该用户。163文库仅提供信息存储空间，仅对该用户上传内容的表现方式做保护处理，对上传内容本身不做任何修改或编辑。若此文所含内容侵犯了您的版权或隐私，请立即通知163文库（点击联系客服），我们立即给予删除！
4. 请根据预览情况，自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器，压缩文件请下载最新的WinRAR软件解压。

配套讲稿：: 如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
特殊限制：: 部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
关键词：: 工学图论配对问题课件

资源描述：: 1、f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5M=(f1,m2),(f2,m1),(f3,m4),(f4,m5)f1f2m1f3f4f5m2m3m4m5M=(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)M=(f1,m3),(f2,m1),(f3,m2),(f5,m5)f1f2m1f3f4f5m2m3m4m5M=(f1,m3),(f2,m1),(f3,m2),(f5,m5)f
2、1f2m1f3f4f5m2m3m4m5饱和的饱和的不饱和不饱和的的f1f2m1f3f4f5m2m3m4m5M=(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)P=f1m3f4m5f2m1f5m4M=(f2,m5),(f3,m2),(f4,m3),(f5,m4)P=m1f2m5f4m3f1 是一条可增广道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5M=(f2,m5),(f3,m2),(f4,m3),(f5,m4)P=m1f2m5f4m3f1 是一条可增广道路。f1f2m1f3f4f5m2
3、m3m4m5M=(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)M=(f1,m3),(f2,m1),(f3,m2),(f5,m5)f1f2m1f3f4f5m2m3m4m5引理引理设设P是匹配是匹配-可增广道路，则可增广道路，则PM是一个比M更大的匹配，且|PM|M|+1.定理定理1(Berge)设设G=(V,E)，M为为G中匹配，则中匹配，则 M为为G的最的最大匹配当且仅当大匹配当且仅当G中不存在中不存在 M 可增广道。可增广道。证明证明必要性：如有必要性：如有M-可增广道路，则有更大匹配。矛盾！可增广道路，则有更大匹配。矛盾！充分性充分性：如果有最大匹配：如果
4、有最大匹配M,|M|M|.考虑考虑M M，在可增广路中，第一条边与最后一条边都不是中的边，因而可增广路中属于的边数比不在中边数少一条。MMMMMM实线边，M虚线边MM其中每个结点的最多与边和一个其中每个结点的最多与边和一个M边关联，每条道路是边关联，每条道路是M边和边和M边交互道路。边交互道路。其中回路包含相同数目的其中回路包含相同数目的M边和边和M边。由边。由|M|M|,必存必存在在M边开始，边开始，M边终止的边终止的M交互道路，即交互道路，即M-可增广道可增广道路，矛盾！路，矛盾！w1w2m1w3w4w5m2m3m4w1w2m1w3w4w5m2m3m4w1w2m1w3w4w5m2
5、m3m4YXx1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)x1x2
6、y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5
7、M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1
8、),(x2,y2),(x3,y5),(x4,y3),(x5,y4)x1x2y1x3x4x5y2y3y4y5 这时，M=(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)就是所求的最大匹配。x1x2y1x3x4x5y2y3y4y53 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5x1x2y1x3x4x5y2y3y4y53 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5l(x1)=5l
9、(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0 x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y53 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5x1x2y1x3x4x5y2y3y4y53 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5l(x1)=5l(x2)=
10、2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,V2=空集x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(
11、x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,V2=x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,x3,V2=y3x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)
12、=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,x3,V2=y3x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,x3,x1,V2=y3,y2x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4
13、)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,x3,x1,V2=y3,y2,3 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5=1NG(V1)=y1,y2,y3,y4,y5x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,x3,x1,V2=y3,y2=1l(x
14、1)=4l(x3)=3l(x4)=0l(y2)=1l(y3)=1x1x2y1x3x4x5y2y3y4y5l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,x3,x1,V2=y3,y23 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5V1=x4,x3,x1,V
15、2=y3,y2l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0 x1x2y1x3x4x5y2y3y4y5M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)M=(x1,y4),(x2,y1),(x3,y3),(x4,y4),(x5,y5),x1x2y1x3x4x5y2y3y4y5M=(x1,y4),(x2,y1),(x3,y3),(x4,y4),(x5,y5),l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(
16、y4)=0W=4+2+4+1+3=14x1x2y1x3x4x5y2y3y4y50 5 5 4 03 3 0 3 31 4 4 3 01 2 2 0 11 3 1 4 4 C=x1x2x3x4x5y1 y2 y3 y4 y5单星妖怪和双星妖怪：单星妖怪双星妖怪x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5单星妖怪第一类图第一类图第二类图第二类图目前仍无有效区分目前仍无有效区分(判别判别)任给定图属任给定图属第几类图的有效方法。第几类图的有效方法。np内排完，且每节课所用教室数？n（1 i p）maxEiip1 lplplpElpin p。pMpi提出条件时，判定
17、课表的存在性问题是个NP-complete问题。甚至当G为简单偶图，且学生不提出要求的情况下，也是如此。x1x2y1x3x4x5y2y3y4y5v1v2v3v4v5v7v6v1v2v3v4v5v7v6C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7v1v2
18、v3v4v5v7v6c1v1v2v3v4v5v7v6c1C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7C2=c2 C3=c2,c3 C7=c2,c3,c4,c5,c6,c7 C5=c2,c3,c4,c5 C6=c2,c3,c4,c5,c6 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2v1v2
19、v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2C3=c3 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c
20、2c3C5=c2,c4,c5 C1=c1,c2,c4 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4
21、,c5,c6,c7c2c3c1c2v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1c2C6=c3,c4,c5,c6 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1c2c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1c2C7=c2,c4,c5,c6,c7 c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c4,c5,c6,c7c2c3c1c2c3c2

展开阅读全文

163文库所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。

关于本文

本文标题：[工学]图论-的配对问题课件.ppt
链接地址：https://www.163wenku.com/p-5102254.html

晟晟文业

内容提供者

实名认证

联系作者