二分图的相关性质

在二分图中有：

1). 二分图的最大匹配数等于其最小点覆盖数

点覆盖是指从图中找出一个点集 V，使得图中任意边与点集中某点相关，如果 V 集合中点数最小，称之为最小点覆盖集。

 

这个结论相信被很多人所知，然则如何去构造这个点覆盖集，这是一个值得思考的问题。

这个问题可以这样求解：

1. 对于在匹配中的点，随便选一个就行了。

2. 对于不在匹配中的点，我们用找类似找增广路径的方法找一条路径，路径中，非匹配边与匹配边交替出现。与增广路不同的是，该路径中有偶数条边，起点不在匹配中，终点在匹配中。然后取路径中第偶数个点为点覆盖集中的点，显然，所取的点能够覆盖这条路径中的所有边。

如下图中有：

这是一个最大匹配:

x1 为匹配点，先取 x1 作为最小点覆盖集中的点

x2 为非匹配点，找一条路径 x2-> y4-> x4-> y5-> x5, 取 y4, y5 为点集中的点

x3 为匹配点，取 x3 作为点集中的点

x4, x5 在 x2-> y4-> x4-> y5-> x5 的路径中已经覆盖。

故一个最小点覆盖集可以为 { x1, y4, y5, x3 }

 

2). 二分图的最大独立集为顶点数减去最大匹配数

 对于任何无向图有，最大独立数加上最大匹配数等于图的顶点数。

 对于任何无向图有，最大团等于补图的最大独立集。

 

代码( Zju 2333 MatScan )， 构造最小点覆盖集:

#include <stdio.h>
#include <stdlib.h>

int const N= 110;
int mat[N][N], mx[N], my[N], vx[N], vy[N], flag[N], n, m;
char g[N][N];

void build(){
    scanf("%d%d",&n,&m );
    for( int i= 0; i< n; ++i )
    scanf("%s", g[i] );

    for( int i= 0; i< n; ++i )
    for( int j= 0; j< m; ++j ){
        mat[i+1][j+1]= 0;
        if( g[i][j]== '*' ) mat[i+1][j+1]= 1;
    }
}

int dfs1( int x ){
    for( int y= 1; y<= m; ++y )
    if( mat[x][y] && !vy[y] ){
        vy[y]= 1;
        int t= my[y];
        if( t== -1 || dfs1(t) ){
            my[y]= x; return 1;
        }
    }
    return 0;
}

int max_match(){
    for( int i= 0; i<= m; ++i ) my[i]= -1;
    int ans= 0;
    for( int i= 1; i<= n; ++i ){
        for( int j= 0; j<= m; ++j ) vy[j]= 0;
        ans+= dfs1(i);
    }
    return ans;
}

void dfs2( int y ){
    vy[y]= 1;
    for( int x= 1; x<= n; ++x )
    if( mat[x][y] && !vx[x] ){
        vx[x]= 1;
        if( mx[x]!= -1 && !vy[ mx[x] ] ) dfs2( mx[x] );
    }
}

void solve(){
    printf("%d\n", max_match() );
    for( int i= 1; i<= m; ++i )
    if( my[i]!= -1 ) mx[ my[i] ]= i;
    
    for( int i= 0; i<= n; ++i ) vx[i]= 0;
    for( int j= 0; j<= m; ++j ) vy[j]= 0;
    
    for( int i= 1; i<= n; ++i )
    for( int j= 1; j<= m; ++j )
    if( mat[i][j] ) flag[j]= 1;
    
    for( int j= 1; j<= m; ++j )
    if( flag[j] && my[j]== -1 ) dfs2(j);
    
    for( int i= 1; i<= n; ++i )
    if( vx[i] ) printf("1 %d\n", i );
    
    for( int j= 1; j<= m; ++j )
    if( flag[j] && !vy[j] ) printf("2 %d\n", j );
    puts("");
}

int main(){
    int test;
    scanf("%d",&test );
    while( test-- ){
        build();
        solve();
    }
    
    return 0;
}