您好、欢迎来到现金彩票网!
当前位置:21点 > 子集覆盖 >

二分图匹配——匈牙利算法

发布时间:2019-06-27 06:22 来源:未知 编辑:admin

  匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

  基本原则就是在原有匹配(最开始的按优先顺序匹配)基础上重新分配,看是否可以添加一个新的匹配。

  【例】下面(b)图中的G2和(c)图中的G3均是无向图,它们的顶点集和边集分别为:

  二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。

  简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

  无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。如果无回路(如图3就没有回路),相当于任一回路的次数为0,0也是偶数,故也视为二分图。

  见图4所示,其存在回路。如:1-4-2-5-1,长度为4,偶数。任意一种都为偶数(循环的周期回路也是偶数)。如果在1和2之前添一条边,那就不是二分图了,如下图。

  添了1--2的边后,回路就存在了1--4--2--1,长度为3,奇数,所以图3就不是二分图。这也违背了二分图的定义 ,定义中指出图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),但是很明显图5中1-2的边的两个顶点来自同一个点集。

  给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

  如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。

  也称增广轨或交错轨。设M为二分图G已匹配边的集合,若P是图G中一条联通两个未匹配顶点的路径,且属于M的边和不属于M的边在P上交替出现,则称P为相对于M的一条增广路径。P的起点在X部,终点在Y部,反之亦可,路径P的起点终点都是未匹配的点。

  增广路径是一条“交错轨”。也就是说, 它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且起点和终点还没有被选择过,这样交错进行,显然P有奇数条边,因为不属于匹配的边比匹配的边要多一条!。

  如图9,红边为三条已经匹配的边。从X部一个未匹配的顶点x4开始,找一条路径P:

  因为y2是Y部中未匹配的顶点,x4是X部中未匹配的顶点,且匹配的边和未匹配的边交替出现,故所找路径是增广路径P。

  另外,单独的一条连接两个未匹配点的边显然也是交错轨。可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.

  下面介绍单独的一条连接两个未匹配点的边显然也是交错轨的情况。如在图11中,刚开始的时候,没有一个匹配的,此时进行匹配1-1,1和1相连就是一条增广路径(交错轨)。

  用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出)

  从X部一个未匹配的顶点Xi开始,找一个未访问的邻接点Yi(Yi一定是Y部顶点)。对于Yi,分两种情况:

  如果Yi未匹配,这俩相连,则就算已经找到一条增广路(是单个边的增广路径)

  如果Yi已经匹配,则取出yi的匹配顶点Xm(Xm一定是X部顶点),边(Xm,Yi)目前是匹配的,根据“取反”的想法,要将(Xm,Yi)改为未匹配,(Xi,Yi)设为匹配,能实现这一点的条件是看从Xm为起点能否新找到一条增广路径P’。如果行,则Xi-Yi-P’就是一条以Xi为起点的增广路径。

  请先看图11,图11中红线表示的是未匹配的边(这就是置M为空),再看如图12所示,蓝线表示的是已匹配的边,这两个匹配的都是单个边的增广路径(在Y部分从上往下找)。因此X1,X2,都找到了单边的增广路径。接着该X3了,X3先从Y1下手,Y1已经和X1匹配了,这时看X1(这时把X1看为未匹配的点,因为增广路径的定义是,从起点为未匹配的点到终点为未匹配的点)能不能找到一条增广路径,显然从X1出发可以找到一条增广路径:X1Y2-Y2X2-X2Y3。这时就形成了新的增广路径:X3Y1-Y1X1-X1Y2-Y2X2-X2Y3。此时根据取反操作,则X3Y1、X1Y2、X2Y3,成为匹配边(3条)。比之前的两条匹配边多了一条。

  接下来是X4,X4因为找不增广路径(增广路径从未匹配起点出发,到未匹配点的终点),所以无法进行匹配。故最大匹配结果为:

  匈牙利算法中的增广路径取反操作在代码实现的时候使用的是递归,递归一直往下找。在递归过程中,进行取反操作。

  图论(一)图:顶点,边,同构,有向/无向图,权重,路径(最短路径),环,连通图/连通分量:

  趣写算法系列之--匈牙利算法(点击打开链接):【书本上的算法往往讲得非常复杂,我和我的朋友计划用一些简单通俗的例子来描述算法的流程】匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。...博文来自:一只秀逗__的博客

  转自:二分图的概念二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无...博文来自:刘二狗的博客

  匈牙利法的基本思路:对费用矩阵C的行和列减去某个常数,将C化为有n个位于不同行不同列的零元素,令这些零元素对应的变量取1,其余变量取0,即得到指派问题的最优解。匈牙利法是基于指派问题的标准型的,标准型...博文来自:Wonz

  本篇文章转自:趣写算法系列之--匈牙利算法正文:【书本上的算法往往讲得非常复杂,我和我的朋友计划用一些简单通俗的例子来描述算法的流程】匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名...博文来自:feengg的博客

  3个重要结论:最大匹配数:最大匹配的匹配边的数目最小点覆盖数:选取最少的点,使任意一条边至少有一个端点被选择最大独立集:选取最多的点,使任意所选两点均不相连最小路径覆盖数:对于一个DAG(有向无环图)...博文来自:尘封丶的博客

  Linux管道是一种进程间通信的机制。它是一种单向的通信机制,读进程和写进程不能倒置。Linux把管道抽象成一种文件来进行操作。类似于对设备的读写操作。实际上管道只是操作系统分配给进程的一段内存缓冲区...博文来自:fengkehuan的专栏

  简介匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法,如果使用暴力穷举求解分配解的话,则是一个NP的问题。任务(目标):假设一个非负矩阵,第i行第j列的元素表示第i个工人完成第j个任务需要...博文来自:Hello World

  二分图又称作二部图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i...博文来自:TUT我好菜啊

  二分图最大匹配:问题描述:给出一个二分图,找一个边数最大的匹配。就是选择尽量多的边,使得选中的边中任意两条边均没有公共点。如果所有的点都是匹配点那就是一个完美匹配。解决方案:增广路定理增广路:从一个未...博文来自:傻子是小傲娇的博客(大钊)

  二分图指的是这样一种图,其所有顶点可以分成两个集合X和Y,其中X或Y中任意两个在同一集合中的点都不相连,所有的边关联在两个顶点中,恰好一个属于集合X,另一个属于集合Y。给定一个二分图G,M为G边集的一...博文来自:月光の雲海

  首先来说明一下匈牙利算法是解决什么问题的简单来说匈牙利算法是寻找通过增广路,并通过扩展增广路找出二分图的最大匹配数的算法。从上面一句话我们可以得到几个关键词,二分图,二分图的匹配,二分图的最大匹配数,...博文来自:唐宋元明清的博客

  二分图的概念二分图又称作二部图,是图论中的一种特殊模型。设G=(V,E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在X中,另一个在Y中,则称图G为二分...博文来自:C20180630的博客

  【书本上的算法往往讲得非常复杂,我和我的朋友计划用一些简单通俗的例子来描述算法的流程,这只是刚开始的样稿,其实我们也才刚开始】匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利...博文来自:DarkScope从这里开始

  分配问题与匈牙利算法例1假如你是个玩具工厂的销售经理,你现在有三个销售人员要去不同城市见买家。你的销售人员分别在在奥斯丁,得克萨斯州;波士顿、马里兰州;和芝加哥,伊利诺伊州。你想让他们飞往其他三个城市...博文来自:kevinjqy的专栏

  二分图简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。也就是说,把一个图的顶点划分为两个不相交集XX和YY,使得每一条边都分别连接XX、YY中的顶点。如果存在这样...博文来自:六天

  近期做了两个二分图的题,之前一直不会,最近就学习了一下匈牙利算法:匈牙利算法是用来解决有关二分图匹配问题的算法。首先,先了解什么是二分图:就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两...博文来自:sxh759151483的博客

  二分图二分图的概念二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在X中,另一个在Y中,则称图...博文来自:XSYYMY的博客

  匈牙利算法(Hungarianmethod)是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是二分图匹配最常见的算法,该算法的核心就是寻找增...博文来自:baodream的博客

  本文讲述的是匈牙利算法,即图论中寻找最大匹配的算法,暂不考虑加权的最大匹配(用KM算法实现),文章整体结构如下:基础概念介绍 算法的实现好的,开始!一.部分基础概念的介绍我会严格介绍其定义,并同时用自...博文来自:夜阑听风

  题目:StrategicGame 用vector实现邻接表的匈牙利算法。典型的最小顶点覆盖!最小顶点覆盖=最大匹配(双向图)/2;此题有个小细节,数据较大,要用邻接表,不然会超时! 最小顶点覆盖:选出...博文来自:ACdreamer

  大家好,关于用匈牙利算法求二部图的最大匹配问题,我有一个疑问,有二部图如下图所示: 假设M是一个只包含边{x1,y1}的匹配,那么M的交错链是什么?论坛

  【基本概念】二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为两个不相交集U和V,使得每一条边都分别连接U、V中的顶点。如果存...博文来自:Keaper的博客

  问题描述:给出一个x集合和y集合的二分图,他们之间有一定的可以匹配的边。求最大匹配。匈牙利算法-DFS:增广路:以一条未匹配的边开始,且以一条未匹配的边结束,并且未匹配边与匹配边交替出现的路径叫做增广...博文来自:STILLxjy

  二分图的定义:二分图是这样的一个图,它的顶点可以分为两个集合X和Y。所有的边关联的两个顶点中,恰好一个属于集合X,一个属于集合Y。二分图的匹配:给定一个二分图G,M为G边集的一个子集,如果M满足当中的...博文来自:Cold_Chair的博客

  今天学了二分图的最大匹配,其中的匈牙利算法。。哦不,其实远不止这个,还有后面的一系列KM、开花树啊什么的算法。反正又是一个异常懵逼的一天。。。我觉得应该是上课前没有稍微预习一下这个算法是什么,了解个大...博文来自:x_y_q_的博客

  第一次写博客,有什么错误请指出我会及时改正。qwq目录二分图匹配最大匹配 完美匹配交替路增广路代码 二分图 二分图其实就是在一个图中所有的点可以分为两组,同一组中没有边,所有的边都跨越了两个组。准确的...博文来自:jvruo233的博客

  前部分算法解释引自感谢大神的讲解【书本上的算法往往讲得非常复杂,我和我的朋友计划用一些简...博文来自:zhaoguowei的博客

  先介绍一下基本概念以下基本概念转自其他的博客,不是原创二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为两个不相交集   和 ...博文来自:的博客

  最近复习算法的时候,发现好多讲匈牙利的教材都讲的特别恶心,其实这是一个非常容易理解的算法。匈牙利算法主要是求二分图的最大匹配主要思想是把左边的一个个匹配,冲突就尝试给前面的分配另一个点下面是详细解析我...博文来自:Never give in.

  基本思想:先初始化匹配M为空,找到图中的一条相对于M的增广路P。对P上的路径取反,更新M,。再次寻找增广路,若不存在增广路算法结束。(有一点点稍微难理解,自己手动模拟一下这个过程就知道啦)#inclu...博文来自:loving coding

  算法应用场景:农夫约翰上个星期刚刚建好了他的新牛棚,他使用了最新的挤奶技术。不幸的是,由于工程问题,每个牛栏都不一样。第一个星期,农夫约翰随便地让奶牛们进入牛栏,但是问题很快地显露出来:每头奶牛都只愿...博文来自:JavaMan_chen的专栏

  题目背景二分图题目描述给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数输入输出格式输入格式:第一行,n,m,e第二至e+1行,每行两个正整数u,v,表示u,v有一条连边输出格式:共一...博文来自:Dance Of Faith

  匈牙利算法应用于二分图(即可以分为两大部分,且个部分内不连接的图)匹配的问题,它的时间复杂度为O(nm)。它的基本原理是增广路。它的用途主要有三:1、单纯二分图匹配;2、最小点覆盖;3、最大独立集。下...博文来自:A_Bright_CH的博客

  一、图的匹配与贝尔热问题\quad图匹配概念:如果M是图G的边子集(不含环),且M中的任意两条边没有共同顶点,则称M是G的一个匹配或对集或边独立集。如下图所示:\quad若顶点是M中某条边的顶点,则称...博文来自:的博客

  利用匈牙利算法可以求得二分图最大匹配。匈牙利算法的基本原理如下:①置M为空;②找到一条增广路径P,通过异或操作获得更大的匹配M代替M;③重复②直到找不到新的增广路径。增广路径的定义如下:若P是图G中...博文来自:Reid_Zhang1993的专栏

  分析:只写了匈牙利 网络流还没有写AC代码:#include#inc...博文来自:MM__1997的博客

  二分图匹配,自然要先从定义入手,那么二分图是什么呢?二分图:二分图又称作二部图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(...博文来自:既然弱小,就只顾变强就是了

  IAP升级功能编写初期的一些困惑与疑问---完成功能后的总结 一,网上下载的例程,跳转部分的代码有差异,尤其是用的汇编那句 二,关于跳转部分的代码的理解(转) 三,关于跳转时能否不用按键,用软件标志位...博文来自:Super_Demo的专栏

  现在的Win7系统中安装的一般都是32位的Office,因为微软推荐使用32位的Office,兼容性更强,稳定性更好。在使用Access作为数据库的时候,C#操作Access,如果Access是acc...博文来自:写代码的蜗牛

  转载请注明出处:     在上一篇blog中介绍过POI检索的使用,本篇blog主要介绍公交信息检索和线路规划的内容。 公交信息检索     实际上,公交信息检索与POI检索、在线建议检索非常相似,也...

  Java中的ThreadLocal类允许我们创建只能被同一个线程读写的变量。因此,如果一段代码含有一个ThreadLocal变量的引用,即使两个线程同时执行这段代码,它们也无法访问到对方的Thread...

  u011860731的专栏C#实现开发windows服务实现自动从FTP服务器下载文件(自行设置分/时执行)

  最近在做一个每天定点从FTP自动下载节目.xml并更新到数据库的功能。首先想到用 FileSystemWatcher来监控下载到某个目录中的文件是否发生改变,如果改变就执行相应的操作,然后用timer...

  摘要 最近要发论文了,被知乎里人推荐使用论文编译软件(CTex、LaTex和Overleaf之类),瞬间感觉自己用Word简直Out了(书读少)。 学校里也听说过LaTex,不过因为当时没怎么写过...

  看到很多朋友配置vsftpd时不能使用匿名用户上传和下载(创建目录或删除、重命名文件夹),本文主要解决vsftpd的匿名用户权限配制问题。...

  一个例子高斯混合模型(Gaussian Mixed Model)指的是多个高斯分布函数的线性组合,理论上GMM可以拟合出任意类型的分布,通常用于解决同一集合下的数据包含多个不同的分布的情况(或者是同一...

  最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗! Docker的三大核心概念:镜像、容器、仓库 镜像:类似虚拟机的镜像、用俗话说就是安装文件。 容器:类似一个轻量...

  我走小路的博客将Excel文件导入数据库(POI+Excel+MySQL+jsp页面导入)第一次优化

  本篇文章是根据我的上篇博客,给出的改进版,由于时间有限,仅做了一个简单的优化。相关文章:将excel导入数据库2018年4月1日,新增下载地址链接:点击打开源码下载地址十分抱歉,这个链接地址没有在这篇...

  Http协议的重要性相信不用我多说了,HttpClient相比传统JDK自带的URLConnection,增加了易用性和灵活性(具体区别,日后我们再讨论),它不仅是客户端发送Http请求变得容易,而且...

  klkxxy的博客三菱FX系列PLC与PC通讯的实现之专有协议(计算机联接)的程序设计之一

  阅读内容为:FX系列微型可编程控制器用户手册(通讯篇)中计算机链接功能章节。 采用本方法通信,pc端的实现,其实就是,把操作按照协议(2种)翻译成相应的字符串,通过串口发送给plc。 编写一应用程...

  强连通分量: 简言之 就是找环(每条边只走一次,两两可达) 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点)   定义: int Ti...

  u013268685的专栏(有一种幸福叫AC,有一种期待叫AK)简单linux字符设备驱动程序与编程小技巧(上)

  这几天开始研究linux下的驱动程序编写了,遇到的问题也挺多的,好在linux是开源的,很多高人编写的技巧和思路都会在他们的源代码中体现,我也在他们的源码中学到了很多好东西,我归纳了下贴出来,希望自己...

  苹果充值的刷单现象在游戏行业非常普遍,很多团队挖空心思寻找漏洞以非法获利。常见的手段主要有以下六种: 伪造充值凭据(receipt)以小额凭据骗取大额商品 凭据重复使用 凭据重复使用信用卡黑卡/...

  分享知识、分享进步jquery/js实现一个网页同时调用多个倒计时(最新的)

  jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...

  一、代理模式为某个对象提供一个代理,从而控制这个代理的访问。代理类和委托类具有共同的父类或父接口,这样在任何使用委托类对象的地方都可以使用代理类对象替代。代理类负责请求的预处理、过滤、将请求分配给委托...

  如下图所示,蜂窝小区,以1为中心,顺时针编号,编号最大限定为100000。求任意两编号之间的最短距离。两个相邻小区的距离为1 示例:19到30的最短距离为5 实现如下三个接口: /**********...

  NYS001的专栏魔兽争霸3冰封王座1.24e 多开联机补丁 信息发布与收集点

  在MATLAB中,可以注释一段程序。 使用“%{”和“%}”。 例如 %{ 。。。 %} 即可。 经典方法是用 if 0,但缺点是不够直观,注释掉的内容仍然保持代码的颜色。现在可以用 ...

http://libroebook.com/zijifugai/113.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有