工学图论的配对问题.pptx
《工学图论的配对问题.pptx》由会员分享,可在线阅读,更多相关《工学图论的配对问题.pptx(102页珍藏版)》请在咨信网上搜索。
1、第五章第五章 匹配匹配1 最大匹配最大匹配1n n具体问题描述:有n个女士和n个男士参加舞会,每位女士与其中若干位男士相识,每位男士与其中若干位女士相识,问如何安排,使得尽量多配对的男女舞伴相识。f1f2m1f3f4f5m2m3m4m51 匹配匹配1 最大匹配最大匹配1下图就是一种分配方法:f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)匹配问题是运筹学的重要问题之一,也是图论的重要匹配问题是运筹学的重要问题之一,也是图论的重要匹配问题是运筹学的重要问题之一,也是图论的重要匹配问题是运筹学的重要问题之一,也是图论的重要内容,
2、它在所谓内容,它在所谓内容,它在所谓内容,它在所谓“人员分配问题人员分配问题人员分配问题人员分配问题”和和和和“最优分配问题最优分配问题最优分配问题最优分配问题”中有重要作用。中有重要作用。中有重要作用。中有重要作用。n n 假定有一个男生有穷集合,其中每个男生认识一些女生,假定有一个男生有穷集合,其中每个男生认识一些女生,假定有一个男生有穷集合,其中每个男生认识一些女生,假定有一个男生有穷集合,其中每个男生认识一些女生,在什么条件下每个男生都可以和他认识的女生配对?在什么条件下每个男生都可以和他认识的女生配对?在什么条件下每个男生都可以和他认识的女生配对?在什么条件下每个男生都可以和他认识的
3、女生配对?n n 类似的工作分配问题:现有类似的工作分配问题:现有类似的工作分配问题:现有类似的工作分配问题:现有n n n n个人,个人,个人,个人,m m m m份工作,每个人有份工作,每个人有份工作,每个人有份工作,每个人有其擅长的工作。在什么条件下每个人都可以得到一份他其擅长的工作。在什么条件下每个人都可以得到一份他其擅长的工作。在什么条件下每个人都可以得到一份他其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作?如何分配?擅长的工作?如何分配?擅长的工作?如何分配?擅长的工作?如何分配?1 最大匹配定义最大匹配定义n n定义:若图G=(V,E)的顶点可以分成X,Y两个子集,每
4、个子集里的顶点互不相邻,这样的图称为二分图二分图。f1f2m1f3f4f5m2m3m4m51 最大匹配定义最大匹配定义1n n定义:若M是图G=(V,E)的边子集,且M中的任意两条边在G中不相邻,则称M为G中的一个匹配匹配,M中的每条边的两个端点称为是M-饱和的饱和的的。f1f2m1f3f4f5m2m3m4m5M=(f1,m2),(f2,m1),(f3,m4),(f4,m5)1 最大匹配定义最大匹配定义2n n定义:若图G中每个顶点均被M许配时,称M为G中的一个完美匹配完美匹配。f1f2m1f3f4f5m2m3m4m5M=(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,
5、m4)1 最大匹配定义最大匹配定义3n n定义:图G中边数最多的匹配M,称为G中的一个最大匹配最大匹配。M=(f1,m3),(f2,m1),(f3,m2),(f5,m5)f1f2m1f3f4f5m2m3m4m51 最大匹配定义最大匹配定义4n n定义:若匹配M的某边和顶点v关联,称v是M-饱和的饱和的,否则就是M-不饱和的不饱和的。M=(f1,m3),(f2,m1),(f3,m2),(f5,m5)f1f2m1f3f4f5m2m3m4m5饱和的饱和的不饱和不饱和的的1 最大匹配定义最大匹配定义5n n定义:若M是图G的一个匹配,若从G中一个顶点到另一个顶点存在一条道路,此路径由属于M和不属于M的
6、边交替出现组成的,则称此路径为M-交错路交错路。f1f2m1f3f4f5m2m3m4m5M=(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)P=f1m3f4m5f2m1f5m41 最大匹配定义最大匹配定义6n n定义:若交错路的两个端点为关于M的不饱和顶点时,称此交互道为可增广道路可增广道路。M=(f2,m5),(f3,m2),(f4,m3),(f5,m4)P=m1f2m5f4m3f1 是一条可增广道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m51 最大匹配定义最大匹配定义8f1f2m1f3f4f5m2m3m4m5M=(f2,
7、m5),(f3,m2),(f4,m3),(f5,m4)P=m1f2m5f4m3f1 是一条可增广道路。f1f2m1f3f4f5m2m3m4m5M=(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)1 最大匹配最大匹配 Berge定理定理n n定理7.1(Berge 1957):M为最大匹配的充要条件是:图G中不存在不存在可增广道路。M=(f1,m3),(f2,m1),(f3,m2),(f5,m5)f1f2m1f3f4f5m2m3m4m5引理引理设设P是匹配是匹配-可增广道路,则可增广道路,则PM是一个比M更大的匹配,且|PM|M|+1.定理定理1(Berge)设设G
8、=(V,E),M为为G中匹配,则中匹配,则 M为为G的最大的最大匹配当且仅当匹配当且仅当G中不存在中不存在 M 可增广道。可增广道。证明证明 必要性:如有必要性:如有M-可增广道路,则有更大匹配。矛盾!可增广道路,则有更大匹配。矛盾!充分性充分性:如果有最大匹配:如果有最大匹配M,|M|M|.考虑考虑M M,在 可增广路中,第一条边与最后一条边都不是 中的边,因而 可增广路中属于 的边数比不在 中边数少一条。M实线边,M虚线边MM其中每个结点的最多与边和一个其中每个结点的最多与边和一个M边关联,每条道路是边关联,每条道路是M边边和和M边交互道路。边交互道路。其中回路包含相同数目的其中回路包含相
9、同数目的M边和边和M边。由边。由|M|M|,必存必存在在M边开始,边开始,M边终止的边终止的M交互道路,即交互道路,即M-可增广道可增广道路,矛盾!路,矛盾!2 Hall定理定理 设有m个人,n项工作,每个人会做其中的若干项工作,能不能适当安排,使得每个人都有工作做?w1w2m1w3w4w5m2m3m42 Hall定理定理 当mn时,肯定是不可能的,即使是mn也不一定。但如果每个人能做的工作越多,越容易实现。w1w2m1w3w4w5m2m3m42 Hall定理定理1n nHall定理(1935):二分图G存在一匹配M,使得X的所有顶点关于M饱和的充要条件是:对于X任一子集A,及与A邻接的点集为
10、N(A),恒有:|N(A)|A|。w1w2m1w3w4w5m2m3m4YX3 人员分派问题人员分派问题 1965年,匈牙利著名数学家Edmonds设计了一种求最大匹配的算法,称为匈牙利(Hungarian)算法。工作分配工作分配问题:现有有n个人,个人,n份工作,每份工作,每个人有其擅个人有其擅长的工作。在什么条件下每个人的工作。在什么条件下每个人都可以得到一份他擅都可以得到一份他擅长的工作?如何分配?的工作?如何分配?3 匈牙利算法匈牙利算法n n 匈牙利(Hungarian)算法:(1)任给一个初始匹配;(2)若X已经饱和,结束;否则转(3);(3)在X中找一个非饱和点x0,V1=x0,V
11、2=空集;(4)若N(V1)=V2则停止,否则任选一点yN(V1)-V2;(5)若y已饱和,M中必有(y,z);作【V1=V1 z,V2=V2 y;转(4)】,否则【求一条从x0到y的可增广道路P,对之进行增广;转(2)】3 匈牙利算法例匈牙利算法例用匈牙利算法求下图的最大匹配:例例x1x2y1x3x4x5y2y3y4y53 匈牙利算法例解匈牙利算法例解(1 1)任给一个初始匹配;)任给一个初始匹配;(2 2)若)若X X已经饱和,结束;否则转(已经饱和,结束;否则转(3 3););解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)3 匈牙利算法例解
12、匈牙利算法例解1(3 3)在)在X X中找一个非饱和点中找一个非饱和点x x0 0,V V1 1=x=x0 0,V V2 2=空集空集(4 4)若)若N(VN(V1 1)=V)=V2 2则停止,否则任选一点则停止,否则任选一点y yN(VN(V1 1)-V)-V2 2解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=x=x2 2,V,V2 2=空集空集N(VN(V1 1)=y)=y2 2,y y3 3 3 匈牙利算法例解匈牙利算法例解2(5 5)若)若y y已饱和,已饱和,MM中必有中必有(y,z)(y,z);作;作【V V1 1=V=
13、V1 1 z z,V V2 2=V=V2 2 yy;转(转(4 4)】,否则,否则【求一求一条从条从x x0 0到到y y的可增广道路的可增广道路P P,对之进行增广;转,对之进行增广;转(2 2)】解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=V=V1 1xx5 5=x=x2 2,x,x5 5;V V2 2=V=V2 2 yy3 3 =y=y3 3 V V1 1=x=x2 2,V,V2 2=空集空集3 匈牙利算法例解匈牙利算法例解3(4 4)若)若N(VN(V1 1)=V)=V2 2则停止,否则任选一点则停止,否则任选一点y yN
14、(VN(V1 1)-V)-V2 2;解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=x=x2 2,x,x5 5;V V2 2=y=y3 3 N(VN(V1 1)=y)=y2 2,y,y3 3,y,y4 4,y,y5 5 3 匈牙利算法例解匈牙利算法例解4(5 5)若)若y y已饱和,已饱和,MM中必有中必有(y,z)(y,z);作;作【V V1 1=V=V1 1 z z,V V2 2=V=V2 2 yy;转(转(4 4)】,否则,否则【求求一条从一条从x x0 0到到y y的可增广道路的可增广道路P P,对之进行增广;,对之进行增广;
15、转(转(2 2)】解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=x=x2 2,x,x5 5;V V2 2=y=y3 3;V V1 1=V=V1 1xx3 3=x=x2 2,x,x5 5,x,x3 3;V V2 2=V=V2 2 yy5 5 =y=y3 3,y,y5 5 3 匈牙利算法例解匈牙利算法例解5(4 4)若)若N(VN(V1 1)=V)=V2 2则停止,否则任选一点则停止,否则任选一点y yN(VN(V1 1)-V)-V2 2;解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V
16、V1 1=x=x2 2,x,x5 5,x x3 3;V V2 2=y=y3 3,y,y5 5;N(VN(V1 1)=y)=y2 2,y,y3 3,y,y4 4,y,y5 5 3 匈牙利算法例解匈牙利算法例解6(5 5)若)若y y已饱和,已饱和,MM中必有中必有(y,z)(y,z);作;作【V V1 1=V=V1 1 z z,V V2 2=V=V2 2 yy;转(转(4 4)】,否则,否则【求求一条从一条从x x0 0到到y y的可增广道路的可增广道路P P,对之进行增广;,对之进行增广;转(转(2 2)】解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,
17、y3)V V1 1=x=x2 2,x,x5 5,x,x3 3;V V2 2=y=y3 3,y,y5 5;x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1),(x2,y3),(x3,y2),(x5,y5)3 匈牙利算法例解匈牙利算法例解7(2 2)若)若X X已经饱和,结束;否则转(已经饱和,结束;否则转(3 3););(3 3)在)在X X中找一个非饱和点中找一个非饱和点x x0 0,V V1 1=x=x0 0,V V2 2=(4 4)若)若N(VN(V1 1)=V)=V2 2则停止,否则任选一点则停止,否则任选一点y yN(VN(
18、V1 1)-V)-V2 2解解x1x2y1x3x4x5y2y3y4y5V V1 1=x=x4 4;V V2 2=空集空集M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)N(VN(V1 1)=y)=y3 3 3 匈牙利算法例解匈牙利算法例解8(5 5)若)若y y已饱和,已饱和,MM中必有中必有(y,z)(y,z);作;作【V V1 1=V=V1 1 z z,V V2 2=V=V2 2 yy;转(转(4 4)】,否则,否则【求求一条从一条从x x0 0到到y y的可增广道路的可增广道路P P,对之进行增广;,对之进行增广;转(转(2 2)】解解x1x2y1x3x4x5y2y3y
19、4y5V V1 1=x=x4 4;V V2 2=空集空集M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=V=V1 1xx2 2=x=x4 4,x,x2 2;V V2 2=V=V2 2yy3 3 =y=y3 3 3 匈牙利算法例解匈牙利算法例解9(4 4)若)若N(VN(V1 1)=V)=V2 2则停止,否则任选一点则停止,否则任选一点y yN(VN(V1 1)-V)-V2 2解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,;V V2 2=y=y3 3 N(VN
20、(V1 1)=y)=y2 2,y,y3 3 3 匈牙利算法例解匈牙利算法例解10(5 5)若)若y y已饱和,已饱和,MM中必有中必有(y,z)(y,z);作;作【V V1 1=V=V1 1 z z,V V2 2=V=V2 2 yy;转(转(4 4)】,否则,否则【求求一条从一条从x x0 0到到y y的可增广道路的可增广道路P P,对之进行增广;,对之进行增广;转(转(2 2)】解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,;V V2 2=y=y3 3 V V1 1=V=V1 1xx3
21、3=x=x4 4,x,x2 2,x,x3 3;V V2 2=V=V2 2yy2 2 =y=y3 3,y,y2 2 3 匈牙利算法例解匈牙利算法例解11(4 4)若)若N(VN(V1 1)=V)=V2 2则停止,否则任选一点则停止,否则任选一点y yN(VN(V1 1)-V)-V2 2解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,x,x3 3;V V2 2=y=y3 3,y,y2 2 N(VN(V1 1)=y)=y2 2,y,y3 3,y,y5 5 3 匈牙利算法例解匈牙利算法例解12(5
22、5)若)若y y已饱和,已饱和,MM中必有中必有(y,z)(y,z);作;作【V V1 1=V=V1 1 z z,V V2 2=V=V2 2 yy;转(转(4 4)】,否则,否则【求求一条从一条从x x0 0到到y y的可增广道路的可增广道路P P,对之进行增广;,对之进行增广;转(转(2 2)】解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,x,x3 3;V V2 2=y=y3 3,y,y2 2 V V1 1=V=V1 1xx5 5=x=x4 4,x,x2 2,x,x3 3,x,x5 5;
23、V V2 2=V=V2 2yy5 5 =y=y3 3,y,y2 2,y,y5 5 3 匈牙利算法例解匈牙利算法例解13(4 4)若)若N(VN(V1 1)=V)=V2 2则停止,否则任选一点则停止,否则任选一点y yN(VN(V1 1)-V)-V2 2解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,x,x3 3,x,x5 5;V V2 2=y=y3 3,y,y2 2,y,y5 5 N(VN(V1 1)=y)=y2 2,y,y3 3,y,y5 5,y,y4 4 3 匈牙利算法例解匈牙利算法例解
24、14(5 5)若)若y y已饱和,已饱和,MM中必有中必有(y,z)(y,z);作;作【V V1 1=V=V1 1 z z,V V2 2=V=V2 2 yy;转(转(4 4)】,否则,否则【求求一条从一条从x x0 0到到y y的可增广道路的可增广道路P P,对之进行增广;,对之进行增广;转(转(2 2)】解解x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,x,x3 3,x x5 5;V V2 2=y=y3 3,y,y2 2,y,y5 5 x1x2y1x3x4x5y2y3y4y5x1x2y1x3
25、x4x5y2y3y4y5M=M E(P)=(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)3 匈牙利算法例解匈牙利算法例解15(2 2)若)若X X已经饱和,结束;否则转(已经饱和,结束;否则转(3 3););解解x1x2y1x3x4x5y2y3y4y5 这时,M=(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)就是所求的最大匹配。4 最佳匹配最佳匹配 公司里有n名工作人员,他们每个人都能承担n项工作的其中若干项,因为每个人的特长不同,所以对每项工作创造的价值也有所不同。问如何安排,使得他们总的创造价值最大?4 最佳匹配最佳匹配 x对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工学 配对 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。