先了解一下基本的知识：

转自：http://blog.sina.com.cn/s/blog_89a06c7d0100trcg.html

二分图:

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

匹配：

给定一个二分图，在G的一个子图G’中，如果G’的边集中的任意两条边都不依附于同一个顶点，则称G’的边集为G的一个匹配

最大匹配：

在所有的匹配中，边数最多的那个匹配就是二分图的最大匹配了

顶点覆盖：

在顶点集合中，选取一部分顶点，这些顶点能够把所有的边都覆盖了。这些点就是顶点覆盖集

最小顶点覆盖：(=最大匹配数)

在所有的顶点覆盖集中，顶点数最小的那个叫最小顶点集合。

独立集：

在所有的顶点中选取一些顶点，这些顶点两两之间没有连线，这些点就叫独立集

最大独立集： (=原点数-最大匹配数)

在左右的独立集中，顶点数最多的那个集合

路径覆盖：

在图中找一些路径，这些路径覆盖图中所有的顶点，每个顶点都只与一条路径相关联。

最小边覆盖：(=原点数-最大匹配数)

最小路径覆盖：(=原点数-新构造的图的最大匹配数)

在所有的路径覆盖中，路径个数最小的就是最小路径覆盖了。

=====================================================================================================================================================================

有一个经常被数据忽略的地方(关于最小路径覆盖)：

转自：http://www.cnblogs.com/ka200812/archive/2011/07/31/2122641.html

首先，最小路径覆盖=总节点数-最大匹配数。这个应该已经是路人皆知了。

所谓最小路径覆盖，是指在一个有向图中，找出最少的几条路径，用它们来覆盖全图

这里说的值得注意的地方，如果有向图的边有相交的情况，那么就不能简单的对原图求二分匹配了

举个例子，假设有图：1->2     2->5     2->3      4->2，事实上，这其实就是两条边：1->5  4->3 ，节点2只是他们的一个交点

如果只是简单的在原图的基础上求二分匹配，那么得到的匹配答案是2，最小路径覆盖答案便是5-2=3。

可是随便一看都能看看出端倪，这个图中，只需要两个点便可以探索完整个地图，这里最小路径覆盖数明显是2。

问题究竟出在哪里呢？其实就和这个交点2有关。既然边有相交，那么他们的连通性也应该连通下去。

解决的办法是对原图进行一次闭包传递(也就是flody)，于是便增加了四条边:1->3   1->5   4->3  4->5

这时再求最大匹配数，匹配答案便是3，最小路径覆盖值为2，这是正确答案！

具体问题可见 PKU 2594 Treasure Exploration

最小路径覆盖和最小边覆盖：

边覆盖集：通俗地讲，所谓边覆盖集，就是G中所有的顶点都是E*中某条边的邻接顶点（边覆盖顶点），一条边只能覆盖2个顶点。

注意：在无向图中存在用尽量少的边去“覆盖”住所有的顶点，所以边覆盖集有极小与最小的区别。

极小边覆盖：若边覆盖E*中的任何真子集都不是边覆盖集，则称E*是极小边覆盖集。

最小边覆盖：边数最小的边覆盖称为最小边覆盖，通俗地讲，就是极小边覆盖中的最小的一个集合。

最小边覆盖在二分图中的应用：

最小边覆盖 = 最大独立集 = n - 最大匹配，这个是二分图上的一个性质。

最小路径覆盖与最小边覆盖的区别

最小路径覆盖和最小边覆盖不同，不要求给的图是二分图，而是要求是PXP的有向图，不能有环，然后根据原图构造二分图，构造方法是将点一分为二（拆点），v分为v*和v**然后如v*和u**有边，那么就在v*和u**之间连一条边。

然后最小路径覆盖是n-m，n为原图的点的个数，m为新造二分图的最大匹配。证明也特别简单，根据定义最小路径覆盖里要求同一个点只可以属于一条路径，即路径时不可以开叉的，如果在二分图里选两条有公共点的边那么反应在原图上就是路径有岔路，那么就不符合匹配的定义了,所以二分图里选的边必须是无公共交点的，这转化到最大匹配了。 

=====================================================================================================================================================================

二分图匹配算法：

匈牙利算法： http://blog.csdn.net/akof1314/article/details/4421262