讲二分图 之前 我先提下关于它的各种基础概念 在了解一个新的算法 应该有必要将关于它的概念 有所了解
1.什么是二分图?
:二分图 又叫做二部图 是图论中的一种特殊模型 设G=(V,E)是一个无向图 如果顶点V可以分割为两个互不相交的子集(A，B) 并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这个不同的顶点集(i in A j in B) 则称G为一个二分图（这是官方的定义 感觉也是最详细的)
2.什么是匹配？
匹配是 基于二分图上提出的概念。 给定一个二分图G M为G边集的一个子集 如果M满足当中的任意两条边都不依附于同一个顶点
则称M是一个匹配
3.什么是二分图 极大匹配?
是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数
4.什么是二分图 最大匹配？
所有极大匹配当中边数最大的一个匹配 同通俗来说就是----在匹配的基础上选择边数最大的子集称为最大匹配
5.增广路（增广轨 交错轨)是什么？
若P是图G中一条连通两个未匹配顶点的路径 并且属于M的边喝不属于M的边(即已匹配和未匹配的边)在P上交替出现
则称P为相对于M的一条增广路径
(sample: 有A B集合 增广路由A中一个点通向B中一个点 再由B中这个点通向A中一个点
就是这样交替进行下去.)
由增广路的定义引申出的三个结论：
1.P的路径长度必定为奇数 第一条边喝最后一条边都不属于M
2.不断寻找增广路可以得到一个更大的匹配M‘
直到找不到更多的增广路
3.M为G的最大匹配当且仅当不存在M的增广路径
6.最小点覆盖数 是什么？
即要求用最少的点(A B任意一集合)让每条边至少和其中一个点相关联
可以证明: 最小点覆盖数 == 最大匹配数（证明过程这里不给出
希望读者自行查阅)
7.独立集是什么？
图G中两两互不相邻的顶点构成的集合
可以证明: 最大独立集 == 顶点数 - 二分图最大匹配（同上 证明过程不予给出 请自行查阅)
8.最小路径覆盖是什么?
简而言之-就是找出最小的路径条数 使之成为P的一个路径覆盖
一个PXP的有向图中 路径覆盖就是在图中找一些路径使之覆盖了图中所有的顶点
且任何一个顶点有且只有一条路径与之关联(如果把这些路径中的每条路径从它们起始点走到它的终点 那么恰好经过图中的每个顶点一次仅且一次) 如果不考虑图中存在回路
那么每条路径就是一个弱连通子集
得出的结论:
1.一个单独的顶点是一条路径
2.如果存在一路径p1,p2,......pk 其中p1 为起点 pk为终点
那么在覆盖图中顶点p1,p2,......pk不再与其它的顶点之间存在有向边
可以证明： 最小路径覆盖 == |P|-二分图最大匹配 (同上)
看完上面这么一大堆概念 是不是和我一样头晕了。。。 还是先去撸一把吧?
继续... 这里我们给出一道例题来更好的理解：
题目链接 ： http://acm.nyist.net/JudgeOnline/problem.php?pid=239
这题 应该是最简单的 二分图最大匹配应用题 题意也很好转换 即是求 二分图最大匹配
同样 对于图的信息存储 这里同样可以用邻接表 或 邻接矩阵
先去上课了~~
原文：http://www.cnblogs.com/radical/p/3666783.html