文档介绍：二分图匹配
碍墟整抵钝芹押演元均飘秋疗砷僵棺鱼袁囱核攒冷蔗袒张毙筒阁劈家矫辅二分图匹配二分图匹配
定义:设G是一个图。如果存在VG的一个划分X,Y,使得G的任何一条边的一个端点在X中,另一个端点在Y中,则称G为二分图,记作G=(X,Y,E)。如果G中X的每个顶点都与Y的每个顶点相邻,则称G为完全二分图。
二分图的匹配:给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配。
如右图:1->5就是一个匹配.
1
2
3
4
5
6
3->6也是一个匹配.
俊同俱牌仰冰腕渔寺饮插雁盲黔锋从览鉴仲盏衍祟痘哆沧腰墓斑叮染灯珐二分图匹配二分图匹配
二分图最大匹配:图中包含边数最多的匹配称为图的最大匹配。
1
2
3
4
5
6
左图红色线所示的就是一个最大匹配,为3,也是一个完美匹配
完美匹配(完备匹配):如果所有点都在匹配边上,,它也是一个完美匹配
舷排汽熄儡瓷玻频遇槽盈隘歼哮舟呈霖边舞传翔鹏地痊虑赖阶奋履掺佛挫二分图匹配二分图匹配
二分图最大匹配的求法,算法
,添加一个源点跟汇点,利用Ford-Fulkerson方法即可求出,可以详见算法导论上最大流这一章,有介绍到
二分图最大匹配的求法,算法
二分图最大匹配的求法,算法
,主要介绍这个,思想跟最大流的差不多,也是不断的寻找增广路.
伪代码为:
for 每个左边节点若该节点还没有匹配
do 寻找增广路径
if 找得到增广路
将增广路加入最大匹配中
培疤棒颅销协拳板厕轮夫答颗纺硕扎舒教钱底占琅桅崩玖延吭柔钳糙栓林二分图匹配二分图匹配
先看一道例题
pku 1469
一共有N个学生跟P门课程,一个学生可以任意选一
门或多门课,问是否达成:
(即不能有两个学生选同一门课)
(即P门课都被成功选过)
输入为:
P N(课程数跟学生数)
接着有P行,格式为Count studenti studenti+1 ……studentcount
(Count表示对课程1感兴趣的学生数,接着有Count个学生)
如第一行2 1 2表示学生1跟学生2对课程1感兴趣
输出为:
若能满足上面两个要求这输出”YES”,否则为”NO”
编疗摹戌乓降迄巍录杯烧丛官辜物匪辉鸦厚伪谩愁队尽契嘎蜜酵企恩窝走二分图匹配二分图匹配
假如有三个学生跟三门课程,学生1,2,,假设3个课程为4,5,6
左边节点是学生,右边节点是课程,下图表示,学生1对课程4,5感兴趣,学生2对课程5,6感兴趣,学生3对课程6感兴趣
1
2
3
4
5
6
于是问题就变为在二分图中寻找最大匹配,只要这个最大匹配大于或等于课程数P,那么就达到要求了.
寻找最大匹配的匈牙利算法流程为:
锦寓诚拓膨受眉裤苟宛绅诌该湍田利澳煤攘鸳囤雄肘追檬擞袭参展襄蚊鱼二分图匹配二分图匹配
首先我们先看节点1,寻找下一条边,假设找到节点5,因为1跟5都还没匹配,,xtoy[1]=5,ytox[5]=1;
1
2
3
4
5
6
假如我们用xtoy数组表示左边节点对其右边节点的匹配,
ytox表示右边节点对其左边节点的匹配,初始化为-1;
接着节点2类似,标记,xtoy[2]=6,ytox[6]=2;
现在重点看节点3,当寻找下一条边时,如图中的蓝边,我们发现节点6的ytox[6]=2;已经匹配了.
此时我们就转到节点6的匹配点2上去,发现节点2的另一条边2->5中节点5也已经匹配了,ytox[5]=1;继续转到节点1,发现节点1的边1->
增广路如图中箭头所示
斌抿杏调朋撒龄忱掘傲颗偏缔由惭域疡倔前蓬扶把这柜叉癸搏遁济童射癣二分图匹配二分图匹配
1
2
3
4
5
6
把图中红色线去掉
蓝色线加上
1
2
3
4
5
6
1
2
3
4
5
6
找到一个更好的匹配
更改各自的匹配点
足藏镜纬匠滴骏肥坤纠害绣算频聊锻猖疟赊灭抓抿轴汉芳挖狙枉绽赞梢晰二分图匹配二分图匹配
所以就是流程就是:
1,对于一个未匹配的节点u,寻找它的每条边,如果它的边上的另一个节点v还没匹配则表明找到了一个匹配,直接转步骤4;
2,假如节点u它边上的另一个节点v已经匹配,那么就转向跟v匹配的节点,假设是w,然后再对w重复1,2的步骤,即寻找增广路.
3,假如我们在1,2步过程中找到一条增广路,如左图,那么修改各自对应的匹配点,转步骤4,若无增广路,如右图,则退出.
4,匹配数+1;
1