1、第四章 匹配问题及其应用一、匹配理论概念及基本性质（1）定义：1、设 M 是图 G 的边子集，称 M 是 G 中的一个匹配，若 M 中任二边在 G 中不相邻；M 中的每条边的两个端点称为在 M 中相配；M 中每边的端点称为被 M 许配；称 M 为 G 的一个完全匹配，若 G 中每个顶点皆被 M 许配；称 G 的最大匹配，若对任意的 G 的匹配 ，均有 。2、权数：对于匹配 M，它的权数为 。Me3、称 M 为最优匹配，若 M 为所有匹配中权数最大的匹配。4、称 P 为关于匹配 M 的可扩路：设 M 是图 G 的一个匹配，若路 P 的边在 M中交替出现，且 P 的两个端点是 M 不饱和的。5、称
2、 B 是 G 的一个覆盖集：设 ，若 G 的每条边皆与 B 中的顶相关联。VB6、称 B 是 G 的极小覆盖：设 ，若 B 是 G 的一个覆盖集，但 ，v不再是 G 的覆盖集。v7、称 B 为 G 的最小覆盖：设 ，若 B 是 G 的顶数最小的覆盖集。V8、G 的覆盖数：最小覆盖中顶的数目，记作 。9、A B 为 A 与 B 的对称差：A B= ，其中 A、 B 为集合，有A时也写成 。（2）基本性质：1、M 是图 G 中的一个最大匹配当且仅当 G 中无 M 的可扩路。2、设 G 是二分图，顶集的二分图划分为 X 与 Y，满足 ；YXV ；X 中的任两点不相邻，Y 中亦然； ，记 ；nX则存在
3、把 X 中点皆许配的匹配的充要条件是 ， ，其中XSSN)(是 S 中每个点的邻点组成的所谓 S 的邻集。)(N求 G 的最大匹配 M 的算法：Step1：任取 G 的匹配 M；Step2：若 ，则 M 为 G 的最大匹配，算法终止；n若不存在 M 的可扩路，则 M 为 G 的最大匹配，算法终止。否则转到 Step3；Step3：取 M 的可扩路 P，作 。PEEg：求图 G 的最大匹配。5,432M路 P：123456作 =E MPE=6,543,21Step1：取 ,yxM取 12P 上一边在 M 中交叉出现 、 都是 M 不饱和的2x1y是关于 M 的可扩路。P作 =11E12,yxSt
4、ep2：对于 ， 也是可扩路。M23xyP作 = =2E3211,yxStep3：对于 , 也是可扩路。453xy作 = =P5432121 ,XM3、k 次正则 2 分图有完备匹配，k0。4、若 G 为二分图，则其最大匹配的边数为 。G5、图 G 有完备匹配当且仅当 ， ，其中 是VSSSG中奇数个顶的连通片的个数。S6、无桥三次正则图有完备匹配（所谓桥是一条边 ，使得 的连通Eee片增加） 。7、设 是具有正常顶标 l 的加权图，取 G 的边子集GKn, xywlxExyl ,令 是以 为边集的 G 的生成子图，如果 有完备匹配 M，则 M 即为 GllEl的最佳匹配。8、 是可以 1 因
5、子分解的， 。nK2 1n9、 存在每个因子皆生成圈的 2 因子分解，共计 n 个生成圈。二、匹配问题的应用图论中涉及的匹配问题无论是在实际生活中还是在学习工作中都有着极其广泛的应用。应用一：回顾这一章开头提出的毕业生应聘问题，设 n 名毕业生为 ，m 家nv,.21招聘公司为 。我们造一个二分图 G， ，X 、Y 是 G 的二mu,.21 EVU分图顶划分，其中， ，nvX,.21muY,.21仅当 可以接受的公司为 之间连一条边，如此构成一个应聘图G 。我们欲给ivju出一个有效算法，求得上述二分图G中的最大匹配。与此问题相似的问题很多，例如某城市有 n 名姑娘，m 名小伙子都到了结婚的年
6、龄，其中一些异性年轻人互相已有友情，但姑娘们不愿轻率处理自己的终身大事，她们排除了一些小伙子作为自己的终身伴侣，这样她们实际上手头（心头）有一份可嫁的名单，问最多有多少位姑娘可以嫁给她如意的人选？为解决诸如此类的问题，1965 年匈牙利数学家埃德蒙兹（Edmonds ）为之设计了一种命名为“匈牙利算法”的有效算法。1、匈牙利算法：（1） 设 G 是连通的二分图，在 G 中任取初始匹配 M；（2） 若 M 把 X 中顶皆许配，止；否则取 X 中未被 M 许配的顶 ,令 ；uTS,（3） 若 ，止，G 中无完备匹配；TSN否则取 ；y（4） 若 y 被 M 许配，设 ，转（ 3） ；ySyz,否则
7、取可增广轨 ，令 ，转（2） 。up, PE匈牙利算法实例应用（摘自 2011 高教社杯全国大学生数学建模竞赛 B 题）：问题重述：（问题中地图取自重庆市部分地图）现就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的5 个问题：.根据该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况示意图，为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。.对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多
8、封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。.根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，请确定需要增加平台的具体个数和位置。.针对全市（主城六区 A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。.如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。第二问的求解就是对“匈牙利
9、算法”的应用对于，本文从 20 个交巡警服务平台中选出 13 个平台封堵交通要道的思想出发，首先求出封堵的最短时间，然后依据匈牙利算法，并针对该问题进行适当改进，最后得出了最优调度方案，具体方法如下：先在图中找出 13 条交通要道的路点集合G=12 ，14，16，21，22 ，23，24，28，29，30， 38，48，62根据 Floyed 算法，求得每个交通平台到各点的最短距离。根据匈牙利算法可以在该问题中虚拟 个交通要道，并且每个平台到这 个虚拟交通要道点的77距离均为 ，这样就可以把问题转化为 个交通平台分配到 个交通要道点2020的问题，由此得到改进后的匈牙利算法。并得到分配方案如下
10、表所示：警力移动到相应的 13 条交通要道点238 462 548 630 729 916 10121122 1224 1323 1421 1528 1614并求得最小距离是 8.01546 千米，也就是最少经过 8.01546 分钟实现封锁。把以上的匈牙利算法稍加修改就能够用来求二分图的最大完备匹配。 最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图G 的每边加了权，表示 做 工作的效益，求加权图G 上的权最大的完备匹配。 0),(jiyxixjy解决这个问题可以用库恩曼
11、克莱斯（Kuhn-Munkres）算法。2、KM 算法：（1）选定初始可行顶点标号 ，确定 ，在 中取定初始匹配 M；lllG（2）若X中顶点皆被M许配，停止，M即G的权最大的完备匹配；否则，取 中未被M许配的顶点 ，令 ， ；l uST（3）若 ，转（4） ，若 ，取TSNlG)(NlG)()(min, xyxlySxl 其 他,)(_TvSll（5） 选 中一顶点 ，若 已被M许配，且 ，TSNlG)(yMyz， ，转（3） ；否则，取 中一个M的可扩路zlG，令 ，转（2） 。),(yup)(pE其中 是 中 的相邻顶点集。SlGlKM算法实例应用例如 的全矩阵为 ， 的元素 ， ， 。
12、5，KW),(jiijyx51ij31200453取正常初始顶点：，5,43,0)(iyli，51,maxa151 jjx，20)(22jjl，4,3513jj，1axa)(44 jjxl.3,2m515jj构造 如下图所示，图中粗实线是 上的最大匹配M， 无完备匹配，其顶lGlGlG标需要修改。取未被M许配的顶点 ， ， ，这时 ，取4x,134xS,23yTTSNlG)(1)()(min, xlTyxl 修改后的顶标为 ， ， ， ， ，)(1_l2_3_l04_l3)(5_xl， ， ， ， 。0)(1_yl2y3y0)(4y)(5y对于 ，得 如下图所示，其上的粗实线是 上的完备匹配，
13、从而由基本性质lGlG7，我们以找到加权图 上的一个最佳匹配 。5，K ,52431241yxyxM应用二：初中数学竞赛1. 动物运动会进行龟兔 100m2 跑，每只乌龟认识 10 只兔子，每只兔子认识10 只乌龟。龟兔们都要求和自己的朋友组队（每队一龟一兔）参赛，问是否能如愿？若能如愿，这种比赛能进行几轮，使得每轮比赛每只龟兔都去参赛，且每对龟兔至多只许参赛一次。2. 国际象棋棋盘上剪掉对角线端点的两个小方格后，能否用 12 的长方形纸片单层覆盖？假设每个小方格边长为 1。3. 从国际象棋棋盘上选出 16 个格子，使得每行每列含有其中两个格，求证：把 8 个白子和 8 个黑子放在所选的格子上，每格一子，可使每行每列恰有一个白子，一个黑子。
