匹配问题及其应用

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