文档介绍：二部图
2017/8/2
2 of 220
点覆盖集与点独立集的关系
0+0=n 点覆盖数+点独立数=点数
2017/8/2
3 of 220
关于匹配中的其他概念
定义设M为G中一个匹配.
(1) 匹配边——(vi,vj)M
(2) v为M饱和点——有M中边与v关联
(3) v为M非饱和点——无M中边与v关联
(4) M的交错路径——由匹配边和非匹配边交替构成的路径
(5) M的增广路径——起、终点都是M非饱和点的交错路径
2017/8/2
4 of 220
最大匹配判别定理
定理 M为G中最大匹配当且仅当G中不含M的可增广交错路径.
二部图匹配
匈牙利算法
2017/8/2
6 of 220
增广路径
匹配M={{x1,y1}, {x2,y3}, {x3,y4}}有一条增广路径
x1
x2
y1
y2
x3
x4
y3
y4
x1
x2
y1
y2
x3
x4
y3
y4
x1
x2
y1
y2
x3
x4
y3
y4
由M增广路径可构造比M大的匹配
存在M增广路径M非最大匹配
用(M-)(-M)代替M
x1
x2
y1
y2
x3
x4
y3
y4
2017/8/2
7 of 220
匈牙利算法
由增广路径的定义可以推出下述三个结论:
1、的路径长度必定为奇数,第一条边和最后一条边都不属于M。
2、经过取对称差操作可以得到一个更大的匹配M。
3、M为G的最大匹配当且仅当不存在关于M的增广路径。
2017/8/2
8 of 220
匈牙利算法
用增广路径求最大匹配(称作匈牙利算法)
算法:
(1)置M为空
(2)找出一条增广路,通过取对称差操作获得更大的匹配M代替M
(3)重复(2)操作直到找不出增广路径为止
2017/8/2
9 of 220
匈牙利算法示例
图1 图2
2017/8/2
10 of 220
匈牙利算法核心代码
#define N 202
int useif[N]; //记录y中结点是否使用
int link[N]; //记录当前与y结点相连的x的结点
int mat[N][N]; //记录连接x和y的边,如果i和j之间有边则为1,否则为0
int gn,gm; //二分图中x和y中点的数目