MENU

二分图是什么

April 6, 2019 • 未分类

二分图

  • 首先，二分图到底是个什么东西，简单的来说，有一个点的集合，而同时这个点集又被划分成两个子集，同一个子集之间的点不相连，而不同子集之间的点可以相连。这样这两个子集组成的图就交二分图。
  • 稍微专业一点就是： 二分图也称二部图，是图论里的一种特殊模型，也是一种特殊的网络流。其最大的特点在于，可以将图里的顶点分为两个集合，且集合内的点没有直接关联二分图模型如下图所示：

判断一个图是否为二分图

  1. 至少欧两个顶点
  2. 如果产生回路，那么一个回路中的边数一定为偶数。
  3. 没有回路的图一也叫二分图。

如上图这个，就不是一个二分图，因为有一些回路，如1->5->2的边数为奇数。这时候如果去掉1、2两个点之间的连接，它就变成了一个二分图。

或者还可以这样判定:(这种方法判定的结果不一定正确，下面会讲)

  • 首先这几个点被分成x，y两个集合，其中1、2、3为一个集合，4、5、6为另一个集合。

    • 1、2、3之间一定不能相连，4、5、6之间一定不能相连。
    • 1、2、3可以和4、5、6随意链接。

一个很可能出错的地方

如果用我上面讲的第二个判断二分图的方法，那么有时候就会出现这样一个问题。我先提前告诉大家，下图中的图是一个二分图但是如果用第二种方法判断的话，将会得到结论这明显不是一个二分图大家可以思考一下这是为什么

其实我们一开始就被这个图误导了，不管这个图的颜色和两个集合，将2和5调换一个位置，成如下的图，这样就可以看出来这是一个二向图。

## 判定方法

  • 我们一般用染色法来判定一个图是否是二分图。### 染色法
  • 用两种颜色，对所有顶点逐个染色，且相连的两个顶点染不同的颜色，如果过程中发现发现相邻顶点染了同一种颜色，就认为此图不为二分图。 当所有顶点都被染色，且没有发现同色的相邻顶点，就退出。
  • 如果要实现染色法，我们最好使用一个深搜（深度优先搜索），思路如下：先将所有点的连接情况接受近一个（二维/动态）数组中，然后对数组进行dfs遍历，这样就可以避免掉上文所处出现的问题。
  • 下面有道例题，可以参考一下：
题目大意二部图又叫二分图证明二部图可以用着色来解决即我们可以用两种颜色去涂一个图使的任意相连的两个顶点颜色不相同切任意两个结点之间最多一条边。为了简化问题我们每次都从0节点开始涂色
输入数据多组数据
第一行一个整数 n(n<=200) 表示 n个节点
第二行一个整数m 表示m条边
随后 m行 两个整数 u , v 表示 一条边
数据输出如果是二部图输出 BICOLORABLE.否则输出 NOT BICOLORABLE.
样例输入3
3
0 1
1 2
2 0
样例输出NOT BICOLORABLE.
样例输入3
2
0 1
0 2
样例输出BICOLORABLE.

示例代码：

二维数组式


#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
const int N = 505;
int m,n;
int color[N];
int edge[N][N];
 
bool dfs(int v, int c){
    color[v] = c;    //将当前顶点涂色
    for(int i = 0; i < n; i++){    //遍历所有相邻顶点，即连着的点
        if(edge[v][i] == 1){    //如果顶点存在
            if(color[i] == c)    //如果颜色重复，就返回false
                return false;
            if(color[i] == 0 && !dfs(i,-c))    //如果还未涂色，就染上相反的颜色-c,并dfs这个顶点，进入下一层
                return false;   //返回false
        }
    }
    return true;   //如果所有顶点涂完色，并且没有出现同色的相邻顶点，就返回true
}
 
void solve(){
    for(int i = 0; i < n; i++){
        if(color[i] == 0){
            if(!dfs(i, 1)){
                printf("NOT BICOLORABLE.\n");
                return;
            }
        }
    }
    printf("BICOLORABLE.\n");
}
 
int main(){
    int u,v;
    while(cin >> n >> m){
        memset(color, 0, sizeof(color));
        memset(edge, 0, sizeof(edge));
        for(int i = 0; i < m; i++){
            cin >> u >> v;    //因为是无向图，所以要往两个方向添加边
            edge[u][v] = 1;    //正着添加
            edge[v][u] = 1;    //反着添加
        }
        solve();
    }
    return 0;
}

动态数组式

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
const int N = 505;
int m,n;
int color[N];
vector<int> node[N];
 
bool dfs(int v, int c){
    color[v] = c;   //为当前顶点上色
    for(int i = 0; i < node[v].size(); i++){    //遍历所有与之连接的顶点，即相邻顶点
       if(color[node[v][i]] == c)   //如果相邻的顶点同色，就返回false
           return false;
        if(color[node[v][i]] == 0 && !dfs(node[v][i], -c))  //如果相邻顶点未染色，就将其染为相反颜色即-c，并继续dfs
           return false;    //返回false
    }
    return true;   //直到所有顶点都被染色，且没出现相邻同色顶点，就返回true
}
 
void solve(){
    for(int i = 0; i < n; i++){     //遍历所有顶点
        if(color[i] == 0){  //如果未染色，就进入深搜
            if(!dfs(i, 1)){
                printf("NOT BICOLORABLE.\n");   //如果返回false值，就不是二分图
                return; //结束搜索
            }
        }
    }
    printf("BICOLORABLE.\n");   //未出现相邻同色，就是二分图
}
 
int main(){
    int u,v;
    while(~scanf("%d %d",&n,&m)){
        memset(node, 0, sizeof(node));
        memset(color, 0, sizeof(color));
        for(int i = 0; i < m; i++){
            cin >> u >> v;  //因为是无向图，所以要双向插入顶点
            node[u].push_back(v);   //在u点后插入v顶点
            node[v].push_back(u);   //在v点后插入u顶点
        }
        solve();
    }
    return 0;
}
Last Modified: September 8, 2021
Leave a Comment