最大匹配算法匈牙利算法.ppt
《最大匹配算法匈牙利算法.ppt》由会员分享,可在线阅读,更多相关《最大匹配算法匈牙利算法.ppt(17页珍藏版)》请在三一文库上搜索。
1、二分图的 最大匹配,RCA,二分图,二分图是一种特殊的图 对于无向图G=(V,E),如果V可以分为两个互不相交的子集,并且图中的每条边所依附的两点都属于不同的子集,则图G则称为一个二分图,最大匹配,给定一个二分图G,在G的一个子图的边集中的任意两条边都不依附于同一个顶点,则称此子图是一个匹配。 选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) 如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。,增广路,对于右图的边,如果我们一开始仅有已经完成的匹配1-1,4-3。 那么当我们对于2,可以让已经有的匹配做下修
2、改,即4-4,1-3,空出来1和2进行匹配,这样沿着已有匹配去寻找到的新匹配叫增广路。,匈牙利算法,1.对于左边的每个点,看看右边有没有增广路,如果有,那么进行增广,没有就不添加新的匹配。 2.当对最后一个点做完增广路以后,整个图就形成了一个最大匹配。,二分图的最小覆盖数,棋盘上有N个点,每次可以拿走一行或者一列。 问最少多少次可以把棋盘上的所有点都拿走 poj3041,二分图的最小覆盖数,将行作为左边的点,列作为右边的点,原图中的每个点形成一条边,将代表其行和列的点连接起来。 对已经建好的图求最大匹配,Konig定理,最大匹配数=最小覆盖数,二分图的最大独立数,一张残缺的棋盘,用1*2的矩形
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最大 匹配 算法 匈牙利
链接地址:https://www.31doc.com/p-3390949.html