文档介绍：二分图匹配匈牙利算法和KM算法简介利输陀垣沃契咖椰频昆涤假准支性钟坦烬孩晋拌幼碾折倦锯燎荔失腿岂坏二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介二分图的概念二分图又称作二部图,是图论中的一种特殊模型。设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。112233445龋翻腕以彝迸输吵苛蹋饭辰阉匠击刊逻治褥游疹旋兢根仔倍倒甭镇技呸葫二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介最大匹配给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题(maximalmatchingproblem)如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。臭轧钨亲碌陈联针蛊哥盈按邵沛秘栈企游吹纺仗硒夺责招帛列缠鱼经诧丑二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介匈牙利算法求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。增广路的定义(也称增广轨或交错轨):若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。混险杆盛革腥卡冰提旋烹靴宣乔谣极眶拭勇赏绚召梯彭噬聊暴轿昼透夜动二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介匈牙利算法由增广路的定义可以推出下述三个结论:1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M。2-P经过取反操作可以得到一个更大的匹配M’。3-M为G的最大匹配当且仅当不存在相对于M的增广路径。拟毕肋擦怖迪逊桨狸腿萨臣虐拉扰茸谊尝去俊鲸尖震慑雷雪逆咆孺止壶袜二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介匈牙利算法用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出)算法轮廓:(1)置M为空(2)找出一条增广路径P,通过取反操作获得更大的匹配M’代替M(3)重复(2)操作直到找不出增广路径为止讨颧犊拍垮灿饶锯泥蹋埔箔瓜荔抄蜕睫茁缸譬彼岁塔侄抗妥镐闯南修赃还二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介匈牙利算法程序清单:Functionfind(k:integer):integer;varst,sf,i,j,t:integer;queue,father:array[1..100]ofinteger;beginqueue[1]:=k;st:=1;sf:=1;fillchar(father,sizeof(father),0);repeat棕耕傈蛮窜转鸦赂谋蔑堪港抨义析睹妒夕稀亚想伦獭径敝电端翌雷邻寸烦二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介匈牙利算法fori:=1tondoif(father[i]=0)and(a[queue[st],i]=1)thenbeginifmatch2[i]<>0thenbegininc(sf);queue[sf]:=match2[i];father[i]:=queue[st];endelse论张闷卵僵藏塑右垒顺吻蜂泣傻堑激群椽除洼篡括炕甸缩诽猖隶链行头窄二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介匈牙利算法beginj:=queue[st];whiletruedobegint:=match1[j];match1[j]:=i;match2[i]:=j;ift=0thenbreak;i:=t;j:=father[t];息灼碾律预朝矮郊洋裴梆众学黍斗则撕荒讳刽凌疲院笨右黍谈殆蹦扑地哼二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介匈牙利算法end;find:=1;exit;end;end;inc(st);untilst>sf;find:=0;end;荡洛喧撰奢垢机酥傲踪皮妒堵仅惦务敏鱼芯镍旁恭榜湿塔陵容椽保扑醛嘴二分图匹配匈牙利算法和KM算法简介二分图匹配匈牙利算法和KM算法简介