图论 - 二分图

定义

二分图 又称作二部图,是图论中的一种特殊模型。 设 ((G=(V,E))) 是一个无向图,如果顶点(V)可分割为两个互不相交的子集((U,V)),并且图中的每条边((i,j))所关联的两个顶点(i)(j)分别属于这两个不同的顶点集,则称图(G)为一个二分图。

一个无向图为二分图的充要条件是没有奇环。

二分图染色

求解算法

思路

判定一个图是否为二分图,使用dfs进行黑白染色,判定能否满足每条边的两个顶点异色。

实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=10050,MAXM=10050;
int n,m,cnt,col[MAXN],head[MAXN],ans;
struct edge
{
    int v,next;
}e[MAXM*2];
void addedge(int x,int y)
{
    e[++cnt]=(edge){y,head[x]};
    head[x]=cnt;
    return;
}
bool dfs(int u,int x)
{
    if(col[u])
    {
        if(col[u]==x)return true;
        return false;
    }
    col[u]=x;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(!dfs(v,x==1?2:1))return false;
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    bool flag=true;
    for(int i=1;i<=n;++i)
        if(!col[i])
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
    flag?puts("Yes"):puts("No");
    return 0;
}

二分图最大匹配

定义

又称最大边独立集,即边数最多的匹配。

有关概念

匹配:又称边独立集,一个边集,满足边集中的任两边不邻接。

极大匹配:又称极大边独立集,本身是匹配,加入任何边就不是。

增广路:连接两个未匹配结点的路径,且已匹配边和未匹配边在路径上交替出现,可以发现非匹配边的数量比匹配边的数量多(1),故将路径上的每一条边取反就能使匹配边的数量(+1)

求解算法

匈牙利算法

思路
  1. 在图中找出增广路;
  2. 对增广路上每一条边取反(即匹配边改为非匹配边,非匹配边改为匹配边);
  3. 重复以上两步直到找不到增广路为止。
样例推导

给出二分图:

《图论 - 二分图》

(X1)开始,找到增广路(X1-Y1),标记(X1-Y1)为匹配边;

《图论 - 二分图》

(X2)开始,找到增广路(X2-Y1-X1-Y3)

《图论 - 二分图》

标记(X1-Y1)为非匹配边,标记(X1-Y3,X2-Y1)为匹配边;

《图论 - 二分图》

(X3)开始,找到(X3-Y1-X2),不是增广路;

《图论 - 二分图》

找到增广路(X3-Y2),标记(X3-Y2)为匹配边;

《图论 - 二分图》

(X4)开始,找到(X4-Y3-X1-Y1-X2),不是增广路;

《图论 - 二分图》

找到增广路(X4-Y4),标记(X4-Y4)为匹配边。

《图论 - 二分图》

至此找出最大匹配。

实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=,MAXM=;
int n,m,cnt,match[MAXN],head[MAXN],ans;
bool vis[MAXN];
struct edge
{
    int v,next;
}e[MAXM*2];
void addedge(int x,int y)
{
    e[++cnt]=(edge){y,head[x]};
    head[x]=cnt;
    return;
}
bool Hungary(int u)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(!vis[v])
        {
            vis[v]=true;
            if(!match[v]||Hungary(match[v]))
            {
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof(vis));
        if(Hungary(i))ans++;
    }
    printf("%dn",ans);
    return 0;
}

网络流解法

思路

建立源点,向(Xi)连边,容量为(1)

若二分图中有边(i,j),则从(Xi)(Yj)连边,容量为(1)

建立汇点,(Yi)向汇点连边,容量为(1)

使用最大流算法解决。

二分图最小点覆盖

定义

点数最少的点覆盖。

有关概念

点覆盖:一个点集,满足所有边至少有一个端点在集合里。

极小点覆盖:本身是点覆盖,其所有真子集都不是。

求解算法

König 定理:最小点覆盖大小=最大匹配数。

首先,二分图最大匹配满足图中没有增广路;

假设最大匹配数为(n),则(X)部和(Y)部都各有(n)个匹配点,覆盖了(n)个匹配边;

对于非匹配边,若它的两个端点都是非匹配点,那么这条非匹配边成一个增广路,和二分图最大匹配的性质不符,故非匹配边的两个顶点一定是一个匹配点和一个非匹配点,于是这个非匹配边会被这个匹配点覆盖;

(X)部的(n)个匹配点或(Y)部的(n)个匹配点都可以覆盖所有边,故最小点覆盖大小为(n)

二分图最大独立集

定义

点数最多的独立集。

有关概念

独立集:一个点集,集合中任意两个点不相邻。

极大独立集:本身是独立集,再加入任何点就不是。

求解算法

最大独立集大小=总点数-最大匹配数。

可以用上面的结论:非匹配边的两个顶点一定是一个匹配点和一个非匹配点,故不存在两个非匹配点之间有边,故非匹配点构成独立集;

又有不存在增广路能使最大匹配数变大而使这个独立集变小,故这个独立集是最大独立集。

二分图最大团

定义

点数最多的团。

有关概念

团:一个点集,集合中任意两个点都相邻,对于二分图来说,我们默认(X)部的每个点之间和(Y)部的每个点之间都有边,故二分图的团是在(X)部找一个点集(S_x),在(Y)部找一个点集(S_y),使得(S_x)中的每一个结点和(S_y)中的每个结点之间都有边。

补图:包含原图的所有结点,原图中若两个结点(Xi,Yj)之间有边,则补图中没有,否则补图中有。

极大团:本身为团,再加入任何点都不是。

求解算法

最大团=补图的最大独立集。

补图中不相邻的两个结点在原图中一定相邻。

二分图最小边覆盖

定义

边数的最小边覆盖。

有关概念

边覆盖:一个边集,使得所有点都与集合中的边邻接。

极小边覆盖:本身是边覆盖,其所有真子集都不是。

求解算法

最小边覆盖大小=总点数-最大匹配数。

首先设最大匹配数为(n),总点数为(m),每个匹配边可以不重复地覆盖(2)个点,故覆盖了(2n)个点;

剩下的每条边最多只能覆盖(1)个点,故剩下(m-2n)个点需要(m-2n)条边来覆盖,故最小边覆盖大小为(m-2n+n=m-n)

DAG最小路径覆盖

定义

用尽量少的不相交简单路径覆盖DAG的所有顶点。

有关概念

DAG:有向无环图。

链:一个点集,其中任意两点(u)(v)可以到达,要么(u)能走到(v),要么(v)能走到(u)

反链:一个点集,其中任意两点均不可到达。

最大(长)反链:反链中点数最多的一个(=最小路径覆盖数)。

求解算法

思路

由最小路径覆盖数=DAG的点数-最小路径覆盖的边数。

把原图的所有节点拆成(Xi)(Yi),如果DAG中存在边(i,j)就在二分图中连有向边(Xi,Yj),跑二分图匹配。

容易得出最大匹配数就是最小路径覆盖的边数,故最小路径覆盖数=DAG的点数-最大匹配数。

二分图最大权匹配

定义

若二分图的每条边都有一个权值(v[i][j]),求一种完美匹配,使得所有匹配边的权值和最大,记做最优完美匹配。

有关概念

完美匹配:又称完备匹配,匹配了所有点的匹配。

可行顶标:对于二分图的每个点给定一个顶标值,用(lx[i])记录(X)部的顶标,用(ly[i])记录(Y)部的顶标。对于图中任意一条边((Xi,Yj))满足(lx[i]+ly[j]geq v[i][j])

相等子图:原图的一个生成子图,包含原图的所有点,但是只包含(lx[i]+ly[j]=v[i][j])的边(可行边)。

求解算法

KM算法

思路

定理:如果原图的一个相等子图中包含完美匹配,那么这个匹配就是原图的最佳完美匹配。

初始化(lx[i]=max{v[i][j]},quad 1leq jleq n)(ly[i]=0),此时满足(lx[i]+ly[j]geq v[i][j])

我们通过修改顶标的方式扩大相等子图,寻找完美匹配。

(X)部的每一个点开始增广,保证增广路径上都是可行边:

若能找到一条增广路,这个点完成配对;

否则在当前增广路径上的所有(X)部结点顶标减去(a),所有(Y)部顶标加上(a)

此时有如下四种情况:

  1. (Xi)(Yj)都属于增广路径,(lx[i]+a+ly[j]-a)不变,故((i,j))仍然为可行边。
  2. (Xi)(Yj)都不属于增广路径,(lx[i]+ly[j])不变,故((i,j))可行性不变。
  3. (Xi)不属于增广路径,(Yj)属于增广路径,(lx[i]+ly[j]+a)增大,((i,j))仍然不可能加入相等子图。
  4. (Xi)属于增广路径,(Yj)不属于增广路径,(lx[i]-a+ly[j])减小,((i,j))有可能会加入相等子图。

所以进行修改操作后,原来的可行边仍然可行,不可行边有可能加入相等子图。

上述四种情况只有第四种可行性可能发生改变,故取所有第四种情况的边,(a=min{lx[i]+ly[i]-v[i][j]})

这样就能保证每次都有至少一个边加入相等子图。

实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=,INF=0x3f3f3f3f;
int n,e[MAXN][MAXN],match[MAXN],lx[MAXN],ly[MAXN],slack[MAXN];
bool visx[MAXN],visy[MAXN];
bool dfs(int x)
{
    visx[x]=true;
    for(int y=1;y<=n;++y)
    {
        if(visy[y])continue;
        int t=lx[x]+ly[y]-e[x][y];
        if(!t)
        {
            visy[y]=true;
            if(!match[y]||dfs(match[y]))
            {
                match[y]=x;
                return true;
            }
        }
        else slack[y]=min(slack[y],t);
    }
    return false;
}
int KM()
{
    memset(match,0,sizeof(match));
    memset(ly,0,sizeof(ly));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            lx[i]=max(lx[i],e[i][j]);
    for(int i=1;i<=n;++i)
    {
        memset(slack,0x3f3f3f3f,sizeof(slack));
        while(true)
        {
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            if(dfs(i))break;
            int d=INF;
            for(int j=1;j<=n;++j)if(!visy[j])d=min(d,slack[j]);
            for(int j=1;j<=n;++j)
            {
                if(visx[j])lx[j]-=d;
                if(visy[j])ly[j]+=d;
                else slack[j]-=d;
            }
        }
    }
    int ret=0;
    for(int i=1;i<=n;++i)ret+=e[match[i]][i];
    return ret;
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                scanf("%d",&e[i][j]);
        printf("%dn",KM());
    }
    return 0;
}

网络流解法

思路

建立源点,向(Xi)连边,容量为(1),费用为(0)

若二分图中有边(i,j),则从(Xi)(Yj)连边,容量为(INF),费用为权值的相反数(由于费用流求出的是最小费用);

建立汇点,(Yi)向汇点连边,容量为(1),费用为(0)

使用费用流算法解决。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据