算法与acm

二分匹配,最大流,匈牙利图形解释及证明

2008年12月10日 阅读(825)

转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/709717672008111064351431/

很明显,对于算法的证明过程的理解有助于算法本身的理解。

关于二分图,算法的流程在这篇blog里讲的很清楚,很多算法都结合了图形,所以讲讲得很易懂,推荐一下

http://imlazy.ycool.com/post.1603708.html

在这里还是主要关注一下关于这些问题的一些定理的证明的理解。(更详细的内容可以参考<<图论及其算法>>王树禾著)

一.匈牙利算法的证明:

关于二分匹配,涉及到了一些定理(Berge, Hall ,Konig, Tutte):这里主要论述定理1,因为它对匈牙利算法的证明

最有用。

定理1:(Berge 1957)M是最大匹配的充要条件是G中无M的可增广轨(关于增广轨可以参考上面那个blog里的说明)。

定理2:如果从一个点A出发,没有找到增广路径,那么无论再从别的点出发找到多少增广路径来改变现在的匹配,从A出发都永远找不到增广路径。

利用定理2,可以对匈牙利算法进行改进,避免点的重复搜索,而定理2的证明实际上与1使用了同样的思想。

定理1证明:

必要性:如果M是最大匹配,则G中无M的可增广轨。

假设M存在一条增广轨,显然如果把增广轨上的边取反(即把在匹配里的边删除,不在匹配里的边加入匹配),根据增广路的性质,很明显得到的这个新的匹配会比原来的匹配大。

充分性:G中无M的可增广轨,则M是最大匹配。

假设M不是最大匹配,则说明存在比M更大的一个匹配M",则取H ={M并M" – M交M"},则H里,顶点的度不是1就是2.不存在度为0的顶点。则H的连通片,或者是M"与M中的边交替出现的一个偶圈,或者是M"与M中的边交替出现的一条轨。又因为|M"| > |M|,必有H的某个连通片是轨,且此轨是M"的边为终止边(实际上包含起边和终边),于是得到了M的可增广轨,与M中无增广轨矛盾。

下面用图说明:

 二分匹配,最大流,匈牙利图形解释及证明 - 星星 - 银河里的星星

观察图中,设M是黑色边代表,的匹配,M"是绿色的那些。H ={M并M" – M交M"},实际是是用它们的并集,去除交集,实际上就是集合中对称差的概念。得到如下,H

 二分匹配,最大流,匈牙利图形解释及证明 - 星星 - 银河里的星星

可以发现,图中有两个连通片,{1,6,2,7,3} {4,8},其实这是最明显的情况,因为{4,8}只含有来自M"的边,明显的可以成为M的一条可增广轨。增广轨实际上对长度并没有要求,只是要求首尾不在匹配中,中间的匹配不匹配的边交替出现,并且不匹配的在两边,这样只要保证可以使匹配数增长就可以了。比如上面的4-8就是一条增广轨。

比如下面这种情况:

1 ——2

3 ——4

第一次,我们找到了1-2,下一次找增广轨,实际上3-4就是相对于匹配1-2的一条增广轨。            

上面文字证明是这个意思,只要有一个连通片成为轨就可以了,而且因为M"比M多一条边,保证了这样的连通片是必然存在的。

因为我们可以发现,H的连通片中,必然是M和M"的边交替出现的,交替出现就保证了大多数连通片里M和M"的边的个数是相等的,但是又因为M"比M多一条边,如果所有的连通片都是交替出现且M和M"的边的个数是相等的,那么显然M"和M边应该一样多,所以比然至少有一个连通片里在M"中的边必M中的边多一个

假设M"中的边用1表示,M中的用0表示,则必然是下面这个形式的序列:

1(就是上文中的{4,8}这种情况), 10101,即首尾必然是1,否则如1010,这个1和0的个数相等。而这样的形式1010101刚好就是我们的增广轨的定义。又它是独立的连通片,显然不应该与其他连通片相连。

 下面证明定理2:

假设我们对点A进行了两次,增广,第一次没有找到增广路,第二次找到了。下面需要证明这样是矛盾的,因为如果第二次可以找到,那么在第一次找时就应该找到了。

前面说过了实际上这个定理利用了1,或者它们证明的方法完全是一样的,我们可以用在第一次增广A时的那个匹配替换上面的M,而第二次增广A之后得到的那个匹配集显然就是上面的M"。两者的区别就在现在那个增广轨的位置已经确定了,因为这里的A点首先他必然不在M中,但是第二次从A处找到了一条增广轨,所以它必然的被加入了M"中,这也就意味着定理1证明中苦苦寻觅的那个增广轨在这里变成了确定的,就是从A开始的,也就是说实际上在第1次增广A时就应该找到这条增广轨了,于是矛盾。

匈牙利算法的一些处理技巧:

1. 

对于增广路径还可以用一个递归的方法来描述。这个描述不一定最准确,但是它揭示了寻找增广路径的一般方法:
“从点A出发的增广路径”一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匹配中没有与任何点配对,则它就是这条增广路径的终点;反之,如果点B已与点C配对,那么这条增广路径就是从A到B,再从B到C,再加上“从点C出发的增广路径”。并且,这条从C出发的增广路径中不能与前半部分的增广路径有重复的点。

2.

如果从一个点A出发,没有找到增广路径,那么无论再从别的点出发找到多少增广路径来改变现在的匹配,从A出发都永远找不到增广路径。
有了这个定理,匈牙利算法就成形了。如下:

初始时最大匹配为空
for 二分图左半边的每个点i
    do 从点i出发寻找增广路径。如果找到,则把它取反(即增加了总了匹配数)。

 二.二分匹配的与最大流的相互靠拢

下面看最大流与二分匹配的关系,如图所示:

二分匹配,最大流,匈牙利图形解释及证明 - 星星 - 银河里的星星

 

 如图1,第一次寻找增广路时,找到的是图中的绿色路线,则得到图2的剩余网络,然后在寻找增广路时,得到了图3的红色路线。

观察这两次路线S-1-3-T  S-2-3-1-4-T
如果对应到匈牙利算法,实际上第一次我们找到了1-3这条增广路,然后继续寻找实际上寻找到了2-3-1-4这条增广路。
很明显的,最大流发现的路径实际上就是匈牙利发现的增广路径,因为最大流发现的从S到T的可达路里,具有以下特点,比如是从S-T-S-T-S这样的属性,我们假设在二分图左边的那些点具有属性S,右侧才那列具有属性T,而可以从T-S则必然是那些曾经被走过的边,也就是匈牙利算法里那些以匹配的边,在这里它们达到了一致。

You Might Also Like