二分图学习笔记

Sweetlemon · 2018-10-18 21:55:12 · 个人记录

二分图

定义

二分图又称双分图、二部图、偶图，指顶点可以分成两个不相交的集U和V，U和V皆为独立集（即同一个集内的顶点没有共同边）的图。（摘自维基百科）

即如果能把某一个图的顶点集V划分为两个集合A和B，使得图中的每一条边都是由A中的顶点连向B中的顶点（或反之），那么就称这个图为二分图。

判定

二分图有两三种判定方法。

染色。如果一个图的所有顶点都可以被指定一个颜色，这个颜色是0或1，且每一条边所连接的两个顶点的颜色都不同，那么这个图就为二分图。
奇环定理。一个图是二分图，当且仅当这个图中没有奇环（即经过边数为奇数的环）。

~~证明留作习题~~

算了，这个稍微证明一下。

首先，二分图与可以染色的等价性是容易证明的，只要把同色顶点划分到一个集合中去就好了。

接着证明奇环定理。这个证明用到了下面的“另一个判定方法”。

引理1：如果无权无向图中存在两点(u,v)，它们之间存在两条长度奇偶性不同的路径，那么这个图存在奇环。

证明：设这两条路径分别为u\rightarrow v, v\rightarrow u，那么u\rightarrow v\rightarrow u的长度为奇数，且构成一个环。证毕。

引理2：如果一个无向图无法进行黑白染色，那么这个图中一定存在两点(u,v)，它们之间存在两条长度奇偶性不同的路径。

证明：采用反证法。如果图中不存在两点(u,v)，使得它们之间存在两条长度奇偶性不同的路径；
那么每个连通块任取一个顶点（记为该连通块的1号点），把到1号点路径长度为奇数的点染上白色，到1号点路径长度为偶数的点染上黑色，就完成了黑白染色（这时同色点之间一定无连边）。证毕。

结合这两个引理，就很容易证明奇环定理了。

补充：带权冰茶姬判断二分图。

二分图的另一个判定方法：在无权图中，如果任意两点间的任何路径长度的奇偶性都相同，就说明这个图是二分图。（上面引理用到的条件）

证明方法：在有奇环的图中，一个点绕奇环奇数次回到自己的路径长是奇数，走了上述路径后再走路径到达另一点，所走所有路径长之和奇偶性和原来不同。

判断方法：对图中每一条边连边，冰茶姬中维护每一个点到根的距离\pmod{2}。

当连接在同一冰茶姬中的两个点时，若这两个点到根的距离之和为奇数，则满足条件；否则不满足二分图条件。

当连接不在同一冰茶姬中的两个点时，在\text{root}(x)和\text{root}(y)之间连边。若把\text{root}(x)并到\text{root}(y)上，则\text{dis}(\text{root}(x))=\text{dis}(x)+1+\text{dis}(y)（上式中的1指边x\rightarrow y）。在\mod{2}的运算中，加法可以表现为位运算的异或。

证明上述方法要点：一条边走两遍不影响\text{dis} \mod{2}的值。

也可以把“每一个点到根的距离\pmod{2}”理解为“这个点是否和根在二分图同一侧”，结合异或的性质可以很容易理解。

注意：路径压缩时如何维护\text{dis}数组？

int ufind(int x){
    if (uset[x]==x)
        return x;
    int raw_par=uset[x];
    uset[x]=ufind(raw_par);
    dis[x]=dis[x]^dis[raw_par];
    return uset[x];
}

例题

设n\in \mathbb{N}^{*}，n\le 15，集合A,B都是I=\left\{1,2,\cdots,n\right\}的真子集，A\cap B=\varnothing，A\cup B=I. 证明：集合A或B中，必有两个不同的数，它们的和为完全平方数。
（《奥数教程高中第一分册第1讲集合的概念与运算例6》）

我们把集合I视作一个图G的顶点集，对两个和为完全平方数的顶点连边，那么这道题其实就是证明G不是二分图。根据二分图的判定方法2，我们只需证明图中有奇环即可。我们发现1\rightarrow 3\rightarrow 6\rightarrow 10\rightarrow 15\rightarrow 1是一个奇环，因此G不是二分图，证毕。
将正整数集\mathbb{N}_{+}分为两个集合使得
(1)1\in A
(2)A中任意两个元素之和都不具有2^{k}+2(k\in \mathbb{N})的形式
(3)B也具有性质(2)
证明：这样的分划是唯一的。
（《奥数教程高中第一分册第22讲集合的分划练习题7》）

一个连通的二分图的分划只有两种，如果指定了某一个元素所属的集合，这样的分划就是唯一的。于是我们只需证明这个图是连通的即可。
我们对两个和具有2^{k}+2(k\in \mathbb{N})的形式的两个顶点连边，经过考察，我们发现这个图不仅是连通图，还是一棵树！（证明方法是，对于每一个x\in \mathbb{N},x>1，有且仅有一个y\in \mathbb{N},0<y<x，使得x+y=2^{k}+2(k\in \mathbb{N})。我们只要把y作为x的父亲节点即可。）于是这道题也解决了。

这道题被改编为了数学社某次周赛题。

二分图染色

用\text{dfs}和\text{bfs}均可，时间复杂度为\text{O}(n)。

二分图匹配

致谢

下文参考和摘录了Renfei Song's Blog - 二分图的最大匹配、完美匹配和匈牙利算法这篇文章的内容，在此向原作者表示感谢！

定义

若M是二分图G的子图，且M中的任意两条边都没有公共顶点，那么就称M为G的一个匹配。

“匹配点”指M中连边的点，“非匹配点”指G中除了匹配点以外的其他点；“匹配边”指M中的边，“非匹配边”指M中除了匹配边以外的其他边。

显然，匹配点的个数v和匹配边的条数e之间存在关系v=2e。

下面的图3和图4都是二分图匹配的例子，其中红色的边是匹配边。图3中1,4,5,7是匹配点，图4中1,2,3,4,5,6,7,8是匹配点。

一个图所有匹配中，所含匹配边数最多的匹配（当然也可以定义为所含匹配点数最多的匹配），称为这个图的最大匹配。图 4 是一个最大匹配，它包含 4 条匹配边。

如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。显然，完美匹配一定是最大匹配（匹配点不可能再多），但并非每个图都存在完美匹配。

匈牙利算法

匈牙利算法是利用“增广路”求最大匹配的算法。首先我们来看一下什么是“交替路”和“增广路”。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边、匹配边...，形成的简单路径叫交替路。

增广路：起点和终点均为非匹配点的交替路称为增广路。例如，图 5 中的一条增广路如图 6 所示（图中的匹配点均用红色标出）：

增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。

我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（这是增广路定理）。匈牙利算法正是这么做的。

摘录了这么多，为什么可以利用增广路来找最大匹配呢？下面我解释一下。

首先，我们要从二分图的集合A中找到一个非匹配点（如果找不到，就说明这已经是最大匹配了，算法结束），下面我们的目标就是对它进行匹配。

从哪里去找匹配呢？肯定只能从和它连边的顶点去找呀。如果和它连边的顶点中有某一个是非匹配点，那么就匹配成功了。此时找到的这条路正是增广路（既满足交替路的条件，又满足起点和终点都是非匹配点）。

如果和它连边的顶点都是匹配点了怎么办？放弃吧！~~南三科艺楼，一跃解千愁~~

不行呢，要热爱生命（逃）。如果和它连边的顶点都是匹配点，有可能是之前的匹配不合适。如下图，与3顶点连边的都是匹配点，但是我们很容易就能看出来这个匹配不合适，如果把顶点1改成和6匹配，那么顶点3就可以和5顺利匹配了。

因此，下一步应该是，让顶点3和顶点1“协商”，请顶点1寻找另一个匹配点。这样问题就转化为了对顶点1进行匹配。这时我们可以理解为先走非匹配边3\rightarrow 5，再走匹配边5\rightarrow 1；接下来顶点1由于不能继续和原来的配对点5配对，必须走非匹配边1\rightarrow 6。而且走环是没有意义的（只会导致死循环）。从而我们证明了，这样一个过程走的是交替路。

如果在上述过程中，某一个A中的顶点找到了与之相邻的非匹配点，那么显然它就可以改成和这个新找到的非匹配点相匹配，从而之前的假设“更换匹配点”就满足了。这时的路径便是一条增广路。或者按照上文增广路的特点来理解，更换增广路中匹配边和非匹配边的身份，也可以增加匹配数。总之，如果这个点有可能匹配成功，就能通过增广路的方法进行匹配。

接下来是一个小优化（效果很好）。“如果一直没有找到增广路，则不再从这个点开始搜索。事实上，此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去，而不影响结果。”

这是什么意思呢？就是说，如果对B中的某个节点，与它匹配的A中节点没有办法更换匹配点，那么我们就可以给B中的这个节点打上一个“你是我的唯一”不可替代的标记，今后再尝试匹配时就不需要再和B中的这个节点进行协调了。

上面这一段的内容有问题。如果是递归的某一层（不是顶层）找不到可更换的匹配，可能原因是，这个点其实是可以换匹配的，但是需要和它的上层协调（它的上层当前还没有更换到合适的匹配），而为了防止死循环，我们规定下层不能和上层协调，因此这次会返回失败。当然，如果顶层匹配失败，那就一定没有匹配，可以给这个点打上一个“单身狗”标签（笑）。

给一组数据：

匈牙利算法的时间复杂度是\text{O}(nm)，是不是和\text{SPFA}的时间复杂度一样呢？事实上，匈牙利算法和\text{SPFA}一样，实际运行时间往往并没有理论上的那么糟。

匈牙利算法的实现

以P3386 【模板】二分图匹配为例。这道题A集合和B集合中的顶点编号是重复的，要格外注意。

下面是\text{bfs}版本的代码。(215\text{ms}，无优化928\text{ms})

#include <cstdio>
#define MAXM 1000005
#define MAXN 1005
#define MAXQ 1005
using namespace std;
int g[MAXM]; //Graph array
int fst[MAXN]={0},nxt[MAXM]={0}; //Fore list
int prev[MAXN]={0}; //prev means the last vertex which wanted to match
int ans=0; //Ans means the count of matching edges
int match[MAXN]={0}; //Match (A->B)
int invmatch[MAXN]={0}; //Match (B->A)
int que[MAXN]; //Don't use std::queue! It's slow.
int visited[MAXN]; //Only for vertexes in B
int unable_stack[MAXN]={0}; //Store the vertexes (in B) which are going to be unable
void hungarian(int x);
int main(void){
    int n,m,e;
    scanf("%d%d%d",&n,&m,&e);
    for (int i=0;i<e;i++){
        int u,v;
        int edge_num=i+1;
        scanf("%d%d",&u,&v);
        if (v>m)
            continue; //According to the tips
        //Only connect edges from A to B
        g[edge_num]=v;
        nxt[edge_num]=fst[u];
        fst[u]=edge_num;
    }
    for (int i=1;i<=n;i++)
        if (!match[i]) //i hasn't found a vertex to match with
            hungarian(i);
    printf("%d\n",ans);
    return 0;
}

void hungarian(int x){
    int head,tail,st; //Queue head, queue tail, stack top
    head=tail=0;
    que[tail++]=x; //Notice: every vertex in que is in A
    prev[x]=0; //Prev means the vertex which asks i to change its matching vertex
    st=0;
    while (head!=tail){ //!q.empty()
        int nowv=que[head++];
        //nowv means the current vertex which wants to change its matching vertex
        if (head==MAXQ)
            head=0;
        //Cycling queue
        for (int i=fst[nowv];i;i=nxt[i]){
            if (visited[g[i]]==-1 || visited[g[i]]==x)
            //The visited array is similar to the "inq" tag
            //visited[x]==-1 means it can't be replaced
                continue;
            unable_stack[st++]=g[i]; //Push g[i] to the stack
            //If this match fails, visited[g[i]] will be set to -1
            visited[g[i]]=x; //Notice: the index of visited means vertexes in B
            if (!invmatch[g[i]]){
                //If g[i] isn't a matching vertex
                int nowv_to_match=g[i];
                int prev_to_match;
                ans++; //Find a new matching edge
                while (nowv){
                    //Go back in order to update the matching vertexes
                    prev_to_match=match[nowv];
                    match[nowv]=nowv_to_match;
                    invmatch[nowv_to_match]=nowv;
                    nowv=prev[nowv];
                    nowv_to_match=prev_to_match;
                }
                //Match successfully, return
                return;
            }
            //Ask invmatch[g[i]] (the vertex which matches with g[i]) to change its matching vertex
            que[tail++]=invmatch[g[i]];
            prev[invmatch[g[i]]]=nowv; //Set down the prev
            if (tail==MAXQ)
                tail=0;
        }
    }
    //Match failed
    //Set the visited value of all the vertexes which I have asked to change to -1
    while (st){
        st--;
        visited[unable_stack[st]]=-1;
    }
}

下面是\text{dfs}版本的代码（262\text{ms}，无优化1042\text{ms}）。

#include <cstdio>
#define MAXM 1000005
#define MAXN 1005
using namespace std;
int g[MAXM]; //Graph array
int fst[MAXN]={0},nxt[MAXM]={0}; //Fore list
int ans=0; //Ans means the count of matching edges
int rnd=0; //Means the round of dfs
int match[MAXN]={0}; //Match (A->B)
int invmatch[MAXN]={0}; //Match (B->A)
int visited[MAXN]; //Only for vertexes in B
int hungarian(int x);
int main(void){
    int n,m,e;
    scanf("%d%d%d",&n,&m,&e);
    for (int i=0;i<e;i++){
        int u,v;
        int edge_num=i+1;
        scanf("%d%d",&u,&v);
        if (v>m)
            continue; //According to the tips
        //Only connect edges from A to B
        g[edge_num]=v;
        nxt[edge_num]=fst[u];
        fst[u]=edge_num;
    }
    for (int i=1;i<=n;i++){
        if (!match[i]){ //i hasn't found a vertex to match with
            rnd=i;
            if (hungarian(i))
                ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

int hungarian(int x){
    for (int i=fst[x];i;i=nxt[i]){
        if (visited[g[i]]==-1 || visited[g[i]]==rnd)
        //The visited array is similar to the "inq" tag
        //visited[x]==-1 means it can't be replaced
            continue;
        visited[g[i]]=rnd; //Notice: the index of visited means vertexes in B
        if (!invmatch[g[i]] || hungarian(invmatch[g[i]])){
            //If g[i] isn't a matching vertex or its matching vertex has successfully changed
            match[x]=g[i];
            invmatch[g[i]]=x;
            return 1;
        }
    }
    //Match failed
    //Set the visited of match[x] to -1
    if (match[x])
        visited[match[x]]=-1;
    return 0;
}