1、匹配与覆盖匹配与覆盖1工作安排问题工作安排问题2匹配与覆盖及其应用匹配与覆盖及其应用系统监控问题系统监控问题3建模案例：锁具装箱问题建模案例：锁具装箱问题4一、匹配与覆盖一、匹配与覆盖1、基本概念、基本概念定义定义1 设图设图(,),GV EME 若若M的边互不相邻，则称的边互不相邻，则称M是是G的一个的一个匹配匹配。M的边称为匹配边，的边称为匹配边， EM的边称为的边称为自由边自由边。若若( , ),u vM 则称则称u(或或v)是是v(或或u)的的配偶配偶。若顶点。若顶点v与与M的一的一条边关联，则称条边关联，则称v是是M-饱和的饱和的；否则称为是；否则称为是M-非饱和的非饱和的。设。设M
2、是是G的一个匹配，若的一个匹配，若G的每个顶点都是的每个顶点都是M-饱和的，则称饱和的，则称M是是G的的完美完美(理想理想)匹配匹配。设。设M是是G的一个匹配，若不存在匹配的一个匹配，若不存在匹配M 使使,MM 则称则称M为为G的的最大匹配最大匹配。说明说明 显然，显然，完美匹配一定是最大匹配，反之不一定成立完美匹配一定是最大匹配，反之不一定成立。 (a)所示的匹配所示的匹配(匹配边用粗线表示，下同匹配边用粗线表示，下同)是最大匹配但不是是最大匹配但不是完美匹配，实际上该图没有完美匹配。完美匹配，实际上该图没有完美匹配。 (b)所示匹配是完美匹配，也是最大匹配。所示匹配是完美匹配，也是最大匹配
3、。(a)最大匹配最大匹配(b)完美匹配完美匹配1、基本概念、基本概念定义定义2 设设M是图是图G=(V,E)的匹配，称其边交错于的匹配，称其边交错于M和和EM的路的路(圈圈)为为M-交错路交错路(圈圈)。起点和终点都是。起点和终点都是M-非饱和点的交错路非饱和点的交错路称为称为M-增广路增广路。定义定义3 设设( ,),GV EKV 若若G的每条边都与的每条边都与K的一个的一个顶点关联，则称顶点关联，则称K是图是图G的一个的一个覆盖覆盖。设。设K是是G的一个覆盖，的一个覆盖，若不存在覆盖若不存在覆盖K 使使,KK 则称则称K是一个是一个最小覆盖最小覆盖。2、性质、性质定理定理1 设设M是图是图
4、G的匹配，则的匹配，则M是最大匹配的充要条件是，是最大匹配的充要条件是，G没有没有M-增广路。增广路。此定理提供了求最大匹配的基本思想和方法。此定理提供了求最大匹配的基本思想和方法。定理定理2 设设M是图是图G的匹配，的匹配，K是覆盖，则：是覆盖，则：(1);MK (2)若若,MK 则则M是最大匹配，是最大匹配，K是最小覆盖。是最小覆盖。3、二元图的匹配、二元图的匹配 关于匹配的一般性质对二元图自然也成立，但二元图的关于匹配的一般性质对二元图自然也成立，但二元图的匹配还有自身的重要性质，即：匹配还有自身的重要性质，即：定理定理3 设设G=(X,Y,E)是二元图，是二元图，M是匹配，是匹配，K是
5、覆盖，则是覆盖，则M,K分别是最大匹配、最小覆盖的充要条件是：分别是最大匹配、最小覆盖的充要条件是：.MK 定理定理4 对二元图对二元图G=(X,Y,E)，有：，有：(1)G存在饱和存在饱和X的每个顶点的匹配的充要条件是的每个顶点的匹配的充要条件是(),(),N SSSX N SvuS vu 与 相邻(2)G存在完美匹配存在完美匹配(),N SSSV , ( ), ( ),tvX d vtuY d ut Z Z(3)则存在则存在饱和饱和X的每个顶点的匹配。的每个顶点的匹配。1x2x3xXY1y2y3y4y下图是否存在最大匹配？下图是否存在最大匹配？定理定理3 设设G=(X,Y,E)是二元图，是
6、二元图，M是匹配，是匹配，K是覆盖，则是覆盖，则M,K分别是最大匹配、最小覆盖的充要条件是：分别是最大匹配、最小覆盖的充要条件是：.MK 1x2x3xXY1y2y3y4y下图是否存在完美匹配？下图是否存在完美匹配？定理定理4 对二元图对二元图G=(X,Y,E)，有：，有：(1)G存在饱和存在饱和X的每个顶点的匹配的充要条件是的每个顶点的匹配的充要条件是(),(),N SSSX N SvuS vu 与 相邻(2)G存在完美匹配存在完美匹配(),N SSSV , ( ), ( ),tvX d vtuY d ut Z Z(3)则存在则存在饱和饱和X的每个顶点的匹配。的每个顶点的匹配。【例】【例】如图
7、所示，如图所示，M是二元图是二元图G的最大匹配，的最大匹配，123,Kx xx 因为因为3MK所以所以K是是G的最小覆盖。的最小覆盖。又因为又因为,SX( ),N SS 因此存在饱和因此存在饱和X的所有顶点的匹配的所有顶点的匹配(或取或取t=3,利用利用定理定理4中中(3)的结论的结论);但对于但对于,( )NSVSS 不成立，如取不成立，如取1234123,( ),( )SyyyyN SxxxN SS ,因此不存因此不存在完美匹配。在完美匹配。1x2x3xXY1y2y3y4y二、工作安排问题二、工作安排问题1、工作安排问题之一、工作安排问题之一 假设有：假设有：n个工人个工人 n件工作件工作
8、1212:,:,nnx xxyyy已知工人已知工人ix能胜任能胜任ik件工作件工作(i=1,2, ,n),问能否问能否存在存在一种安排使每人能分配到他所能胜任的一件工作，若能，一种安排使每人能分配到他所能胜任的一件工作，若能，如何安排？如何安排？即：找到一个方案即可，不即：找到一个方案即可，不妨寻找完美匹配。妨寻找完美匹配。【分析】【分析】设顶点集设顶点集X= 顶点集顶点集Y=1212,nnx xxyyyiiiixyxy与 相邻能胜任工作由此得到二元图由此得到二元图G=(X,Y,E),问题转化为二元图的完美匹配。问题转化为二元图的完美匹配。因为因为,XY 因此完美匹配即为最大匹配。因此完美匹配
9、即为最大匹配。匈牙利（匈牙利（Hungarian）算法）算法求二元图的最大匹配。求二元图的最大匹配。匈牙利（匈牙利（Hungarian）算法）算法 求二元图的最大匹配。求二元图的最大匹配。基本思想基本思想 任选取一个匹配任选取一个匹配M，对，对X的所有的所有M-非饱和点，寻找非饱和点，寻找M-增广增广路，若不存在路，若不存在M-增广路，则增广路，则M为最大匹配；若存在为最大匹配；若存在M-增广路，增广路，则将则将M-增广路中增广路中M与非与非M的边互换，得到比的边互换，得到比M多一边的多一边的,M 再对再对M 重复上述过程。重复上述过程。定理定理1 设设M是图是图G的匹配，则的匹配，则M是最大
10、匹配的充要条件是，是最大匹配的充要条件是，G没有没有M-增广路。增广路。此定理提供了求最大匹配的基本思想和方法。此定理提供了求最大匹配的基本思想和方法。算法步骤算法步骤设设G=(X,Y,E) 是二元图，是二元图，M是一个匹配是一个匹配1)令令,;ST 2)若若M饱和饱和XS的每个顶点，则的每个顶点，则M是最大匹配。否则，取是最大匹配。否则，取M-非饱和点非饱和点,uXS 令令 ;SSu 3)若若( ),N ST 转转6). 否则，取否则，取( ).yN ST 若若y是是M-饱和点，转饱和点，转4),否则转否则转5);4)设设( , ),y xM 则令则令 , ,SSx TTy 转转3);5)u
11、-y路是路是M-增广路，设为增广路，设为P，并令，并令MMP转转1);6)若若,XS 则则M是最大匹配，否则转是最大匹配，否则转2).2、工作安排问题之二、工作安排问题之二 假设有：假设有：n个工人个工人 n件工作件工作1212:,:,nnx xxyyy若工人若工人ix担任工作担任工作jy的效率为的效率为( ,1,2, ),ijwi jn 对每人分配一件工作，使总效率最大。对每人分配一件工作，使总效率最大。 设顶点集设顶点集1212,nnXx xxYyyy 以以ijw为边为边(,)ijxy的权，作赋权完备二元图的权，作赋权完备二元图G=(X,Y,E),则问题转化为：在赋则问题转化为：在赋权完备
12、二元图中，求权最大的饱和权完备二元图中，求权最大的饱和X顶点的完美匹配顶点的完美匹配最佳匹配。最佳匹配。分析分析算法算法Kuhn-Munkres可行顶点标号法：求赋权完备二可行顶点标号法：求赋权完备二元图的元图的X的最佳匹配。的最佳匹配。定义定义1设赋权完备二元图设赋权完备二元图G=(X,Y,E)的每个顶点的每个顶点vV 对应一个实数对应一个实数( ),L v若满足：若满足：( )( )( , ),L xL yw x yxX yY 其中其中w(x,y)是边是边(x,y)的权，则称的权，则称L为为G的一个可的一个可行顶点标记。行顶点标记。设设L为可行顶点标记，则称相应的生成子图为可行顶点标记，则
13、称相应的生成子图( ,)lGV E ( , )( )( )( , )lEx yE L xL yw x y 定理定理1 设设L是赋权完备二元图是赋权完备二元图G=(X,Y,E)的可行顶点标记的可行顶点标记lG是相等子图，若是相等子图，若*M是是lG的完美匹配，则的完美匹配，则*M是是G的的最佳匹配。最佳匹配。此定理提供了求最佳匹配的算法的基本思路和方法。此定理提供了求最佳匹配的算法的基本思路和方法。算法基本思想算法基本思想通过对顶点标记将赋权图转化为非赋权图，再用通过对顶点标记将赋权图转化为非赋权图，再用Hungarian算法求最大匹配，若求出的匹配为完美匹配，则停止；否算法求最大匹配，若求出的
14、匹配为完美匹配，则停止；否则，改进顶点标记，重新计算。则，改进顶点标记，重新计算。算法的具体步骤算法的具体步骤 设设G=(X,Y,E)，每条边，每条边e=(x,y)有权有权w(e)或记为或记为w(x,y),L是一个初始可行顶点标记，通常取是一个初始可行顶点标记，通常取( )max ( , ),( )0,L xw x y yYxXL yyY M是相等子图是相等子图lG的一个匹配。的一个匹配。1）若）若X的每个顶点都是饱和的，则的每个顶点都是饱和的，则M是最佳匹配。否则取是最佳匹配。否则取M-非饱和点非饱和点,uX 令令 ,Su T 3）调整标记，计算）调整标记，计算 ( )( )( , ),la
15、min L xL yw x y xS yT 由此得新的可行顶点标记由此得新的可行顶点标记( ),( )( ),( ),llL va vSL vL va vTL velse 令令,;llLL GG 2）若）若( ),lGNST 则则lG没有完美匹配，转没有完美匹配，转3），否则），否则转转4）；）；4）取）取( ),lGyNST 若若y是是M-饱和点转饱和点转5），否则转），否则转6）算法的具体步骤算法的具体步骤4）取）取( ),lGyNST 若若y是是M-饱和点转饱和点转5），否则转），否则转6）5) 设设( , ),y xM 令令 , SSx TTy 转转2）6) 在在lG中的中的u-y交错
16、路是交错路是M-增广路，记为增广路，记为P，并令，并令MMP 转转1）。）。【例【例1】求赋权邻接矩阵求赋权邻接矩阵M表示的赋权完备二元图的最佳匹配。表示的赋权完备二元图的最佳匹配。M 1234yyyy1234xxxx45512246423350211x2x3x4x1y2y3y4y1.如何取初始顶如何取初始顶点标记？点标记？2.如何取相等子如何取相等子图？图？ 5 6 4 50 0 0 0( )max ( , ),( )0,L xw x y yYxXL yyY 【例【例1】求赋权邻接矩阵求赋权邻接矩阵M表示的赋权完备二元图的最佳匹配。表示的赋权完备二元图的最佳匹配。M 1234yyyy1234
17、xxxx4551224642335021取初始可行顶点标记如表取初始可行顶点标记如表1（左），右上角打（左），右上角打“*”的元素表的元素表示示( )( )( , )L xL yw x y 作出相等子图作出相等子图lG并任给并任给lG的匹配的匹配M，如图，如图11x2x3x4x1y2y3y4y0000*4551224642335021( )L y( )L x5645( )L y( )L x5634*45512246423350211000表表11x2x3x4x1y2y3y4y作相等子图作相等子图的匹配的匹配按步骤：按步骤：41),;SxT 1234xxxx1234yyyy图图114)( );l
18、GyNST 134315)(,),;y xM SxxTy 2)( );lGNST 调整标记调整标记3）调整标记，计算）调整标记，计算 ( )( )( , ),lamin L xL yw x y xS yT 由此得新的可行顶点标记由此得新的可行顶点标记( ),( )( ),( ),llL va vSL vL va vTL velse 令令,;llLL GG 34,xx1y0000*4552331224645021( )L y( )L x5645( )L y( )L x5634*455122464332502110001la( ),( )( ),( ),llL va vSL vL va vTL v
19、else 3)计算计算11,a 经调整得新的可行顶点标记如表经调整得新的可行顶点标记如表1（右），（右），相应作出新的相等子图相应作出新的相等子图2G而匹配而匹配M没有改变如图没有改变如图2，继，继续迭代；续迭代；1234xxxx1234yyyy图图2234)( );GyNST 1234xxxx1234yyyy图图31234xxxx1234yyyy图图24133122433416),(,),(,),(,),(,)Px y x yMMPxyxyxyxy 改进匹配改进匹配M备注备注4133122433416),(,),(,),(,),(,)Px y x yMMPxyxyxyxy 改进匹配改进匹配M
20、()()MPMPMP 411333,x yy xx y122431,x yx yx y1234xxxx1234yyyy图图3则则X的每个顶点都是饱和的，所以当前匹配是最佳匹配，即的每个顶点都是饱和的，所以当前匹配是最佳匹配，即12243341(,),(,),(,),(,)Mxyxyxyxy 其权为：其权为：12243341()19w Mwwww 三、系统监控问题三、系统监控问题1、系统监控问题之一、系统监控问题之一例例1 在城市街道中，需要在街道口设立岗亭，以便监在城市街道中，需要在街道口设立岗亭，以便监控和指挥过往交通。为了监控所有街道，问至少要设立多控和指挥过往交通。为了监控所有街道，问至
21、少要设立多少岗亭？少岗亭？分析问题分析问题 用一个连通图来模拟城市街道系统，在某街道口设岗用一个连通图来模拟城市街道系统，在某街道口设岗亭，即把相应的顶点作为监控点而监控所关联的所有边，亭，即把相应的顶点作为监控点而监控所关联的所有边，因此，例因此，例1的问题就是一个的问题就是一个“顶点监控边顶点监控边”的问题。换言的问题。换言之，需在一个连通图之，需在一个连通图G中找顶点子集中找顶点子集( ),KV G 使每条使每条边都与边都与K的一个顶点关联，且的一个顶点关联，且K是满足这个性质的顶点最少是满足这个性质的顶点最少的集，也就是求连通图的集，也就是求连通图G的最小覆盖。的最小覆盖。 设想把顶点
22、度数最大的顶点作为监控点，则能监控更设想把顶点度数最大的顶点作为监控点，则能监控更多的边，这是一个合理的想法。多的边，这是一个合理的想法。 求连通图的最小覆盖没有有效算法，可以用逻辑算求连通图的最小覆盖没有有效算法，可以用逻辑算法，但随着顶点数的增加，逻辑算法的复杂性成指数倍增法，但随着顶点数的增加，逻辑算法的复杂性成指数倍增长，因此逻辑算法只适用顶点较少的情况。由于实际问题长，因此逻辑算法只适用顶点较少的情况。由于实际问题中，顶点数一般较多，下面介绍求最小覆盖的近似算法，中，顶点数一般较多，下面介绍求最小覆盖的近似算法，即启发式算法。即启发式算法。说明说明设想一下，你会选择那些点作为监控点设
23、想一下，你会选择那些点作为监控点算法步骤算法步骤最小覆盖的启发式算法最小覆盖的启发式算法设设G是连通图，用是连通图，用K表示所求的最小覆盖。令表示所求的最小覆盖。令.K 1)若若(),V G 停。否则取停。否则取( ),uV G 使使( )max ( )( )d ud v vV G当当u的选取不唯一时，可能导致不同的结果，因此，必要的选取不唯一时，可能导致不同的结果，因此，必要时应比较所有的结果。通常只能得到最小覆盖的近似覆盖。时应比较所有的结果。通常只能得到最小覆盖的近似覆盖。2)令令 ,KKu GGu 转转1).例例2求下图的最小覆盖。求下图的最小覆盖。123456cccccc123456
24、bbbbbb1234567aaaaaaa按每次取顶点度数最大的顶点，可依次选取：按每次取顶点度数最大的顶点，可依次选取：7654321123456,a a a a a a a c c c c c c故得故得7654321123456,Ka a a a a a a c c c c c c 例例2求下图的最小覆盖。求下图的最小覆盖。123456cccccc123456bbbbbb1234567aaaaaaa另一方面，我们仍按每次取顶点度数最大的顶点，又可得另一方面，我们仍按每次取顶点度数最大的顶点，又可得123456,Kb b b b b b 【求解】【求解】按每次取顶点度数最大的顶点，可依次选取
25、：按每次取顶点度数最大的顶点，可依次选取：7654321123456,a a a a a a a c c c c c c故得故得7654321123456,Ka a a a a a a c c c c c c 另一方面，我们仍按每次取顶点度数最大的顶点，又可得另一方面，我们仍按每次取顶点度数最大的顶点，又可得123456,Kb b b b b b 显然，显然，K 是最小覆盖。因为每个是最小覆盖。因为每个ib都连接着一条都连接着一条割边割边( ,),1,2,6,iib ci 即最小覆盖至少含有即最小覆盖至少含有6个点。个点。 从此例可以看出，两个顶点的度数相同时，若其中一个从此例可以看出，两个顶
26、点的度数相同时，若其中一个顶点关联着割边，应先选这一顶点，使得到的覆盖更接近顶点关联着割边，应先选这一顶点，使得到的覆盖更接近最小覆盖。最小覆盖。V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中 割边的定义割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边2、系统监控问题之二、系统监控问题之二 例例3用一连通图代表一指挥系统。顶点表示被指挥的用一连通图代表一指挥系统。顶点表示被指挥的单位，边表示可以直接下达命令的通信线路。欲在某些单单位，边表示可以直接下达命令的通信线路。欲在某些单位建立指挥
27、站，以便可以通过指挥站直接给各单位下达命位建立指挥站，以便可以通过指挥站直接给各单位下达命令，问如何建立指挥站使指挥站尽可能少？令，问如何建立指挥站使指挥站尽可能少？ 假如在某一顶点假如在某一顶点v建立指挥站，则可通过这个指挥站直接建立指挥站，则可通过这个指挥站直接给出相邻顶点（单位）下达命令。因此例给出相邻顶点（单位）下达命令。因此例3的问题就是在一的问题就是在一个监控系统中个监控系统中“顶点监控顶点顶点监控顶点”问题。换言之，需在一个问题。换言之，需在一个连通图连通图G中找顶点数最少的子集中找顶点数最少的子集( ),DV G 或者或者v在在D中，或中，或者者v与与D中某个顶点相邻。中某个顶
28、点相邻。分析分析【定义】【定义】设设G是连通图，是连通图，(),DV G 若对每个若对每个,vD 或或( ),DN v 则称则称D为图为图G的一个控制集。若的一个控制集。若D是控制集，是控制集，而而D的任何真子集都不是控制集，则称的任何真子集都不是控制集，则称D是极小控制集。顶点是极小控制集。顶点数最小的控制集称为最小控制集。最小控制集所含顶点数目数最小的控制集称为最小控制集。最小控制集所含顶点数目称为控制数，记为称为控制数，记为0( )G 或或0. 例例3就是求最小控制集问题。求最小控制集没有有效算就是求最小控制集问题。求最小控制集没有有效算法，可用逻辑算法或近似算法（即启发式算法）。法，可
29、用逻辑算法或近似算法（即启发式算法）。 设想把顶点度数越大的顶点作为监控点（即属于控制设想把顶点度数越大的顶点作为监控点（即属于控制集），则能监控更多的顶点，由此求出最小控制集。从这集），则能监控更多的顶点，由此求出最小控制集。从这一合理的想法，得到启发式算法。一合理的想法，得到启发式算法。算法步骤算法步骤最小控制集的启发式算法最小控制集的启发式算法设设G是连通图，用是连通图，用D表示所求的最小控制集。令表示所求的最小控制集。令D 1)若若(),V G 停。否则取停。否则取( ),uV G 使使( )max ( )( )d ud v vV G当当u的选取不唯一时，可能导致不同的结果，因此，必要
30、的选取不唯一时，可能导致不同的结果，因此，必要时应比较所有的结果。通常只能得到最小控制集的近似值时应比较所有的结果。通常只能得到最小控制集的近似值2)令令 , ,( ),DDu GGu N u 其中其中N(u)表示表示u的所的所有相邻顶点的集合，转有相邻顶点的集合，转1). 某厂生产一种子弹锁具，每个锁具的钥匙有某厂生产一种子弹锁具，每个锁具的钥匙有5 5个槽，每个槽个槽，每个槽的高度从的高度从1,2,3,4,5,661,2,3,4,5,66个数中任取一数，要求满足：个数中任取一数，要求满足：1.1.任意一把锁至少有三个槽高度互不相同；任意一把锁至少有三个槽高度互不相同；2.2.任意一把锁相邻
31、两槽的高度之差不能为任意一把锁相邻两槽的高度之差不能为5 5，所有互不相同的，所有互不相同的锁具称为一批。锁具称为一批。两把锁具互开当且仅当两把锁具互开当且仅当1.1.两把锁的钥匙有两把锁的钥匙有4 4个槽高度相同；个槽高度相同；2.2.其余一个槽高度相差其余一个槽高度相差1 1。 在原来一批锁具中随机取在原来一批锁具中随机取6060个装为一箱，成箱购买的顾客个装为一箱，成箱购买的顾客总抱怨购得的锁具有互开现象。如何装箱（总抱怨购得的锁具有互开现象。如何装箱（6060个为一箱），个为一箱），如何给箱子以标志，出售时如何利用这些标志，使团体顾客如何给箱子以标志，出售时如何利用这些标志，使团体顾客减少抱怨。减少抱怨。
