匹配算法MATLAB程序.doc资源-CSDN文库

版权申诉

47 浏览量 2022-05-07 17:43:14 上传评论收藏 59KB DOC 举报

资源推荐

资源详情

资源评论

求二部图G 的最大匹配的算法(匈牙利算法), 其基本思想是：从G 的任意匹配M

开始,

对X 中所有M 的非饱和点, 寻找M 增广路. 若不存在M 增广路, 则M 为最大匹配;

若存

在M 增广路P, 则将P 中M 与非M 的边互换得到比M 多一边的匹配M1 , 再对M1

重复上

述过程.

设 G = ( X, Y, E )为二部图, 其中X = {x1, x2, ⋯ , xn }, Y = { y1, y2, ⋯ , yn}. 任取G

的一初

始匹配M (如任取e∈E, 则M = {e}是一个匹配).

① 令 S =

f

, T =

f

, 转向②.

② 若 M 饱和X \ S 的所有点, 则M 是二部图G 的最大匹配. 否则, 任取M 的非饱和

点

u∈X \ S , 令S = S ∪{ u }, 转向③.

③ 记 N (S ) = {v | u∈S, uv∈E }. 若N (S ) = T, 转向②. 否则取y∈N (S ) \ T. 若y 是

M

的饱和点, 转向④, 否则转向⑤.

④ 设 x y∈M, 则令S = S ∪{ x }, T = T ∪{ y }, 转向③.

⑤ u  y 路是M增广路, 设为P, 并令M = M⊕P, 转向①. 这里M⊕P = M∪P \ M∩

P, 是对称差.

由于计算 M增广路P 比较麻烦, 因此将迭代步骤改为：

① 将 X 中M 的所有非饱和点(不是M 中某条边的端点)都给以标号0 和标记*, 转

向②.

② 若 X 中所有有标号的点都已去掉了标记*, 则M 是G 的最大匹配. 否则任取X

中一

个既有标号又有标记*的点xi , 去掉xi 的标记*, 转向③.

③ 找出在 G 中所有与xi 邻接的点yj (即xi yj∈E ), 若所有这样的yj 都已有标号, 则

转向

②, 否则转向④.

④ 对与 xi 邻接且尚未给标号的yj 都给定标号i. 若所有的yj 都是M的饱和点, 则转

向⑤,

否则逆向返回. 即由其中M的任一个非饱和点yj的标号i 找到xi, 再由xi的标号k 找

到yk , ⋯ ,

最后由 yt 的标号s 找到标号为0 的xs 时结束, 获得M 增广路xs yt ⋯ xi yj, 记P =

{xs yt, ⋯ ,

xi yj }, 重新记M 为M⊕P, 转向①.

⑤ 将 yj在M 中与之邻接的点xk (即xk yj∈M), 给以标号j 和标记*, 转向②.

例1 求图 6-9 中所示的二部图G 的最大匹配.

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余4页未读，立即下载

内容反馈

版权申诉

老帽爬新坡

粉丝: 79
资源: 2万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip