二分图及其应用

《二分图及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ACM程序设计计算机学院刘春英7/15/20211今天，请个假,下周调课(西安)7/15/20212每周一星（8）：050721207/15/20213第九讲二分图及其应用（BipartiteGraph&Applications）7/15/20214主要内容什么是二分图二分图的最大匹配匈牙利算法二分图的最小顶点覆盖DAG图的最小路径覆盖二分图的最大独立集处理技巧7/15/20215什么是二分图？如果一个图的顶点可以分为两个集合X和Y，图的所有边一定是有一个顶点属于集合X，另一个顶点属于集合Y，则称

2、该图为“二分图”（BipartiteGraph）7/15/20216例：婚配问题男女7/15/20217二分图的最大匹配在二分图的应用中，最常见的就是最大匹配问题，很多其他的问题都可以通过转化为匹配问题来解决。7/15/20218如何求二分图的最大匹配呢？7/15/20219经典算法：匈牙利算法7/15/202110/*hdoj_1150匈牙利算法月下版*/#include#include#includeusingnamespacestd

3、;boolmark1[100],mark2[100];intlist[100];intn,m,edge,num;vector>v;booldfs(intto){registerinti,point,s=list[to];for(i=0;i

4、

5、dfs(point)){lis

6、t[point]=s;returntrue;}}returnfalse;}voidSolve(){inti,j,point;boolflog=false;memset(mark1,true,sizeof(mark1));memset(list,-1,sizeof(list));num=0;for(i=0;i

7、=i;num++;if(i==0)flog=true;break;}}for(i=0;i

8、

9、dfs(point)){list

10、[point]=i;num++;break;}}}mark1[i]=false;}}if(flog

11、

12、list[0]!=-1)cout<>n){if(n==0)break;v.clear();v.resize(n);cin>>m>>edge;for(i=0;i>j>>s>>d;v[s].push_back(d);

13、}Solve();}return0;}7/15/202111匈牙利算法(求二分图最大匹配)谈匈牙利算法自然避不开Hall定理Hall定理：对于二分图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有：

14、T(A)

15、>=

16、A

17、7/15/202112图示（1）：男1男2女1女2女3返回7/15/202113图示（2）：男1男2女1女2女3返回X0=男2V1={男2}V2=ΦT(V1)={女1}Y=女1V1={男2，男1}V2={女1

18、}Y=女2M←M⊕E(P)(其中，P是从x0→y的可增广道路)7/15/202114匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：1．任给初始匹配M；2．若X已饱和则结束，否则进行第3步；3．在X中找到一个非饱和顶点x0，作V1←{x0},V2←Φ；4．若T(V1)=V2则因为无法匹配而停止，否则任选一点y∈T(V1)V2；5．若y已饱和则转6，否则做一条从x0→y的可增广道路P，M←M⊕E(P)，转2；6．由于y已饱和，所以M中有一条边(y,z)，作V1←V1∪