二分图匹配.ppt
《二分图匹配.ppt》由会员分享,可在线阅读,更多相关《二分图匹配.ppt(29页珍藏版)》请在三一文库上搜索。
1、二分图匹配,匈牙利算法和KM算法简介,二分图的概念,二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,R)是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。,最大匹配,给定一个二分图G,在G的一个子图M中,M的边集E中的任意两条边都不依附于同一个顶点,则称M是一个匹配。 选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) 如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。,匈牙利算法,求最大匹配的一种显而易见的算法是:先找出全部匹配
2、,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。 增广路的定义(也称增广轨或交错轨): 若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。,匈牙利算法,由增广路的定义可以推出下述三个结论: 1P的路径长度必定为奇数,第一条边和最后一条边都不属于M。 2P经过取反操作可以得到一个更大的匹配M。 3M为G的最大匹配当且仅当不存在相对于M的增广路径。,匈牙利算法,用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出) 算法轮廓: (1)置
3、M为空 (2)找出一条增广路径P,通过取反操作获得更大的匹配M代替M (3)重复(2)操作直到找不出增广路径为止,匈牙利算法,程序清单: Function find(k:integer):integer; var st,sf,i,j,t:integer; queue,father:array1100 of integer; begin queue1 := k; st := 1; sf := 1; fillchar(father,sizeof(father),0); repeat,匈牙利算法,for i:=1 to n do if (fatheri=0)and(aqueuest,i=1) the
4、n begin if match2i0 then begin inc(sf); queuesf := match2i; fatheri := queuest; end else,匈牙利算法,begin j := queuest; while true do begin t := match1j; match1j := i; match2i := j; if t = 0 then break; i := t; j := fathert;,匈牙利算法,end; find := 1; exit; end; end; inc(st); until stsf; find := 0; end;,匈牙利算法
5、,在主程序中调用下面的程序即可得出最大匹配数。 Bmatch := 0; For I:=1 to n do Bmatch := Bmatch + find(i); Writeln(Bmatch); 一个关于二分图的性质: 最大匹配数最大独立集XY,最佳匹配,如果边上带权的话,找出权和最大的匹配叫做求最佳匹配。 实际模型:某公司有职员x1,x2,xn,他们去做工作y1,y2,yn,每个职员做各项工作的效益未必一致,需要制定一个分工方案,使得人尽其才,让公司获得的总效益最大。 数学模型:G是加权完全二分图,求总权值最大的完备匹配。,KM算法,穷举的效率n!,我们需要更加优秀的算法。 定理: 设M是
6、一个带权完全二分图G的一个完备匹配,给每个顶点一个可行顶标(第i个x顶点的可行标用lxi表示,第j个y顶点的可行标用lyj表示),如果对所有的边(i,j) in G,都有lxi+lyj=wi,j成立(wi,j表示边的权),且对所有的边(i,j) in M,都有lxi+lyj=wi,j成立,则M是图G的一个最佳匹配。证明很容易。,KM算法,对于任意的G和M,可行顶标都是存在的: l(x) = maxw(x,y) l(y) = 0 欲求完全二分图的最佳匹配,只要用匈牙利算法求其相等子图的完备匹配;问题是当标号之后的Gl无完备匹配时怎么办?1957年(居然比匈牙利算法早?),Kuhn和Munkras
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分 匹配
链接地址:https://www.31doc.com/p-2551146.html