一、二分图最小点覆盖:
   给定一张二分图,求出一个最小的点集S,使得图中任意一条边都有至少一个端点属于S。这个问题被称为二分图的最小点覆盖,简称最小覆盖。

Konig定理:
   二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。

   
   证明:
   首先,因为最大匹配是原二分图边集的一个子集,并且所有的边都不相交,所以至少需要从每条匹配边中选出一个端点。因此,最小点覆盖包含的点数不可能小于最大匹配包含的边数。如果能对任意二分图构造出一组点覆盖,其包含的点数等于最大匹配包含的边数,那么定理就能得证。构造方法如下:
(1)求出二分图的最大匹配。

(2)从左部每个非匹配点出发,再执行一次DFS寻找增广路的过程(一定会失败),标记访问过的节点。

(3) 取左部未被标记的点、右部被标记的点,就得到了二分图最小点覆盖。

下面证明该构造的正确性。经过上述构造方法之后:
(1) 左部非匹配点一定都被标记——因为它们是出发点。
(2)右部非匹配点一定都没被标记——否则就找到了增广路。
(3)一对匹配点要么都被标记,要么都没被标记——因为在寻找增广路的过程中,左部匹配点只能通过右部到达。
在构造中,我们取了左部未被标记的点、右部被标记的点。根据上面的讨论我们可以发现,恰好是每条匹配边都取了一个点,所以选出的点数等于最大匹配包含的边数。

再来讨论这种取法是否覆盖了所有的边:
(1) 匹配边一定被覆盖——因为恰好有一个端点被取走。
(2)不存在连接两个非匹配点的边——否则就有长度为1的增广路了。
(3)连接左部非匹配点 i,右部匹配点 j 的边——因为 i 是出发点,所以 j 一定被访问。而我们取了右部所有被标记的点,因此这样的边也被覆盖。
(4)连接左部匹配点 i ,右部非匹配点 j 的边——i 一定没有被访问,否则再走到 j 就找到增广路。而我们取了左部所有未被标记的点,因此这样的边也被覆盖。

   证毕。

二分图最小覆盖的模型特点:每条边有2个端点,二者至少选择一个,我们称之为 2要素。
   
   
   
   
二、二分图最大独立集:
   定义:
   给定一张无向图G=(V,E),满足下列条件的点集S被称为图的独立点集:
   (1)S含于V。
   (2)任意的x,y∈S,(x,y)不属于E。
通俗的讲,图的独立集就是 任意两点之间都没有边相连 的点集。包含点数最多的一个就是图的最大独立集。
对应的,任意两点之间都有一条边相连 的子图被称为无向图的团。点数最多的团被称为图的最大团。
   
   定理:
   无向图G的最大团等于其补图GG的最大独立集。
   注:GG=(V,EE)被称为G=(V,E)的补图,其中EE={ (x,y)不属于E}。
   正确性显然。值得提醒的是,在一些题目中,补图转化思想能成为解答的突破口。
   对于一般无向图,最大团、最大独立集是NPC问题。
NPC问题:即NP完全问题,是理论计算机科学中有关计算复杂性的一个概念。到目前为止,尚未找到任何NPC问题的多项式时间解法。换言之,此类问题难解,目前只能使用暴力搜索等方法计算。

   
   定理:
   设G是有n个节点的二分图,G的最大独立集的大小等于n减去最大匹配数。
证明:
   选出最多的点构成独立集
   等价于 在图中去掉最少的点,使剩下的点之间没有边
   等价于 用最少的点覆盖所有的边
   因此,去掉二分图的最小点覆盖,剩余的点就构成二分图的最大独立集。而最小点覆盖数等于最大匹配数。故最大独立集大小等于n减去最大匹配数。

   
   
   
三、有向无环图的最小路径点覆盖:
   定义:
   给定一张有向无环图,要求用尽量少的不相交的简单路径,覆盖有向无环图的所有顶点(也就是每个顶点恰好被覆盖一次)。这个问题被称为有向无环图的最小路径点覆盖,简称最小路径覆盖。
   设原来的有向无环图为G=(V,E),n = | V |。把G中的每个点x拆成编号为x和x+n的两个点。建立一张新的二分图,1----n作为二分图左部点,n+1----2n作为二分图的右部点,对于原图的每条有向边(x,y),在二分图的左部点x与右部点y+n之间连边。最终得到的二分图称为G的拆点二分图,记为G2.
   
   定理:
   有向无环图G的最小路径点覆盖包含的路径条数,等于n减去拆点二分图G2的最大匹配数。
证明:
   在有向无环图G=(V , E)的最小路径覆盖中,对于任意的x∈V,因为路径不相交,所以x的入度和出度都不超过1。因为每个节点都被覆盖,所以x的入度和出度至少有一个是1。

   因此,最小路径覆盖的所有边,在拆点二分图G2中构成一组匹配。最小路径覆盖中每条边(x,y)的起点x与二分图每条匹配边(x,y+n)是一一对应的。
   
   特别的,对于每条路径的终点t,因为t没有出边,所以在二分图中,t匹配失败。即路径的终点和二分图左部的非匹配点是一一对应的。
   
   路径覆盖包含的路径条数最少
   等价于 路径的终点数(出度为0的点数)最少
   等价于 二分图左部非匹配点数最少
故G的最小路径覆盖的路径数等于n减去拆点二分图G2的最大匹配数。

   
   
   最小路径可重复点覆盖:
   给定一张有向无环图,要求用尽量少的可相交的简单路径,覆盖有向无环图的所有顶点(也就是一个节点可以被覆盖多次)。这个问题被称为有向无环图的最小路径可重复点覆盖。

   在最小路径可重复点覆盖中,若两条路径u -> p -> v 和 x -> p -> y在p点相交,则我们在原图中添加一条边(x,y),让第二条路径直接走 x -> y,就可以避免重复覆盖点p。

   进一步地,如果我们把原图中所有间接连通地点对x,y直接连上有向边(x,y),那么任何 有路径相交的点覆盖 一定能转化成 没有路径相交的点覆盖

   综上所述,有向无环图G的最小路径可重复点覆盖,等价于先对有向图传递闭包,得到有向无环图GG,再在GG上求一般的(路径不可相交的)最小路径点覆盖。

例题:hihoCoder 1127 二分图最小点覆盖和最大独立集:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define ll long long
using namespace std;
const int _max=1005;
const int maxn=10005;
int head[_max],ver[maxn],nt[maxn];
int match[_max];
bool ha[_max];
int tot;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

bool dfs(int x)
{
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(!ha[y])
        {
            ha[y]=true;
            if(!match[y]||dfs(match[y]))
            {
                match[y]=x;
                return true;
            }
        }
    }
    return false;
}

int main(void)
{
    memset(match,0,sizeof(match));
    memset(head,0,sizeof(head));
    tot=0;
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(ha,0,sizeof(ha));
        if(dfs(i)) ans++;
    }

    printf("%d\n%d\n",ans/2,n-ans/2);

    return 0;
}

四、无向二分图的最小路径覆盖:
无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2
给定一张二分图,求出一个最小的边集E,使得图中任意一个点都是边集E的某个顶点。

无向图的最小路径覆盖:
无向图的最小路径覆盖与二分图的匹配有公式:
无向图最小路径覆盖数=顶点数—二分图最大匹配数/2
当求一个无向图的最小路径覆盖时,我们就要试图构造一个与这个无向图相一致的二分图:
运用拆点的技术,将无向图中的每一个顶点 i 拆成两个点 i 和 i′ (复制),两个点分别属于不同的顶点集。
无向图中的边相当于双向边,即将 i 到 j 的边拆分成 i 到 j’ 的边和 j 到 i’ 的边
(大概就是直接建立无向图就好啦,其中一部分看作左部顶点,一部分看作右部顶点)
接下来就可以通过匈牙利算法求出最大匹配数。