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

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

二分图:
二分图又称二部图，是图论中的一种特殊模型。设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