二分图(匈牙利,KM算法详解).pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《二分图(匈牙利,KM算法详解).pptx》由会员分享,可在线阅读,更多相关《二分图(匈牙利,KM算法详解).pptx(35页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、二分图匹配二分图匹配培训专用Bi-partite graph二分图的定义:二分图是这样的一个图,它的顶点可以分为两个集合X和Y。所有的边关联的两个顶点中,恰好一个属于集合X,一个属于集合Y。123456二分图的匹配:给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配。培训专用二分图的最大匹配定义:图中包含边数最多的匹配称为图的最大匹配。如右图所示:蓝色部分就构成一个最大匹配,同时它也是一个完美匹配完美匹配:如果所有点都在匹配边上,称这个最大匹配是完美匹配。培训专用二分图的最大匹配匈牙利算法(时间复杂度O(nm))其思想是用宽度优先搜索来找增
2、广路径(和floodfill算法类似转化为单位容量简单网络的最大流问题在二分图的基础上,加入源点s和汇点t,让s与每个X结点连一条边,每个Y结点和t连一条边,所有弧的容量为1。这样,饱和弧就对应着匹配边。培训专用二分图的最大匹配匈牙利算法:寻找增广路:初始时最大匹配为空for二分图左半边的每个点ido从点i出发寻找增广路径如果找到,则把它取反(即增加了总了匹配数)。看一道例题:PKU1469培训专用PKU 1469一共有N个学生跟P门课程,一个学生可以任意选一门或多门课,问是否达成:1.每个学生代表的都是不同的课(如果一个学生选修的那门课,那么他就可以代表这门课)2.每门课都有一个代表培训专用
3、PKU1469输入为:PN(课程数跟学生数)接着有P行,格式为Countstudentistudenti+1studentcount(Count表示对课程1感兴趣的学生数,接着有Count个学生)如第一行212表示学生1跟学生2对课程1感兴趣输出为:若每门课都能找到一位代表则输出”YES”,否则为”NO”培训专用PKU1469假如有三个学生跟三门课程,学生1,2,3.为了跟学生区分,假设3个课程为4,5,6左边节点是学生,右边节点是课程,下图表示,学生1对课程4,5感兴趣,学生2对课程5,6感兴趣,学生3对课程6感兴趣123456于是问题就变为在二分图中寻找最大匹配,只要这个最大匹配大于或等于
4、课程数P,那么就达到要求了.培训专用寻找最大匹配的匈牙利算法流程首先我们先看节点1,寻找下一条边,假设找到节点5,因为1跟5都还没匹配,所以找到一个匹配.标记,xM1=5,yM5=1;123456假如我们用xM数组表示左边节点对其右边节点的匹配,yM表示右边节点对其左边节点的匹配,初始化为-1;现在重点看节点3,当寻找下一条边时,如图中的蓝边,我们发现节点6的yM6=2;已经匹配了.此时我们就转到节点6的匹配点2上去,发现节点2的另一条边2-5中节点5也已经匹配了,yM5=1;继续转到节点1,发现节点1的边1-4中节点4还没匹配.于是我们找到了一个增广路径增广路如图中箭头所增广路如图中箭头所示
5、示培训专用123456把图中红色线去掉蓝色线加上123456123456找到一个更好的匹配更改各自的匹配点培训专用总结所以流程就是:1,对于一个未匹配的节点u,寻找它的每条边,如果它的边上的另一个节点v还没匹配则表明找到了一个匹配,直接转步骤4;2,假如节点u它边上的另一个节点v已经匹配,那么就转向跟v匹配的节点,假设是w,然后再对w重复1,2的步骤,即寻找增广路.3,假如我们在1,2步过程中找到一条增广路,那么修改各自对应的匹配点,转步骤4,若无增广路,则退出.4,匹配数+1;培训专用最小点覆盖最小覆盖:最小覆盖要求用最少的点(集合或集合的都行)让每条边都至少和其中一个点关联。可以证明:最少
6、的点(即覆盖数)最大匹配数M简单的证明如下:(1)M个是足够的。只需要让它们覆盖最大匹配的M条边,则其它边一定被覆盖(如果有边e不被覆盖,把e加入后得到一个更大的匹配)(2)M个是必需的,仅考虑形成最大匹配的这M条边,由于它们两两之间没有公共点,因此至少需要M个点才可以把它们覆盖培训专用PKU 3041:(类似的有PKU3020)问题:假如你现在正处在一个N*N的矩阵中,这个矩阵里面有K个障碍物,你拥有一把武器,一发弹药一次能消灭一行或一列的障碍物,求最小的弹药消灭全部障碍物输入为:N K接下来有K行,每行包含障碍物的坐标,即r行c列;如:3 4 1 11 32 23 2 输出为:花费最小的弹
7、药数培训专用PKU3041对于上面那个数据我们可以用下面的表示,0表示无障碍物,1表示有;1 0 10 1 00 1 0首先,我们利用行跟列做二分图:123123行列如果第i行的第j列有障碍物,则在图中左边的i行连一条边到右边的j列,上面的数据就对应左图于是问题就转化成最小点覆盖的问题.求最大匹配即可.培训专用PKU2226现在我们看一道构图比较复杂的题:PKU2226培训专用DAG图的最小路径覆盖用尽量少的不相交简单路径覆盖有向无环(DAG)G的所有顶点,这就是DAG图的最小路径覆盖问题。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个:结点集中的i和Y结点集中的i,如果有边i-j,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分 匈牙利 KM 算法 详解
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内