二分图的最大匹配-匈牙利算法.ppt

二分图的最大匹配 Br171 思考一下?棋盘上有 N个点,每次可以拿走一行或者一列。?问最少多少次可以把棋盘上的所有点都拿走 poj3041 二分图?二分图是一种特殊的图?对于无向图 G=(V,E) ,如果V可以分为两个互不相交的子集,并且图中的每条边所依附的两点都属于不同的子集,则图 G则称为一个二分图 5 4’ 4 3’ 3 2’ 2 1’ 1最大匹配?给定一个二分图 G,在 G的一个子图的边集中的任意两条边都不依附于同一个顶点,则称此子图是一个匹配。?选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) ?如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。增广路?图1是我给出的二分图中的一个匹配:[ 1,5]和[2,6]。图 2就是在这个匹配的基础上找到的一条增广路径: 3->6->2->5- >1->4 。增广路径的性质? 1)有奇数条边。(2) 起点在二分图的左半边,终点在右半边。(3) 路径上的点一定是一个在左半边,一个在右半边,交替出现。(其实二分图的性质就决定了这一点,因为二分图同一边的点之间没有边相连,不要忘记哦。) (4) 整条路径上没有重复的点。(5) 起点和终点都是目前还没有配对的点,而其它所有点都是已经配好对的。(如图1、图 2所示,[ 1,5]和[ 2,6]在图 1中是两对已经配好对的点;而起点 3和终点 4目前还没有与其它点配对。) (6) 路径上的所有第奇数条边都不在原匹配中,所有第偶数条边都出现在原匹配中。(如图 1、图 2所示,原有的匹配是[ 1,5]和[ 2,6],这两条配匹的边在图 2给出的增广路径中分边是第 2和第 4条边。而增广路径的第 1、3、5条边都没有出现在图 1给出的匹配中。) (7) 最后,也是最重要的一条,把增广路径上的所有第奇数条边加入到原匹配中去,并把增广路径中的所有第偶数条边从原匹配中删除(这个操作称为增广路径的取反),则新的匹配数就比原匹配数增加了 1个。(如图 2所示,新的匹配就是所有蓝色的边,而所有红色的边则从原匹配中删除。则新的匹配数为 3。) 匈牙利算法? ,看看右边有没有增广路,如果有,那么进行增广,没有就不添加新的匹配。? ,整个图就形成了一个最大匹配。匈牙利算法算法的思路是不停的找增广路径, 并增加匹配的个数, 增广路径顾名思义是指一条可以使匹配数变多的路径, 在匹配问题中,增广路径的表现形式是一条"交错路径",也就是说这条由图的边组成的路径, 它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过。这样交错进行,显然他有奇数条边。那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推。也就是将所有的边进行“反色”,可以发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对。另外,单独的一条连接两个未匹配点的边显然也是交错路径。可以证明。当不能再找到增广路径时,就得到了一个最大匹配,这也就是匈牙利算法的思路。匈牙利算法?每次我们从上面的第 i个点出发尽量去找一个能唯一和它匹配的点 p,策略有两种,一是直接在下面的点中找到一个点 p, 他没有和上面的点匹配过(即 match[p] =0 )。二是当 p和上面的某个点匹配过, 即( match[p] )那么我们就从 match[p] 出发,去给他找下面另外的点和他匹配,把 p点留给点 i。这样我们不就多找到了一条? 建图?将行作为左边的点,列作为右边的点, 原图中的每个点形成一条边,将代表其行和列的点连接起来。?对已经建好的图求最大匹配