离散数学怎么判断二部图

在许多图论问题中，二部图是非常重要的一种类型。判断一个图是否为二部图是一个基本问题，在离散数学中也有着重要的地位。本文将从定义、特点以及判定方法等多个角度来分析二部图，希望能为读者带来帮助。

定义

二部图是指可以将图的顶点分为两个不相交的集合，使得任意一条边所连接的两个顶点分别属于这两个不相交的集合。通俗来说，就是把图的顶点分成 A 和 B 两组，使得图中的每一条边连接的两个顶点属于不同组，如下图所示。


特点

根据二部图的定义，可以得出它具有以下特点：

1. 二部图的所有环都是偶数长度的。

2. 二部图不包含奇数长度的回路。

3. 二部图的任意两个非自身相邻顶点是否同属一组是等价的。

判定方法

判断一个图是否为二部图有多种方法，下面列举几种常用的方法。

方法一：涂色法

涂色法是一种直观易懂的方法。具体操作如下：

1. 任选一个顶点，将其染成红色。

2. 将其所有相邻的顶点染成蓝色。

3. 将每个蓝色顶点相邻的红色顶点染成蓝色，每个蓝色顶点相邻的蓝色顶点染成红色。

4. 以此类推，直到所有的顶点都被染色为止。

5. 如果染色冲突（即一个顶点的相邻顶点染的颜色与它不同），则该图不是二部图。

由于涂色法的时间复杂度为 O(n^2)，所以对于大规模的图来说效率并不高。

方法二：DFS

在 DFS 的过程中，判断是否有相邻的节点已经被染色，如果已经被染色且与当前节点颜色相同，则说明该图不是二部图。该算法时间复杂度为 O(n+m)。下面是使用 DFS 算法判断二部图的示例代码。

```c++

const int N = 100010, M = 200010;

int h[N], e[M], ne[M], idx;

int color[N];

int n, m;

void add(int a, int b) {

e[idx] = b;

ne[idx] = h[a];

h[a] = idx ++;

}

bool dfs(int u, int c) {

color[u] = c;

for (int i = h[u]; ~i; i = ne[i]) {

int j = e[i];

if (!color[j]) {

if (!dfs(j, 3 - c)) return false;

} else if (color[j] == c) {

return false;

}

}

return true;

}

bool check() {

memset(color, 0, sizeof color);

for (int i = 1; i <= n; i ++ )

if (!color[i])

if (!dfs(i, 1)) return false;

return true;

}

```

方法三：BFS

BFS 的实现方法和 DFS 基本相同，只是使用一个队列而已，下面是使用 BFS 算法判断二部图的示例代码。

```c++

const int N = 100010, M = 200010;

int h[N], e[M], ne[M], idx;

int color[N];

int n, m;

void add(int a, int b) {

e[idx] = b;

ne[idx] = h[a];

h[a] = idx ++;

}

bool bfs(int u) {

queue q;

q.push(u);

color[u] = 1;

while (q.size()) {

int t = q.front();

q.pop();

for (int i = h[t]; ~i; i = ne[i]) {

int j = e[i];

if (!color[j]) {

color[j] = 3 - color[t];

q.push(j);

} else if (color[j] == color[t]) {

return false;

}

}

}

return true;

}

bool check() {

memset(color, 0, sizeof color);

for (int i = 1; i <= n; i ++ )

if (!color[i])

if (!bfs(i)) return false;

return true;

}

```