图论总结（一）二分图最大匹配

二分图最大匹配

（一）、二分图

1、定义

2、性质

定理：当且仅当无向图G的每一个环
的结点数均是偶数时，图G才是一个二分图。如果无环，相当于每的结点数为 0，故也视为二分图。

3、判定

如果一个图是连通的，可以用如下的染色法判定是否二分图：
我们把X部的结点颜色设为0，Y部的颜色设为1。
从某个未染色的结点u开始，做BFS或者DFS 。把u染为0，枚举u的儿子v。如果v未染色，就染为与u相反的颜色，如果已染色，则判断u与v的颜色是否相同，相同则不是二分图。
如果一个图不连通，则在每个连通块中作判定。

代码如下：

#include 
    #include 
    using namespace std; #define MAX_N 100 bool flag=true;//记录答案 bool G[MAX_N][MAX_N];//邻接矩阵 int m,n,Col[MAX_N+5];//记录边数、结点数和结点的颜色 queue<int>Q;//定义队列进行拓展 void Bfs(int x){ Q.push(x);//初始结点入队 Col[x]=0;//颜色为0 while(!Q.empty()){ int p=Q.front(); Q.pop(); for(int i=1;i<=n;i++) if(G[p][i]){ 
  //枚举相连结点 if(Col[i]==Col[p])//根据判定，相同颜色则不为二分图 flag=false;//记录答案 else if(Col[i]==-1){ Col[i]=!Col[p];//与之相反的颜色 Q.push(i);//入队拓展 } } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); G[u][v]=G[v][u]=true; } memset(Col,-1,sizeof Col);//初始状态都为-1 for(int i=1;i<=n;i++)//需要枚举每个结点，考虑多个连通块的情况 if(Col[i]==-1) Bfs(i); if(!flag) puts("False"); else puts("True"); }

（二）、二分图的匹配

1、二分图的最大匹配

2、 König定理及其证明

最小覆盖点数=最大匹配数

证明：首先，我们要抓住二分图最大匹配后的特点，此时，不存在增广路。如上图所示，该图为不完整的最大匹配后二分图。
红点为匹配点，蓝点未匹配。
对于一个点而言，他所连接的有这三种情况：
1、只连接了红点；
2、只连接了蓝点；
3、连接了红点和蓝。
在上面的图中，x与y所连接的边是匹配边。x连接了红点和蓝点， 这个时候y所连接的点一 所连接的点一定没有蓝点，如果有，就是一条新的增广路那么该图就不是最大匹配了。
在最大匹配图中不会出现一条边同时连接着两个蓝点。那么，对于一条边而言只有两种情况：
1、两端的点是红点；
2、两端的点一个红色，一个蓝色。
可知，一条边上，一定有红点，那么我们就选择红点作为覆盖点。
对于上面的匹配边xy，我们无论是选择x还是y都可以覆盖xy这条边， 但是对于图中的蓝点而言这条边， 但是对于图中的蓝点而言这条边， 但是对于图中的蓝点而言这条边， 但是对于图中的蓝点而言这条边，只能选择x作为覆盖点去覆盖那条边，这样，我们就选择x作为覆盖点，它所覆盖的边中既包括了与他相连的那些蓝点的边，也包括了xy这条匹配边。因为y点没有蓝色连接点，所以y不是必须选择的覆盖点，它与那些红点相连的边都可以选择那些红点来覆盖。所以，对于一条匹配边而言，我们只需要选择其中一个点就可以覆盖完整个二分图里的边了。
所以最小覆盖点数等于大匹配数。

3、最小边覆盖与最大独立集

最小边覆盖=最大独立集=总节点数-最大匹配数

（三）、增广路径

1、定义

增广路径的定义：设M为二分图G已匹配边的集合，若P是图G中一条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边 (即已匹配和待的边)在P上交替出现，则称P为相对于M的一条增广路径。
增广路径是一条“交错轨”。也就说 , 它的第一条边是目前还没有参与匹配的 ,第二条边参与了匹配 ,第三条边没有······最后一条边没有参与匹配 ,并且起点和终还没有被选择过，这样交错进行 ,显然 P有奇数条边。

2、性质

3、寻找增广路

红边为三条已经匹配的边。从X部一个未匹配的顶点x4 开始，找一条路径：找一条路径：
x4, y3, x2, y1, x1, y2
因为y2是Y部中未匹配的顶点，故所找路径是增广路径。
其中有属于匹配M的边为 {x2,y3},{x1,y1}
不属于匹配的边为{x4,y3},{x2, y1}, x1,y2}
可以看出：不属于匹配的边要多一条

如果从 M中抽走 {x2,y3},{x1,y1}并加入
{x4,y3},{x2, y1}, {x1,y2}，也就是将增广路所有的边进行 “反色”，则可以得到四条边的匹配M’={
{x3,y4}, {x4,y3},{x2, y1},{x1,y2}}
容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对。另外,单独的一条连接两个未匹配点边显然也是交错轨。可以证明 ,当不能再找到增广轨时,就得到了一个最大匹配。这也就是匈牙利算法的思路。
可知四条边的匹配是最大匹配。

（四）、匈牙利算法

1、找增广路经的算法

2、实践

匈牙利算法

/匈牙利算法/ #include 
  
    #include 
   
     #include 
    
      using namespace std; #define MAX_N 
     512 vector< 
     int>Adj[MAX_N]; 
     int n,m,ans; 
     void AddEdge( 
     int u, 
     int v){ Adj[u].push_back(v); Adj[v].push_back(u); } 
     /读入数据，建图*/ 
     void Init(){ scanf( 
     "%d%d",&n,&m); 
     for( 
     int i= 
     1;i<=n;i++){ 
     int si,k; scanf( 
     "%d",&si); 
     for( 
     int j= 
     1;j<=si;j++){ scanf( 
     "%d",&k); k+=n; AddEdge(i,k); } } } 
     /深搜找增广路/ bool Vis[MAX_N+ 
     1]; 
     int Match[MAX_N+ 
     1]; bool Dfs( 
     int u){ 
     for( 
     int i= 
     0;i 
     
       int v=Adj[u][i]; 
      if(Vis[v]) 
      continue; Vis[v]= 
      true; 
      if(!Match[v]||Dfs(Match[v])){ Match[v]=u; Match[u]=v; 
      return 
      true; } } 
      return 
      false; } 
      /*匈牙利算法主函数/ 
      void Solve(){ 
      for( 
      int i= 
      1;i<=n;i++){ memset(Vis, 
      false,sizeof Vis); 
      if(!Match[i]) 
      if(Dfs(i)) ans++; } } 
      int main(){ Init(); Solve(); printf( 
      "%d\n",ans); } 
      
     
    
  

3、算法分析

（五）、例题

1、最小点覆盖

2、最小边覆盖

3、最大独立集