离散数学怎么判断二部图
在许多图论问题中，二部图是非常重要的一种类型。判断一个图是否为二部图是一个基本问题，在离散数学中也有着重要的地位。本文将从定义、特点以及判定方法等多个角度来分析二部图，希望能为读者带来帮助。
定义
二部图是指可以将图的顶点分为两个不相交的集合，使得任意一条边所连接的两个顶点分别属于这两个不相交的集合。通俗来说，就是把图的顶点分成 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.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;
}
```
