工学图论的配对问题.pptx

第五章第五章 匹配匹配1 最大匹配最大匹配1n n具体问题描述：有n个女士和n个男士参加舞会，每位女士与其中若干位男士相识，每位男士与其中若干位女士相识，问如何安排，使得尽量多配对的男女舞伴相识。f1f2m1f3f4f5m2m3m4m51 匹配匹配1 最大匹配最大匹配1下图就是一种分配方法：f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)匹配问题是运筹学的重要问题之一，也是图论的重要匹配问题是运筹学的重要问题之一，也是图论的重要匹配问题是运筹学的重要问题之一，也是图论的重要匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓内容，它在所谓内容，它在所谓内容，它在所谓“人员分配问题人员分配问题人员分配问题人员分配问题”和和和和“最优分配问题最优分配问题最优分配问题最优分配问题”中有重要作用。中有重要作用。中有重要作用。中有重要作用。n n 假定有一个男生有穷集合，其中每个男生认识一些女生，假定有一个男生有穷集合，其中每个男生认识一些女生，假定有一个男生有穷集合，其中每个男生认识一些女生，假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生配对？在什么条件下每个男生都可以和他认识的女生配对？在什么条件下每个男生都可以和他认识的女生配对？在什么条件下每个男生都可以和他认识的女生配对？n n 类似的工作分配问题：现有类似的工作分配问题：现有类似的工作分配问题：现有类似的工作分配问题：现有n n n n个人，个人，个人，个人，m m m m份工作，每个人有份工作，每个人有份工作，每个人有份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他其擅长的工作。在什么条件下每个人都可以得到一份他其擅长的工作。在什么条件下每个人都可以得到一份他其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？擅长的工作？如何分配？擅长的工作？如何分配？擅长的工作？如何分配？1 最大匹配定义最大匹配定义n n定义：若图G=(V,E)的顶点可以分成X，Y两个子集，每个子集里的顶点互不相邻，这样的图称为二分图二分图。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,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的边交替出现组成的，则称此路径为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,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)设设GV,E)，M为为G中匹配，则中匹配，则 M为为G的最大的最大匹配当且仅当匹配当且仅当G中不存在中不存在 M 可增广道。可增广道。证明证明 必要性：如有必要性：如有M-可增广道路，则有更大匹配。矛盾！可增广道路，则有更大匹配。矛盾！充分性充分性：如果有最大匹配：如果有最大匹配M,|M|M|.考虑考虑M M，在 可增广路中，第一条边与最后一条边都不是 中的边，因而 可增广路中属于 的边数比不在 中边数少一条。M实线边，M虚线边MM其中每个结点的最多与边和一个其中每个结点的最多与边和一个M边关联，每条道路是边关联，每条道路是M边边和和M边交互道路。边交互道路。其中回路包含相同数目的其中回路包含相同数目的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邻接的点集为N(A)，恒有：|N(A)|A|。w1w2m1w3w4w5m2m3m4YX3 人员分派问题人员分派问题 1965年，匈牙利著名数学家Edmonds设计了一种求最大匹配的算法，称为匈牙利(Hungarian)算法。工作分配工作分配问题：现有有n个人，个人，n份工作，每份工作，每个人有其擅个人有其擅长的工作。在什么条件下每个人的工作。在什么条件下每个人都可以得到一份他擅都可以得到一份他擅长的工作？如何分配？的工作？如何分配？3 匈牙利算法匈牙利算法n n 匈牙利(Hungarian)算法：（1）任给一个初始匹配；（2）若X已经饱和，结束；否则转（3）；（3）在X中找一个非饱和点x0，V1=x0，V2=空集；（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 匈牙利算法例解匈牙利算法例解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=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 yNVN(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，对之进行增广；，对之进行增广；转（转（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 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,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(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）】解解x1x2y1x3x4x5y2y3y4y5V 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(VNV1 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 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 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；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 匈牙利算法例解匈牙利算法例解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 x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=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对每项工作创造的价值的如右边的矩阵所表示：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 y55 最佳匹配算法及例最佳匹配算法及例 Kuhn和Munkras设计了求最佳匹配的有效算法，他们把求最佳匹配的问题转化成可用匈牙利算法求另一个图的完美匹配的问题。5 最佳匹配算法最佳匹配算法1 为此，他们对加权的二分图每个顶点v给一个顶标l(v)，当xiX，yjY，l(xi)+l(yj)cij时，称这样的顶标为可行顶点可行顶点a标号标号（feasible vertex labelling）。5 最佳匹配算法最佳匹配算法2初始的时候，令l(xi)=max ci*；l(yi)=0；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 y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0最佳匹配定理最佳匹配定理n n设二分图Kn,n=G是具有正常顶标l的加权图，取G的边子集El=eij|eijE(G),l(i)+l(j)=cij。令Gl是以El为边集的生成子图，如果有Gl完美匹配M，则M即为G的最佳匹配。x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y55 最佳匹配算法最佳匹配算法3n nKM算法：（1）选定初始正常标顶l，构作图Gl，在Gl中用匈牙利算法求一个最大匹配；（2）若X饱和则结束，此时所得匹配就是最佳匹配，否则在X中任选一个非饱和点x0，令V1=x0，V2=；（3）若NGl(V1)=V2，则取=min(l(xi)+l(yj)-cij)，其中xiV1，yjNG(V1)-V2，使得 l(v)-vV1 l(v)=l(v)+vV2 l(v)其他重新构作图Gl，在NGl(V1)-V2任取一点y，转向（4）；否则在NGl(V1)-V2任取一点y，转向（4）5 最佳匹配算法最佳匹配算法4（4）若y已饱和，M中必有(y,z)；作【V1=V1 z，V2=V2 y；转（3）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】5 最佳匹配算法例最佳匹配算法例求下图的最佳匹配例例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 y55 最佳匹配算法例解最佳匹配算法例解1（1 1）选定初始正常标顶）选定初始正常标顶l l，构作图，构作图GGl l，在，在GGl l中中用匈牙利算法求一个用匈牙利算法求一个最大匹配；最大匹配；解解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 y5l(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)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y55 最佳匹配算法例解最佳匹配算法例解2（2 2）若）若X X饱和则结束，此时所得匹配就是最饱和则结束，此时所得匹配就是最佳匹配，否则在佳匹配，否则在X X中任选一个非饱和点中任选一个非饱和点x x0 0，令令V V1 1=x=x0 0 ，V V2 2=空集；空集；解解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,V2=空集5 最佳匹配算法例解最佳匹配算法例解3（3）若NGl(V1)=V2，则；否则在NGl(V1)-V2任取一点y，转向（4）解解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,V2=5 最佳匹配算法例解最佳匹配算法例解4（4 4）若）若y y已饱和，已饱和，MM中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z z，V V2 2=V=V2 2 yy；转（转（3 3）】，否则，否则【求一条从求一条从x x0 0到到y y的可增广道路的可增广道路P P，对之进行增，对之进行增广；转（广；转（2 2）】解解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=y35 最佳匹配算法例解最佳匹配算法例解5（3）若NGl(V1)=V2，则；否则在NGl(V1)-V2任取一点y，转向（4）解解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=y35 最佳匹配算法例解最佳匹配算法例解6（4 4）若）若y y已饱和，已饱和，MM中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z z，V V2 2=V=V2 2 yy；转（转（3 3）】，否则，否则【求一条从求一条从x x0 0到到y y的的可增广道路可增广道路P P，对之进行增广；转（，对之进行增广；转（2 2）】解解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,x3,x1,V2=y3,y25 最佳匹配算法例解最佳匹配算法例解7（3）若NGl(V1)=V2，取=min(l(xi)+l(yj)-cij)，其中xiV1，yjNG(V1)-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,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,y55 最佳匹配算法例解最佳匹配算法例解8 l(v)-vV1 l(v)=l(v)+vV2 l(v)其他解解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,x1,V2=y3,y2=1l(x1)=4l(x3)=3l(x4)=0l(y2)=1l(y3)=15 最佳匹配算法例解最佳匹配算法例解9重新构作图重新构作图GGl l，在，在NNGlGl(V(V1 1)-V)-V2 2任取一点任取一点y y，转向（，转向（4 4）解解x1x2y1x3x4x5y2y3y4y5l(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 y5x1x2y1x3x4x5y2y3y4y5l(xl(xi i)+l(y)+l(yj j)c cij ij5 最佳匹配算法例解最佳匹配算法例解10（4 4）若）若y y已饱和，已饱和，MM中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z z，V V2 2=V=V2 2 yy；转（转（3 3）】，否则，否则【求一条从求一条从x x0 0到到y y的可增广道路的可增广道路P P，对之进行增广；转（，对之进行增广；转（2 2）】x1x2y1x3x4x5y2y3y4y5解解V1=x4,x3,x1,V2=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),5 最佳匹配算法例解最佳匹配算法例解11（2 2）若）若X X饱和则结束，此时所得匹配就是最佳匹配，饱和则结束，此时所得匹配就是最佳匹配，否则在否则在X X中任选一个非饱和点中任选一个非饱和点x x0 0，令，令V V1 1=x=x0 0 ，V V2 2=；x1x2y1x3x4x5y2y3y4y5解解M=(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(y4)=0W=4+2+4+1+3=14课堂练习课堂练习1、用匈牙利算法求下图的最大匹配。x1x2y1x3x4x5y2y3y4y5课堂练习课堂练习2、若二分图K5,5的权值矩阵如下，求其最佳匹配。0 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 y56 色数问题色数问题n n边的着色问题n n顶点的着色问题一、边的着色问题一、边的着色问题定义给图G的边着色，使得有共同顶点的边异色的最少颜色数，称为边色数边色数。边色数=3边色数=5一、边的着色问题一、边的着色问题n n妖怪图（snark graph）妖怪图每个点都关联着3条边，用4种颜色可以把每条边涂上颜色，使得有公共端点的边异色，而用3种颜色办不到，切断任意3条边不会使它断裂成2个有边的图。一、边的着色问题一、边的着色问题1单星妖怪和双星妖怪：单星妖怪双星妖怪一、边的着色问题一、边的着色问题n n时间表问题；时间表问题；设设x x1 1,x,x2 2,x,xmm为为mm个工作人员，个工作人员，y y1 1,y,y2 2,y,yn n表为表为n n种设备，种设备，工作人员对设备提出要求，使用时间均假定以单位时间计工作人员对设备提出要求，使用时间均假定以单位时间计算，自然每一个工作人员在同一个时间只能使用一种设备，算，自然每一个工作人员在同一个时间只能使用一种设备，某一种设备在同一时间里只能为一个工作人员使用，问应某一种设备在同一时间里只能为一个工作人员使用，问应如何合理安排，使得尽可能短时间里满足工作人员的要求如何合理安排，使得尽可能短时间里满足工作人员的要求？问题转换为问题转换为X=x1,x2,X=x1,x2,xm,xm，Y=y1,y2,Y=y1,y2,yn,yn的二的二分图分图GG，工作人员，工作人员xi xi要求使用设备要求使用设备yj yj，每单位时间对应一，每单位时间对应一条从条从xi xi到到yj yj的边，这样所得的二分图过的边，这样所得的二分图过xi xi，yj yj的边可能不的边可能不止一条。问题变为对所得二分图止一条。问题变为对所得二分图GG的边着色问题。有相的边着色问题。有相同颜色的边可以安排在同一时间里。同颜色的边可以安排在同一时间里。一、边的着色问题一、边的着色问题3n n定理：二分图G的边色数图中顶点的最大度。x1x2y1x3x4x5y2y3y4y5一、边的着色问题一、边的着色问题3n n定理(Vizing 1964)：若图G为简单图，图中顶点最大度为d，则G的边色数为d或d+1。x1x2y1x3x4x5y2y3y4y5单星妖怪第一类图第一类图第二类图第二类图目前仍无有效区分目前仍无有效区分(判别判别)任给定图属任给定图属第几类图的有效方法。第几类图的有效方法。一、边的着色问题一、边的着色问题4n n边的着色问题可以转化为顶点的着色问题。二、顶点的着色问题二、顶点的着色问题n n定义：给图G的顶点着色，使得相邻的顶点异色的最少颜色数，称为图图G顶色数顶色数，简称色数色数；记作(G)。(G)=2二、顶点的着色问题二、顶点的着色问题四色猜想：平面图的色数不大于5。一、边的着色问题一、边的着色问题n n课程考试安排；用顶点v1,v2,vn表示n门课程，若其中两门课i,j被同时选，则vi,vj间连一条边。考试安排问题相当于图的顶点染色问题，着同一颜色的顶点对应的课程可以同时进行考试，使图的相邻顶点有不同颜色的最少颜色数目，便是进行考试的最少场次。n n物资存储问题；6.2 排课表问题排课表问题 n n问题问题问题问题 mm位教师和位教师和n n个班级，其中教师个班级，其中教师X Xi i要给班级要给班级Y Yj j上上pij ij节课。欲在最少节次节课。欲在最少节次p p内排完所有的课。内排完所有的课。n n 将偶图将偶图G=(X,Y,E)G=(X,Y,E)的边集的边集E E划分成互不相交的划分成互不相交的p p个匹配个匹配(E1(E1，Ep)Ep)，且使，且使p p为最小，其中为最小，其中 X=xX=x1,1,x xmm,Y=y,Y=y1 1,y,yn n n n 求偶图求偶图GG的的p-p-边着色，其中边着色，其中p=p=。n n由习题由习题6.1.46.1.4知，上述问题有好算法。知，上述问题有好算法。n n当上述问题中教室数有限时（当上述问题中教室数有限时（教室数教室数 ），），若要在若要在 p p（）节内排完全部（）节内排完全部（l l=E E）节课，所）节课，所需教室数需教室数c c n n问题问题问题问题 能否适当排课，使全部节课在能否适当排课，使全部节课在p p（）节）节内排完，且每节课所用教室数内排完，且每节课所用教室数？n n（1 1 i i p p）6.2 排课表问题排课表问题 n n引理引理引理引理6.3 6.3 设设MM，NN为为GG的二不相交匹配，且的二不相交匹配，且 MM NN，则存在，则存在GG的二不相交匹配的二不相交匹配MM，NN 使使 MM =MM-1-1，NN =NN+1+1，且，且MM NN =M=M N N。n n证明：令证明：令H=GM H=GM NN，则，则HH的每个分支为一路或的每个分支为一路或圈，由圈，由MM及及NN的边交错组成。且由于的边交错组成。且由于 MM NN ，存，存在在HH的一个分支，它是路的一个分支，它是路P P，起、止于，起、止于M M 边。因此边。因此 MM =M =M E(P)E(P)及及 NN =N =N E(P)E(P)即为所求。即为所求。n n定理定理定理定理6.36.3 设设GG为偶图，为偶图，p p ，则存在，则存在GG的的p p个互个互不相交的匹配使不相交的匹配使 E=M1 E=M1 Mp Mp。n n且且 ,1,1 i i p p。6.2 排课表问题排课表问题 n n证明：由定理证明：由定理6.1,E6.1,E可划分为可划分为 个互不相交的匹配个互不相交的匹配M1M1，MM 。因此，对因此，对p p ，GG有有p p个互不相交的匹配个互不相交的匹配M1M1，MM，MpMp。（令（令MiMi=当当i pi p）使使E=M1E=M1 Mp Mp 。今对边数差。今对边数差 1 1的两的两个匹配，反复使用引理个匹配，反复使用引理6.36.3，最后可得所求的匹配，最后可得所求的匹配M1M1，Mp Mp。n n注注注注 在实际应用中，教师和班级往往会提出一些，在实际应用中，教师和班级往往会提出一些，例如所上节次时间的要求，问题变得很复杂。例如所上节次时间的要求，问题变得很复杂。EvenEven，Itai&ShmirItai&Shmir（19761976）证明：在教师和班级）证明：在教师和班级提出条件时，判定课表的存在性问题是个提出条件时，判定课表的存在性问题是个NP-NP-completecomplete问题。甚至当问题。甚至当GG为简单偶图，且学生不提为简单偶图，且学生不提出要求的情况下，也是如此。出要求的情况下，也是如此。二、顶点的着色问题二、顶点的着色问题1n n色数的性质：（1）图G只有孤立点时，(G)=1；（2）n个顶点的完全图G有(G)=n；二、顶点的着色问题二、顶点的着色问题1（3）若图G是n个顶点的回路，则 (G)=2 n为偶数 =3 n为奇数；二、顶点的着色问题二、顶点的着色问题1（4）图G是顶点数超过1的树时，(G)=2；二、顶点的着色问题二、顶点的着色问题1（5）若图G是二分图，则(G)=2。x1x2y1x3x4x5y2y3y4y5二、顶点的着色问题二、顶点的着色问题2n n定理：图G=(V,E)的色数(G)=2的充要条件是：(1)|E|1；(2)G不存在边数为