文档介绍：二分图匹配匈牙利算法和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算法简介