二部图最大匹配问题的求解

Published on 2016 - 06 - 25

网络流解法

基本思路

设二部图为G(V,E),它的顶点集合V所包含的两个子集为X={x1,x2,…,xm}和Y={y1,y2,…,yn},如图19(a)所示。如果把二部图中看成一个网络,边(xi,yk)都看成有向边<xi,yk>,则在求最大匹配时要保证从顶点xi发出的边最多只选一条,进入顶点yk的边最多也只选一条,在这些前提下将尽可能多的边选入到匹配中来。

设想有一个源点S,控制从S到xi的弧<s,xi>的容量为1,这样就能保证从顶点xi发出的边最多只选一条。同样,设想有一个汇点T,控制从顶点yk到T的弧<yk,t>的容量也为1,这样就能保证进入顶点yk的边最多也只选一条。另外,设边<xi,yk>的容量也为1。

按照上述思路构造好容量网络后,任意一条从S到T的路径,一定具有S-xi-yk-T的形式,且这条路径上3条弧<s,xi>、<xi,yk>、<yk,t>的容量均为1。因此,该容量网络的最大流中每条从S到T的路径上,中间这一条边<xi,yk>的集合就构成了二部图的最大匹配。

网络流的构造及求解

求二部图最大匹配的容量网络构造和求解方法如下。

  • 从二部图G出发构造一个容量网络G′,步骤如下。
    ①增加一个源点S和汇点T。
    ②从S向X的每一个顶点都画一条有向弧,从Y的每一个顶点都向T画一条有向弧。
    ③原来G中的边都改成有向弧,方向是从X的顶点指向Y的顶点。
    ④令所有弧的容量都等于1。构造好的容量网络如图19(b)所示。

  • 求容量网络G′的最大流F。

  • 最大流F求解完毕后,从X的顶点指向Y的顶点的弧集合中,弧流量为1的弧对应二部图最大匹配中的边,最大流F的流量对应二部图的最大匹配的边数。

为什么这样构造的容量网络求出来的最大流就是最大匹配?这是因为:①网络中所有的弧容量均为1,这样原二部图G中的边,要么选择(流量为1),要么不选择;②尽管在网络中顶点xi可能发出多条边,但在最大流中只能选择一条边,因为从源点S流入顶点xi的流量为1;③尽管在网络中可能有多条边进入顶点yk,但在最大流中只能选择一条边,因为从顶点yk流入汇点T的流量为1。

以上第②、③点保证了最大流F中属于二部图的边不存在共同顶点。

网络流解法实例

设有5位待业者,用x1,x2,x3,x4,x5表示;另外有5项工作,用y1,y2,y3,y4,y5表示;如果xi能胜任yi工作,则在他们之间连一条边。图20(a)描述了这5位待业者各自能胜任工作的情况,很明显,这是一个二部图。现在要求设计一个就业方案,使尽量多的人能就业。这是求二部图最大匹配的问题。

按照前面描述的方法构造网络流:在二部图中增加两个顶点S和T,分别作为源点、汇点;并用有向边把它们与原二部图中顶点相连,令全部边上的容量均为1,如图20(b)所示。当网络流达到最大时,如果在最大流中弧<xi,yj>上的流量为1,就让xi作yj工作,此即为最大匹配方案。图20(c)是求网络最大流的结果。在图20(d)中,粗线所表示的边就是求得的最大匹配,x1,x2,x3,x4分别做y2,y1,y4,y5工作,故最多可安排4个人工作。

匈牙利算法

匈牙利算法的原理为:从当前匹配M(如果没有匹配,则取初始匹配为M=φ)出发,检查每一个未盖点,然后从它出发寻找可增广路,找到可增广路,则沿着[…]”

....