定义 任何无回路的的图均是二分图 最大独立数（无向图）: 从V个顶点中选出k个点，使得这k个点互不相邻。 那么最大的k就是这个图的最大独立数。 最大团（无向图）: 从V个顶点选出k个点，使得这k个点构成一个完全图，即该子图任意两个点都有直接的边。 最小边覆盖(二分图)： 在图中找一些边，使之覆盖了图中所有顶点，且任何一个顶点有且只有一条边与之关联。 最小顶点覆盖(二分图)： 用最少的点（左右两边集合的点）让每条边都至少和其中一个点关联。 最小路径覆盖（有向图，拆点构造二分图）： 在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联。 最小链覆盖（有向图，拆点构造二分图）： 用最少的链，经过所有的点至少一次 最长反链（有向图，拆点构造二分图）： 反链是一个点的集合，这个集合中任意两点谁也不能走到谁 最小点权覆盖集：（带点权的无向图） 点权之和最小的点覆盖集 最大点权独立集：（带点权无向图） 点权之和最大的点独立集
匹配 匹配(matching)是一个边集，满足边集中的边两两不邻接。 匹配又称边独立集(edge independent set)。 在匹配中的点称为匹配点(matched vertex)或饱和点；反之，称为未匹配点(unmatched vertex)或未饱和点。 交错轨(alternating path)是图的一条简单路径，满足任意相邻的两条边，一条在匹配内，一条不在匹配内。 增广轨(augmenting path)：是一个始点与终点都为未匹配点的交错轨。 最大匹配(maximum matching)是具有最多边的匹配。 匹配数(matching number)是最大匹配的大小。 完美匹配(perfect matching)是匹配了所有点的匹配。 完备匹配(complete matching)是匹配了二分图较小集合（二分图X，Y中小的那个）的所有点的匹配。 增广轨定理：一个匹配是最大匹配当且仅当没有增广轨。所有匹配算法都是基于增广轨定理，一个匹配是最大匹配当且仅当没有增广轨。这个定理适用于任意图。
关系： 适合普遍图： 对于不存在孤立点的图，最大匹配+最小边覆盖=顶点数 最大独立集+最小顶点覆盖=顶点数 最大团 = 补图的最大独立集 最小割 = 最小点权覆盖集 = 点权和 - 最大点权独立集
局限于二分图 最大匹配=最小顶点覆盖 最小边覆盖 = 最大独立集 = |V| - 最大匹配数
N x N的有向图： （需根据原图构造二分图，构造方法是将点一分为二，如，i分为i1和i2，如果i和j有边，那么就在i1和j2之间连一条边） 最小路径覆盖 =原图的点的个数－原图最小路径覆盖中的边数=原图的点的个数-新造二分图的最大匹配 （二分图中寻找最大匹配M,就是找到了对应DAG中的非路径结尾顶点的最大数目,那么DAG中顶点数-|M|就是DAG中结尾顶点的最小数目,即DAG的最小路径覆盖数.） Dilworth定理：最小链覆盖数 = 最长反链长度 最长链长度 = 最小反链覆盖数 （求最小链覆盖数的方法，就是首先传递闭包，然后就变成了最小路径覆盖）
求最大匹配 EK算法 匈牙利算法（有关此算法可参考下面链接）
参考： http://dsqiu.iteye.com/blog/1689505 http://blog.csdn.net/leolin_/article/details/7199688 http://blog.csdn.net/pi9nc/article/details/11848327 http://blog.csdn.net/flynn_curry/article/details/52966283 http://blog.csdn.net/wall_f/article/details/8187144 http://www.cnblogs.com/icode-girl/p/5418461.html
