图论——二分图

二分图又称作二部图，是图论中的一种特殊模型。

G=(V, E)是一个无向图 如果G的顶点集V可分割为两个互不相交的子集X和Y，并且E中每 条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分 图，记为G=(X,Y,E)。

由定义可知，二分图的这两个部分中的任意两个顶点之间没有路径

无向图 G 为二分图的充分必要条件是，G 至少有两个顶点，且其所有回路的长度均为偶数。

Question：给定一个无向联通图，如何判定该图是否为一个二分图？

染色法：参考博文：http://www.cnblogs.com/1227xq/p/6826783.html

　　　　　　　　　https://www.cnblogs.com/digitalhermit/p/5119908.html

(1) 二分图的判定 [邻接表]

　　 对二分图的结点进行染色。如果处于同一组，则应该染成同色，否则为不同色。在染色过程中，如果发生矛盾，说明此图不是二分图。

　　这种方法就像涂颜色一样，相邻（若有边相连）则染成不同色，反之染成同色，若矛盾，则false，反之true

下面为自作代码+借鉴代码

邻接链表

#include<bits/stdc++.h>
#define N 100000

using namespace std;

struct node{
    int to,next;
}e[N];
int head[N],tot,n,m;
bool vis[N],colar[N];
void add(int u,int v){
    e[++tot].to=v;e[tot].next=head[u];head[u]=tot;
}

bool dfs(int k){
    vis[k]=1;
    for(int i=head[k],v;i,v=e[i].to;i=e[i].next){
        if(vis[v]==0){
               colar[v]=!colar[k];
        }else {
            if(colar[v]!=colar[k]) return true;
        }
    }
}//判断函数退出，默认返回false

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int u,v;
          cin>>u>>v;add(u,v);add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            if(dfs(i)==1){
                printf("NO
");
                break;
            }
        }
    }printf("YES
");
    return 0;
}
View Code

vector（STL神器）

#include<bits/stdc++.h>
#define N 100000

using namespace std;

vector<int>G[N];

int colar[N];

bool dfs(int u,int c){
    colar[u]=c;
    for(int i=0;i<G[u].size();i++){
        if(colar[G[u][i]]==c) return false;//如果相邻的顶点同色，就剪掉这一枝，返回false
        if(colar[G[u][i]]==0&&!dfs(G[u][i],-c)) return false;//如果相邻的顶点还没有染色就把它染成-c
    }return true;
}

void solve(){
     for(int i=1;i<=n;i++){
        if(vis[i]==0){
            if(dfs(i,0)==0){
                printf("NO
");
                return;
            }
        }
    }printf("YES
");
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int u,v;
          cin>>u>>v;
          G[u].push_back(v);
          G[v].push_back(u);
    }solve();
    return 0;
}
View Code

这段代码更容易理解：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define N 1000
#define M 2000
int col[N],cnt,n,m,head[N],to[M],next[M];
void add(int x,int y){
    next[++cnt]=head[x];
    to[cnt]=y;
    head[x]=cnt;
}
void dfs(int u,int c){
    col[u]=c;
    for(int v,i=head[u];i;i=next[i]){
        v=to[i];
        if(!col[v])
          dfs(v,-c); // 染 -c 
        if(col[v]==col[u]){ // 有冲突 
            printf("NO");
            exit(0);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int x,y,i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!col[i])
            dfs(i,1); // 默认 染色 1 
    printf("YES");
    return 0;
}
View Code

并查集（神奇的做法）

我们可以将每个节点抽象出两个节点 v0,v1.

v0表示v染0这种颜色，v1表示v染1这种颜色。
对于这个新图，
图中的每一条边（iq,jw）(I,j为原本的点编号，q,w为0或1)，
表示i选q颜色的话，j一定要选w颜色。
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define N 1000
int fa[N<<1],n,m;
int find(int k){return fa[k]==k?k:fa[k]=find(fa[k]);}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n*2;i++)fa[i]=i;
    for(int fx,fy,x,y,i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        
        fx=find(x*2-1);
        fy=find(y*2);
        fa[fx]=fy;//一个染白则另一个染黑 
        
        fx=find(x*2);
        fy=find(y*2-1);
        fa[fx]=fy;//一个染黑则另一个染白 
    }
    for(int i=1;i<=n;i++)
        if(find(i*2)==find(i*2-1)){//既染白又染黑 
            printf("NO");
            return 0;
        }
    printf("YES");
    return 0;
}
View Code

粘一波概念：

匹配：给定一个二分图G=(X,Y,E)，若存在E的一个子集M，满足 M中的任意两条边都没有公共顶点，则M称为一个G的匹配

匹配边：在匹配中的边

未匹配边：不在匹配中的边

未匹配点：对于一个匹配，不与任何匹配边邻接的点

匹配点：刚好相反

极大匹配：无法再加边的匹配
最大匹配：在所有极大匹配中，边数|M|最大的匹配

完全匹配：如果一个匹配中，图中每个顶点都与一条边相关联 ，则称此匹配为完全匹配

下面给出关于二分图最大匹配的三个定理：

① 最大匹配数＋最大独立集数＝n

② 二分图的最小覆盖数＝最大匹配数

③ 最小路径覆盖＝最大独立集 最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。 最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。 最小路径覆盖是指一个不含圈的有向图 G 中，G 的一个路径覆盖是一个其结点不相交的路径集合 P，图中 的每一个结点仅包含于 P 中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，包括 0。

增广路

增广路径：若 P 是图 G 中一条连通两个未匹配顶点的路径，并且属于 M 的边和不属于 M 的边（即已匹配 和待匹配的边）在 P 上交替出现，则称 P 为相对于 M 的一条增广路径。

由增广路的定义可以推出下述三个结论：

① P 的路径长度必定为奇数，第一条边和最后一条边都不属于 M。

② P 经过取反操作可以得到一个更大的匹配 M'。

③ M 为 G 的最大匹配当且仅当不存在相对于 M 的增广路径。

方法（匈牙利算法）：

求二分图的最大匹配常用匈牙利算法，它是通过不断地寻找增广轨来实现的。很明显，如果二分图的两部 分点分别为 X 和 Y，那么最大匹配的数目应该小于等于 min{X,Y}。因此我们可以枚举某一部分里的每一个点， 从每个点出发寻找增广轨，最后，该部分的点找完以后，就找到了最大匹配的数目。当然我们也可以通过记录来找出这些边。

匈牙利算法找一条增广路的复杂度为 O(m)，最多找 n 条增广路，故时间复杂度为 O(mn)。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/song-/p/9149165.html