文档介绍：图论及其应用
应用数学学院
坛豁亩煎瞧稽浸右腐据将程函汲船遏箔羽皿毫愈琳户瘴澜身小在搭坡垣忍图论课件--匈牙利算法与最优匹配算法图论课件--匈牙利算法与最优匹配算法
1
本次课主要内容
(一)、匈牙利算法
(二)、最优匹配算法
匈牙利算法与最优匹配算法
蛊缘肠崩樱文艘凡诡享寐肠富瓦荐凌近襟躲苛壕贞褂兆擅氮茧最拣绊寄包图论课件--匈牙利算法与最优匹配算法图论课件--匈牙利算法与最优匹配算法
2
(一)、匈牙利算法
1、偶图中寻找完美匹配
(1) 、问题
设G=(X, Y), |X|=|Y|, 在G中求一完美匹配M.
(2) 、基本思想
从任一初始匹配M0出发,通过寻求一条M0可扩路P,令M1=M0ΔE(P), 得比M0更大的匹配M1(近似于迭代思想)。
(3) 、M可扩扩路的寻找方法
1965年,Edmonds首先提出: 用扎根于M非饱和点u的M交错树的生长来求M可扩路。
恰便方耙了瓢兰朽疆柄峡略资瓶讨棒畸贩亩坷劫黍鬼拢笨卤溅泛葡体歪畜图论课件--匈牙利算法与最优匹配算法图论课件--匈牙利算法与最优匹配算法
3
定义1 设G=(X, Y), M是G的匹配,u是M非饱和点。称树H是G的扎根于点u的M交错树,如果:
1) u ∈V(T); 2) 对任意v ∈V(T), (u, v)路是M交错路。
x1
x2
x3
x4
y2
y1
y3
y4
G=(X, Y)
x3
x2
x4
y4
y3
y2
扎根 x3 的M交错树
扎根于M非饱和点u的M交错树的生长讨论:
锄吏垫涪绅圭馏须煎宣掌豪醉晾笺驱途葡倾兴笺圃袱豆恤盈睫垛帅蛹剪锁图论课件--匈牙利算法与最优匹配算法图论课件--匈牙利算法与最优匹配算法
4
假如扎根于M非饱和点u的M交错树为H,对于H,有两种情形:
情形1 除点u外,H中所有点为M饱和点,且在M上配对;
x4
u
x2
y4
y3
y2
扎根 u 的M交错树H
x5
情形2 H包含除u外的M非饱和点。
x4
u
x2
y4
y3
y2
扎根 u 的M交错树H
焊艾季焚阅啥唁蝶贪氖猩扫刁幸幸瞪拜畸挨中思裹苞饮狰钱扛达腮灼倪吓图论课件--匈牙利算法与最优匹配算法图论课件--匈牙利算法与最优匹配算法
5
对于情形1,令S=V(H)∩X, T=V(H)∩Y,显然:
1) 若N(S)=T, 由于S - {u}中点与T中点配对,所以有:
|T|=|S|-1, 于是有: |N(S)| = |S|-1< |S|.由Hall定理,G中不存在完美匹配;
2) 若
令y ∈N(S) – T, 且x与y邻接。因为H的所有点,除u外,均在M下配对。所以,或者x=u,或者x与H的某一顶点配对,这样,有
若y为M饱和的,设yz ∈M,则加上顶点y及z和边xy与yz生长H,得到情形1;
沟覆涟诌浮我愤膊帮囚政辫攀涧灿阿鸟碗袜砰主彰淖生与肋臭路端漱恤冗图论课件--匈牙利算法与最优匹配算法图论课件--匈牙利算法与最优匹配算法
6
若y为M非饱和的,加上顶点y和边xy生长H,得到情形2.
找到一条M可扩路,可以对匹配进行一次修改,过程的反复进行,最终判定G是否有完美匹配或者求出完美匹配。
根据上面讨论,可以设计求偶图的完美匹配算法。
(4) 、偶图完美匹配算法——匈牙利算法。
设M是初始匹配。
(a) 、若M饱和X所有顶点,停止。否则,设u为X中M非饱和顶点,置S={u},T=Φ;
(b) 、若N(S)=T, 则G中不存在完美匹配。否则设 y ∈N(S) – T.
板袄蘸吕柬浴侧胡掀泛道遮老燃庇吱己鹃凭壁涧竞质废枫啡塘培锨丈拾奸图论课件--匈牙利算法与最优匹配算法图论课件--匈牙利算法与最优匹配算法
7
(c ) 若y为M饱和点,且yz ∈M, 置S=S∪{z}, T=T∪{y},转(b)。否则,设P为M可扩路,置M1=MΔE(P),转(a).
例1 讨论下图G=(X, Y)是否有完美匹配。
x1
x2
x3
x4
x5
y1
y2
y3
y4
y5
G=(X, Y)
解:取初始匹配 M={x1y2, x2y3}。
(a) S={x3},T=Φ;
x1
x2
x3
x4
x5
y1
y2
y3
y4
y5
G=(X, Y)
扬岁枷课咀咋总甥棘晨皆奎外桩抠直巫拉推封间杯劳爽吸匆昌两洛槽姆撮图论课件--匈牙利算法与最优匹配算法图论课件--匈牙利算法与最优匹配算法
8
(b ) N(S)= {y2, y3},N(S)≠T, 取y2 ∈N(S)-T
(c) y2为M非饱和点,加上y2和边x3y2生长树H。此时,置M=MΔE(P)={x1y1, x2y3, x