图论课件–匈牙利算法与最优匹配算法.ppt

图论课件–匈牙利算法与最优匹配算法.ppt

  1. 1、本文档共32页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
图论课件–匈牙利算法与最优匹配算法

* * 图论及其应用 应用数学学院 本次课主要内容 (一)、匈牙利算法 (二)、最优匹配算法 匈牙利算法与最优匹配算法 (一)、匈牙利算法 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可扩路。 定义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交错树的生长讨论: 假如扎根于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 对于情形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; 若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. (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) (b ) N(S)= {y2, y3},N(S)≠T, 取y2 ∈N(S)-T (c) y2为M非饱和点,加上y2和边x3y2生长树H。此时,置M=MΔE(P)={x1y1, x2y3, x3y2} x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y) x3 y2 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y) (a) S={x4},T=Φ; x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y) (b ) N(S)= {y2, y3},N(S)≠T, 取y2 ∈N(S)-T (c) y2为M饱和点,y2x3 ∈ M。此时,置S=S∪{x3} T=T∪{y2}。 (b ) N(S)= {y2, y3} ≠T,取y3 ∈N(S)-T x4 y2 x3 (c) y3为M饱和点,x2y3 ∈ M。此时,置S=S∪{x2} T=T∪{y3}。 (b ) N(S)= {y2, y3} ≠T,取y3 ∈N(S)-T x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 G=(X, Y) (b ) N(S)= {y2, y3} =T,所以,G无完美匹配。 (5) 、匈牙利算法复杂性分析 1) 、最多循环|X|次可以找到完美匹配; 2)

文档评论(0)

shaoye348 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档