二分图匹配
Bi-partite graph
二分图的定义：
二分图是这样的一个图，它的顶点可以 分为两个集合X和Y。所有的边关联的两个顶点 中，恰好一个属于集合X，一个属于集合Y。
二分图的匹配：
1
4
给定一个二分图G，M为
G边集的一个子集，如果M满 2
5
足当中的任意两条边都不依
附于同一个顶点，则称M是一 3 个匹配。
（1）M个是足够的。只需要让它们覆盖最大匹配 的M条边，则其它边一定被覆盖（如果有边e不被 覆盖，把e加入后得到一个更大的匹配）
（2）M个是必需的，仅考虑形成最大匹配的这M 条边，由于它们两两之间没有公共点，因此至少需 要M个点才可以把它们覆盖
PKU 3041:(类似的有PKU3020)
问题: 假如你现在正处在一个N*N的矩阵中,这个矩阵里面 有K个障碍物,你拥有一把武器,一发弹药一次能消灭 一行或一列的障碍物,求最小的弹药消灭全部障碍物
如果找到，则把它取反
（即增加了总了匹配数）。
看一道例题：PKU 1469
PKU 1469
一共有N个学生跟P门课程,一个学生可 以任意选一门或多门课,问是否达成: 1.每个学生代表的都是不同的课（如果 一个学生选修的那门课，那么他就可 以代表这门课） 2.每门课都有一个代表
PKU1469
输入为: P N(课程数跟学生数) 接着有P行,格式为Count studenti studenti+1 ……studentcount (Count表示对课程1感兴趣的学生数,接着有Count个学
1
4
1
4
2
5 把图中红色线去掉
2
5
蓝色线加上
3
6
3
6
1
4
更改各自的匹配点
找到一个更好的匹配 2
5
3
6
总结
所以流程就是:
1,对于一个未匹配的节点u,寻找它的每条边,如果它的边上 的另一个节点v还没匹配则表明找到了一个匹配,直接转步 骤4;
2,假如节点u它边上的另一个节点v已经匹配,那么就转向跟 v匹配的节点,假设是w,然后再对w重复1,2的步骤,即寻找增 广路.
3,假如我们在1,2步过程中找到一条增广路, 那么修改各自 对应的匹配点,转步骤4,若无增广路, 则退出.
4,匹配数+1;
最小点覆盖
最小覆盖： 最小覆盖要求用最少的点（Ｘ集 合或Ｙ集合的都行）让每条边都至少和其中一 个点关联。可以证明：最少的点（即覆盖数） ＝最大匹配数 M
简单的证明如下：
输入为: NK 接下来有K行,每行包含障碍物的坐标,即r行c列; 如:
34 11 13 22 32 输出为: 花费最小的弹药数
PKU3041
对于上面那个数据我们可以用下面的表示,0表示无障 碍物,,我们利用行跟列做二分图:
行
列
如果第i行的第j列有障碍物,则在图中
1
1
4 于是问题就变为在二分图中寻找最大
2
5 匹配,只要这个最大匹配大于或等于
课程数P,那么就达到要求了.
3
6
寻找最大匹配的匈牙利算法流程
假如我们用xM数组表示左边节点对其右边节点的匹
1
4 配,
yM表示右边节点对其左边节点的匹配,初始化为-1;
2
5
首先我们先看节点1,寻找下一条边,假设找到节点
3
5,因为1跟5都还没匹配,所以找到一个匹配.标记 6 ,xM[1]=5,yM[5]=1;
增广路如图中箭头 所示
现在重点看节点3,当寻找下一条边时,如图中的蓝 边,我们发现节点6的yM[6]=2;已经匹配了.
此时我们就转到节点6的匹配点2上去,发现节点2的 另一条边2->5中节点5也已经匹配了,yM[5]=1;继续 转到节点1,发现节点1的边1->4中节点4还没匹配.于 是我们找到了一个增广路径
生) 如第一行2 1 2表示学生1跟学生2对课程1感兴趣 输出为: 若每门课都能找到一位代表则输出”YES”,否则为”NO”
PKU1469
假如有三个学生跟三门课程,学生1,2,3.为了跟学生 区分,假设3个课程为4,5,6
左边节点是学生,右边节点是课程,下图表示,学生1 对课程4,5感兴趣,学生2对课程5,6感兴趣,学生3对 课程6感兴趣
6
二分图的最大匹配
定义： 图中包含边数最多的匹配称为图的最
大匹配。
如右图所示：蓝色部分 就构成一个最大匹配， 同时它也是一个完美匹 配
完美匹配： 如果所有点都在匹配边上，称这个最大 匹配是完美匹配。
二分图的最大匹配
匈牙利算法（时间复杂度O(nm)）
其思想是用宽度优先搜索来找增广路径（和 floodfill算法类似
Input: 3 34 13 23
Output: 2
1
1’
1
4
2
2’
3
3’
2
3
4
4’
二分图的最大独立集
最大独立集问题： 在Ｎ个点的图G中选出m个点，使 这m个点两两之间没有边．求m最大值．
记住一个重要的结论： 二分图的最大独立集数=节点数(n)-最大匹配数
黑色点即为一个最大独立集
可以这样理解，在总的点集中，去掉最少的点， 使得剩下的点相互之间没有边。用最少的点去 覆盖所有的边，也就是最小覆盖。
1
左边的i行连一条边到右边的j列,上面
的数据就对应左图
2
2
于是问题就转化成最小点覆盖的问题
3
3
.求最大匹配即可.
PKU2226
现在我们看一道构图比较复杂的题：PKU2226
DAG图的最小路径覆盖
用尽量少的不相交简单路径覆盖有向无环 (DAG)G的所有顶点，这就是DAG图的最小路 径覆盖问题。
解决此类问题可以建立一个二分图模型。把所 有顶点i拆成两个：Ｘ结点集中的i和Y结点集中 的i',如果有边i->j，则在二分图中引入边i->j'， 设二分图最大匹配为m,则结果就是n-m
记住一个重要的结论： DAC图的最小路径覆盖数=节点数(n)-最大匹配数 看一道例题：PKU1422
PKU1422
有一个城镇，它的所有街道都是单行的，并且 每条街道都是和两个路口相连。同时已知街道 不会形成回路。
你的任务是编写程序求最小数量的伞兵，这些 伞兵可以访问（visit）所有的路口。对于伞 兵的起始降落点不做限制。
转化为单位容量简单网络的最大流问题
在二分图的基础上，加入源点s和汇点t，让s与 每个X结点连一条边，每个Y结点和t连一条边 ，所有弧的容量为1。这样，饱和弧就对应着 匹配边。
二分图的最大匹配
匈牙利算法：
寻找增广路：
初始时最大匹配为空 for 二分图左半边的每个点i do 从点i出发寻找增广路径