最大匹配、最小顶点覆盖、最大独立集、最小路径覆盖(转)

最大匹配、最小顶点覆盖、最大独立集、最小路径覆盖(转)

大家好,又见面了,我是全栈君。

在讲述这两个算法之前,首先有几个概念须要明确:

二分图:
二分图又称二部图,是图论中的一种特殊模型。设G=(V,E)是一个无向图。假设顶点V能够切割为两个互不相交的子集(A,B),而且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A, j in B), 则称图G是二分图。
匹配:
给定一个二分图。在G的一个子图G’中,假设G’的边集中的随意两条边都不依附于同一个顶点。则称G’的边集为G的一个匹配
最大匹配:
在全部的匹配中,边数最多的那个匹配就是二分图的最大匹配了
顶点覆盖:
在顶点集合中。选取一部分顶点,这些顶点能够把全部的边都覆盖了。

这些点就是顶点覆盖集
最小顶点覆盖:
在全部的顶点覆盖集中,顶点数最小的那个叫最小顶点集合。
独立集:
在全部的顶点中选取一些顶点,这些顶点两两之间没有连线,这些点就叫独立集
最大独立集:
在左右的独立集中,顶点数最多的那个集合
路径覆盖:
在图中找一些路径,这些路径覆盖图中全部的顶点。每一个顶点都仅仅与一条路径相关联。
最小路径覆盖:
在全部的路径覆盖中,路径个数最小的就是最小路径覆盖了。

熟悉了这些概念之后,还有一个二分图最大匹配的König定理,这个定理的内容是:最大匹配 = 最小顶点覆盖。此处不证明其正确性。有了这个定理之后还能够得出一些二分图特有的公式:
最大独立集 = 顶点个数 – 最小顶点覆盖(最大匹配)
这个公式。我们能够利用最大匹配来找到最大的独立集。而最大独立集和最小路径覆盖有个千丝万缕的关系。
对于二分图的最大匹配,经常使用的求解方法是hungarian算法和最大流算法。以poj上的题目为例说明:
POJ2271: 题目大意是。一群男孩和女孩共N人。某些男孩和女孩之间会发生恋爱关系(满足一定的关系)。如今希望找到最多的孩子,他们之间不会发生恋爱关系。
分析:找到最多的孩子。没有恋爱关系,这实质上是找最大独立集。假设男孩在左有a个,女孩在右有b个,那么假设某男孩和某女孩之间有关系。就连线。最大独立集就是找到最多顶点,顶点之间没有联系,正好就是所求,而最大独立集就是 N-最大匹配,所以问题得到解决。

试想。假设二分图中没有连线,那么全部的孩子都可选。最大独立集也是N,他们是等价的。假设存在一条连线,那么去掉一个孩子就是所找的孩子,最大独立集此时是N-1.依次类推。

在试想,最大匹配事实上就找到了几对恋爱对象。假设是这种
a b
B0 G0
B1 G1
… …
Bi Gi
… …
我们仅仅须要把他们的还有一半去掉,就是我们找的孩子。只是会有这种疑问。假设我取出了B1的还有一半G1,B1会不会和其余的孩子恋爱呢,比方说B1和b会恋爱,那么好吧,去掉G1的还有一半B1,这样就不会有问题了吧。

还有操心?G1会不会和其余的孩子恋爱呢。比方说G1和a会恋爱,只是这种情况是不会出现的。

假如G1和a好,B1和b好。那么最大匹配中出现的是两条边G1->a B1->b。而不是如今的B1和G1.所以,既然最大匹配中选择了B1和G1,去掉他们中间的一个肯定是可行的。所以答案就是N-最大匹配了。

POJ3692:题目大意是,一群男孩B个(他们互相认识),一群女孩G个(他们互相认识),某些男孩和某些女孩相识。如今找出最多的孩子,他们互相认识
分析:这个题目和上面的有些类似。对于利用二分图最大匹配算法解题最重要不是匹配算法本身,而是怎样问题转化为二分图模型。一旦模型建立,就非常easy了。题目要找的是一群孩子,他们之间都互相认识。也就是说这是一个团(图的概念。随意两个顶点之间都有连线)。但是假设直接去找团。可能比較麻烦。

由于这是二分图,自然要利用二分图的性质。在二分图的算法里面没有找团的相关算法。所以我们能够考虑反问题。找出最多的孩子。他们之间互不认识,这不是就是求最大独立集嘛。建立这种二分图,左边是男孩,右边是女孩,假设男孩和女孩不认识就连上边,在这种二分图中,找最大独立集。事实上就是找出全部的相互认识的孩子了。

接下来就非常easy了。

此题说明模型的转化和构图非常重要。
POJ3041:题目大意是。一个矩阵,某些位置有小行星。有一种炸弹,一次能够炸掉一行或者一列,如今问题是须要最少用多少这种炸弹。
分析:模型转化。非常巧妙的利用二分图来解决。

利用二分图必须有左顶点和右顶点,我们把行作为左顶点。列作为右顶点,假设该行和该列的交点有小行星,就连线。求此二分图的最大匹配就是了。对这个问题展开思考,为什么能够这么转化。

事实上从最小顶点覆盖的角度来想比較好理解,左边的顶点和右边的顶点仅仅有当有小行星的时候才有连线,那么仅仅要找到最少的顶点把全部的边覆盖了。那么就是所求的解了。最小顶点覆盖等值于最大匹配
POJ1466:题目大意是。一群人N。某人可能是多某些人有罗曼史,性别未知,但一定是异性。找出最多的同学。他们之间无罗曼史
分析:由于性别未知,所以能够把全部的人当成左顶点,右边也是全部的人。建立二分图,能够想象,这样求出来的最大匹配是男女分开建立的二分图的最大匹配的二倍。而题目让找最大独立集,所以应该是N-最大匹配/2;
POJ1325:题目大意是,有两台机器,有多个任务。每一个任务都可在这两台机器上执行。只是不同的模式须要重新启动电脑。非常浪费时间,如今要找出最好的调度方式,降低调度时间。
分析:最少的顶点覆盖最多的边(任务)。所以是最小顶点覆盖问题
POJ2060:题目大意。有非常多人预订出租车,假设出租车做完一个任务能够敢到下一个任务,就不须要在调度一辆出租车了。如今请问最少须要几辆出租车。
分析:最小路径问题,对任务构图,将一个任务拆开成两个点,建立二分图,假设一个任务能够完毕之后赶到下个任务就连线,然后就是二分图问题了。最小路径等值于二分图的最大独立集
POJ2226:和3041类似,只是这里不是销毁一行或者一列,一次仅仅能销毁连着的一行或者一列。能够把全部的行连续的段拿出来作为左顶点,全部的列连续的段拿出来作为右顶点。假设左段与右段之间有相交。就连线。然后求最小顶点覆盖
POJ1422:最小路径覆盖
POJ2594:特殊的最小路径覆盖。每一个顶点能够有多条路径经过,这时须要事先把随意两点之间能否够到达求出,然后在求路径覆盖。
POJ1548:最小路径覆盖
POJ3216:最小路径覆盖

二分图最小顶点覆盖的证明
首先。回想一下二分图最小点覆盖的定义:
二分图中,选取最少的点数,使这些点和全部的边都有关联(把全部的边的覆盖)。叫做最小点覆盖。

最少点数=最大匹配数
结合昨天看的介绍,,今天依照我的理解给出自己的证明(原创,仅作參考,欢迎讨论)
从最大匹配数究竟能不能覆盖全部的边入手。
由于已知了最大匹配,全部再也不能找到增广路了。有最大匹配定义知。
如今全部的边就剩下两种情况了。一种是匹配,一种是不匹配。
假设全部的匹配边有n条,那么左右边就都有n个匹配边的顶点了,标记全部左边匹配边的顶点,则有n个。
问题就是证明n=最小点覆盖,即证明最大匹配数n究竟能不能覆盖全部的边入手。
考察右边的匹配边的顶点,明显。左边都能够找到其匹配点且为n,说明全部匹配边已经被这左边的n个点关联了。
接下来证明未匹配边也能被这左边的n个匹配的点关联那么不就证明了“,使这些点和全部的边都有关联(把全部的边的覆盖)”吗。

对于剩下的未匹配边,每条边都有一个右边点(显然既然是未匹配边。这个点自然是未匹配点)和左边点(我将证明着些左边点都是匹配边的顶点。证明了这一点。也就证明了这左边的n个点也和剩下的未匹配边关联了)
假设上面说的左边点不在这n个匹配边的左边点之中。那从剩下的某个未匹配边的右边点出发不就能够找到增广路了吗(想想增广路的定义就知道了,右未匹配。左未匹配的话那就能够找到增广路了),所以左边点也在匹配边之中,。所以就证明了剩下的未匹配边关联的范围也在这左边的n个匹配点的范围内力了。
也就证明了这n个左边匹配边的点既也右边匹配边关联,也与右边未匹配边关联了。即与全部边关联了。
那么依照最小覆盖的定义。接下来仅仅要证明这个n是做小值即可了。

假设能够比n小,那就相当于随便删一些匹配边,那么这些删除了边的右边点就没人匹配了。也就不满足与所以边关联了,所以矛盾,全部n就是最小值。
故得证。
主要从最小覆盖的定义的两个要点(1。能不能关联全部的边。

2,最小)来证明最大匹配的全部左边点就满足这个要求,匹配边有n条那自然匹配边的左边点就有n个了。

转载自:http://blog.sina.com.cn/s/blog_5ceeb9ea0100l08n.html

性质:
最大团 = 补图的最大独立集

最小边覆盖 = 二分图最大独立集 = |V| – 最小路径覆盖

最小路径覆盖 = |V| – 最大匹配数

最小顶点覆盖 = 最大匹配数

最小顶点覆盖 + 最大独立数 = |V|

最小割 = 最小点权覆盖集 = 点权和 – 最大点权独立集

不错的解说二分图大讲堂http://dsqiu.iteye.com/blog/1689505

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115431.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Python – 数据类型之字符串、数字

    Python – 数据类型之字符串、数字数据类型之字符串、数字

  • 补码的加减法运算_简述补码减法运算的规则

    补码的加减法运算_简述补码减法运算的规则补码的加减法运算本文内容参考自王达老师的《深入理解计算机网络》一书<中国水利水电出版社>一、补码加法:1、补码的加法运算两个机器数相加的补码可以先通过分别对两个机器数求补码,然后再相加得到,在采用补码形式表示时,进行加法运算可以把符号位和数值位一起进行运算(若符号位有进位,导致了益出,则直接舍弃),结果为两数之和的补码形式。示例1:求两个十进制数的和35+18。首先,规…

  • oracle数据库去重查询_oracle高效去重

    oracle数据库去重查询_oracle高效去重数据库多字段去重方法介绍:distinct关键字、groupby 、row_number()over()

  • 如何获取相应tableview中的touchesBegan事件[通俗易懂]

    如何获取相应tableview中的touchesBegan事件[通俗易懂]我

  • MySQL常用命令总结

    MySQL常用命令总结一.连接MySQL格式:mysql-h主机地址-u用户名-p用户密码或者:mysql-u用户名-p//回车后要求输入密码,密码不可见1、连接到本机上的MYSQL首先打开DOS窗口,然后进入目录mysql\bin,再键入命令mysql-uroot-p,回车后提示你输密码.注意用户名前可以有空格也可以没有空格,但是如果-p后带有用

  • SIGPIPE信号详解

    SIGPIPE信号详解SIGPIPE信号详解当服务器close一个连接时,若client端接着发数据。根据TCP协议的规定,会收到一个RST响应,client再往这个服务器发送数据时,系统会发出一个SIGPIPE信号给进程,告诉进程这个连接已经断开了,不要再写了。我写了一个服务器程序,在Linux下测试,然后用C++写了客户端用千万级别数量的短链接进行压力测试.  但是服务器总是莫名退出,没有cor

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号