图的匹配问题

Published on 2016 - 06 - 25

完美匹配

完美匹配:对于一个图G与给定的一个匹配M,如果图G中不存在M的未盖点,则称匹配M为图G的完美匹配。

例如,图15(a)所示的无向图,取M={e1,e4,e7},则M是G的一个完美匹配,同时M也是图G的最大匹配及最小边覆盖。

而在图15(b)中,不可能有完美匹配,因为对任何匹配都存在未盖点。

定理4的推论 设G中顶点个数为n,且G中无孤立顶点,M为G中的匹配,W是G中的边覆盖,则—M—≤—W—,—M—表示M中边的数目。当等号成立时,M为G中完美匹配,W为G中最小边覆盖。

二部图的完备匹配与完美匹配

二部图的完备匹配:设无向图G(V,E)为二部图,它的两个顶点集合为X和Y,且—X—≤—Y—,M为G中的一个最大匹配,且—M—=—X—,则称M为X到Y的二部图G的完备匹配。若—X—=—Y—,则该完备匹配覆盖住G的所有顶点,所以该完备匹配也是完美匹配。

“例如,如图16所示的3个二部图中,图16(a)和图16(b)中取定的匹配M都是完备匹配,而图16(c)中不存在完备匹配。

二部图完备匹配的一个应用例子是:某公司有工作人员x1,x2,…,xm,他们去做工作y1,y2,y3,…,yn,n>m,每个人适合做其中一项或几项工作,问能否恰当地安排使得每个人都分配到一项合适的工作。

最佳匹配

继续对上面的应用例子进行深化:工作人员可以做各项工作,但效率未必一致,现在需要制定一个分工方案,使公司的总效益最大,这就是最佳分配问题。

二部图的最佳匹配:设G(V,E)为加权二部图,它的两个顶点集合分别为X={x1,x2,…,xm}、Y={y1,y2,…,yn}。W(xi,yk)≥0表示工作人员xi做工作yk时的效益,权值总和最大的完备匹配称为二部图的最佳匹配。

匹配问题求解的基本概念及思路

交错轨

交错轨:设P是图G的一条轨(即路径),M是图G中一个给定的匹配,如果P的任意两条相邻的边一定是一条属于匹配M而另一条不属于M,则称P是关于M的一条交错轨。

例如,在图17(a)所示的图中,取定M={e4,e6,e10},则图17(b)、17(c)所示的路径都是交错轨。

特别地,如果轨P仅含一条边,那么无论这条边是否属于匹配M,P一定是一条交错轨。

可增广轨

可增广轨:对于一个给定的图G和匹配M,两个端点都是未盖点的交错轨称为关于M的可增广轨。

例如,图17(b)所示的交错轨的两个端点v2、v11都是匹配M的未盖点,所以这条轨是可增广轨,而图17(c)所示的交错轨不是可增广轨。

特别地,如果两个未盖点之间仅含一条边,那么单单这条边也组成一条可增广轨。

可增广轨的含义。对于图G的一个匹配M来说,如果能找到一条可增广轨P,那么这个匹配M一定可以通过下述方法改进成一个多包含一条边的匹配Ms(即匹配M扩充了):把P中原来属于匹配M的边从匹配M中去掉(粗边改成细边),而把P中原来不属于M的边加到匹配Ms中去(细边改成粗边),变化后的匹配Ms恰好比原匹配M多一条边。

例如,对图17(a)中G的一个匹配M,找到图18(a)所示的一条可增广轨,那么按照前面所述的方法可以将原匹配进行扩充,得到图18(b)所示的新匹配Ms,Ms比M多一条边。

求最大匹配的可行方法

定理5 M为G的最大匹配,当且仅当G不存在关于M的可增广轨。

因此,求最大匹配的一个可行方法如下。

给定一个初始匹配M(如果没有给定,则M=),如果图G没有未盖点,则肯定不会有可增广轨了,即M就是最大匹配;否则对图G的所有未盖点vi,通过一定的方法搜索以vi为端点的可增广轨,从而通过可增广轨逐渐把M扩大。(在扩大M的过程当中,某些未盖点会逐渐被M盖住)

参考文档

图论算法理论、实现及应用 第七章 支配集、覆盖集、独立集与匹配