二分图的性质及其应用（konig定理)

  写在之前：更多二分图知识，请关注--->二分图知识导航篇

性质

二分图中，点覆盖数是匹配数。
　　（1）二分图的最大匹配数等于最小覆盖数，即求最少的点使得每条边都至少和其中的一个点相关联，很显然直接取最大匹配的一段节点即可。
　　（2）二分图的独立数等于顶点数减去最大匹配数，很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。
　　（3）DAG的最小路径覆盖，将每个点拆点后作最大匹配，结果为n-m，求具体路径的时候顺着匹配边走就可以，匹配边i→j',j→k',k→l'....构成一条有向路径。

（4）最大匹配数=左边匹配点+右边未匹配点。因为在最大匹配集中的任意一条边，如果他的左边没标记，右边被标记了，那么我们就可找到一条新的增广路，所以每一条边都至少被一个点覆盖。

（5）最小边覆盖=图中点的个数-最大匹配数=最大独立集。

转自其他博主。

  本章内容主要讲解其中的最大匹配数=最小覆盖数，这性质也叫konig定理，引用最广的证明来自博主Matrix67，这里我就不贴原文(转载)了，我就用我的话来理解下他的证明。

图解

  且看第1图，这是一个已经找到最大匹配的二分图，橘线代表最终的匹配边，实心圈是已经匹配好的顶点，空心圈是没有找到匹配的顶点。其中有两个集合B和G，这里我们选择以G集为出发集，B集为被匹配集。

图1

   根据证明，我们要找到最小覆盖点，就要从G集里找到未匹配点（如6和9），然后对每个未匹配点进行增广路的查找，查找过程中，所遇到的所有点将被记录，也就是做记号。下面图2和图3就是对点6和9寻找增广路的过程，绿色代表寻找路径，并且绿色的点代表对其做了记录，记住是从6和9出发，为起点。

图2

图3

  完成这一过程后，来看最后被记录(绿色)的点有哪些，见下面图4。

图4

  然后我们将从这两个集合里找点，其中在出发集G里找没有被标记的点（7），在被匹配集B里找被标记的点（2，4），见图5。

图5

  最后得到点2、4、7，这就是最小覆盖点了，刚好3个，跟最大匹配边数一样。根据博主Matrix67的反证法式的证明，这些最小覆盖点一定是匹配边的某个端点(从图5可知)，那么m条最大匹配边，至少用m个点来代表即覆盖（二分图的匹配是一一匹配）。这也是我对找最小覆盖点思路的理解了。下面看一道例题(UVa 11419)，来分析代码怎么具体实现。

描述

  给出一个R*C大小的网格，网格上面放了一些目标，可以在网格外发射子弹，子弹会沿着垂直或者水平方向飞行，并且打掉飞行路径上的所有目标。你的任务是计算出最少需要多少子弹，各从哪些位置发射，才能把所有目标全部打掉。

• Input
• The input file contains several test cases. Here, the temple is defined as a R × C grid. The first line of each test case contains 3 integers: R (0 < R < 1001), C (0 < C < 1001) representing the grid of temple (R means number of row and C means number of column of the grid) and the number of enemies N (0 < N < 1000001) inside the temple. After that there are N lines each of which contains 2 integers representing the position of the enemies in that temple. Each test case is followed by a new line (except the last one). Input is terminated when R = C = N = 0.
• Output
• For each test case there will be one line output. First print the minimum number (m) of cannonballs needed to wipe out the enemies followed by a single space and then m positions from which he can shoot those cannonballs. For shooting horizontally print ‘r’ followed by the row number and for vertical shooting print ‘c’ followed by the column number. If there is more than one solution any one will do.
• Sample Input
• 4 4 3
• 1 1
• 1 4
• 3 2
• 4 4 2
• 1 1
• 2 2
• 0 0 0
• Sample Output
• 2 r1 r3
• 2 r1 r2

题目分析

  每个敌人，所占的坐标，就代表了x轴和y轴的一个关系，即横打和纵打的一个关系。然后观察横打和纵打的关系，如果你从第一行横着打，你会将第一行所有敌人清空，但不会影响到其他行的敌人；如果你从第一列竖着打，你将会清空第一列的所有敌人，但不会影响其他列的敌人，这里的敌人代表关系。从这样的角度来看，很明显可以分成一个二分图，而出发集和被匹配集可以分为x轴和y轴。根据输出要求，是要将覆盖点输出，并且是最少覆盖点，因为要用最少的点（炮弹）关联（轰掉）所有的关系（敌人）。

解题思路

  因为要求最少覆盖点的具体值，所以不能仅仅求出最大匹配数(匈牙利算法)就完了。而是要在求完最大匹配数后，再对出发集中未匹配点再进行一边增广路的查找(匈牙利算法)。然后根据出发集未被标注的点，和被匹配集标注的点，来输出攻击方向和位置。下面代码中，我用X轴横着打作为出发集，也就是r；用Y轴竖着打作为被匹配集，c。（因为受经典男女配对题目的影响，我习惯用Girl表示出发集，Boy表示被匹配集。）

AC代码

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
const int N = 1010;
int line[N][N];     //新建可搭配数组
int gUsed[N],bUsed[N];
int Girl[N],Boy[N];
vector<int> h;
vector<int> v;
int k,m,n;
int r,c,e,x,y;

bool found(int x){
    gUsed[x] = 1;   //第x横坐标被标记
    for(int i = 1; i <= c; i++){    //遍历所有纵轴点
        if(line[x][i] && !bUsed[i]){     //如果第x横坐标和第i纵坐标有关系(出现敌人)，并且第i纵坐标还没被用过，就进行选择
            bUsed[i] = 1;   //第i纵坐标被标记
            if(Boy[i] == 0 || found(Boy[i])){   //如果第i纵坐标还没被任何人横坐标搭配过，或者说选择第i纵坐标的横坐标还有其他纵坐标可选(DFS)
                Girl[x] = i;    //第x横坐标选择了第i纵坐标
                Boy[i] = x;     //第i纵坐标选择了第x横坐标
                return 1;       //并返回1
            }
        }
    }
    return 0;   //如果没有选择的对象，就返回0
}

int main(){
    while(1){
        scanf("%d %d %d",&r,&c,&e);
        if(r == 0 && c == 0 && e == 0)
            break;
        memset(line, 0, sizeof(line));
        for(int i = 0; i < e; i++){
            scanf("%d %d",&x,&y);
            line[x][y] = 1;     //标记关系，也是记录敌人位置
        }
        int sum = 0;     //最大匹配数，也是最小覆盖数
        memset(Girl, 0, sizeof(Girl));
        memset(Boy, 0, sizeof(Boy));
        for(int i = 1; i <= r; i++){        //遍历所有横轴点
            memset(gUsed, 0, sizeof(gUsed));    //用于记录出发集X里的顶点有没有被使用
            memset(bUsed, 0, sizeof(bUsed));    //用于记录被匹配集Y里的顶点有没有被使用
            if(found(i))    //看下一个横坐标能否匹配成功
                sum++;
        }
        printf("%d",sum);   //输出最小覆盖数
        v.clear();
        h.clear();
        memset(gUsed, 0, sizeof(gUsed));    //用于记录出发集X里的顶点有没有被使用
        memset(bUsed, 0, sizeof(bUsed));    //用于记录被匹配集Y里的顶点有没有被使用
        for(int i = 1; i <= r; i++){
            if(!Girl[i])    //出发集里还未匹配的点
                found(i);   //寻找增广路，并标记经过的点
        }
        for(int i = 1; i <= r; i++){
            if(!gUsed[i])   //出发集X里，所有没有被打记号的
                h.push_back(i);     //记录位置
        }
        for(int i = 1; i <= c; i++){
            if(bUsed[i])    //被匹配集Y里，所有被打了记号的
                v.push_back(i);     //记录位置
        }
        for(int i = 0; i < h.size(); i++){
            printf(" r%d",h[i]);    //预设出发集为横轴，所以输出r
        }
        for(int i = 0; i < v.size(); i++){
            printf(" c%d",v[i]);    //预设被匹配集为纵轴，所以输出c
        }
        puts("");
    }
    return 0;
}

此外还有最大独立集合和DAG最小路径覆盖的应用，见其他文章。