• 定义
• 示例
• 应用

定义

• 一个图是二分图；
• 一个图具有二着色性；
• 一个图不包含任何奇数长度的环；

实现

/*** Program 18.6 Two-colorability* ---------------------------------------------------------------------------------------------------------------------* This DFS function assigns the values 0 or 1 to the vertex-indexed array `G->color` and* indicates in the return value whether or not it was able to do the assignment such that,* for each graph edge `v-w`, `G->color[v]` and `G->color[w]` are different.* ---------------------------------------------------------------------------------------------------------------------* Two-colorability, bipartiteness, odd cycle* - Is there a way to assign one of two colors to each vertex of a graph such that*   no edge connects two vertices of the same color?* - Is a given graph bipartite (see Section 17.1)?* - Does a given graph have a cycle of odd length?*/
int dfsRcolor(Graph G, int v, int c) {int t;G->color[v] = 1-c;for (t = 0; t < G->V; t++) {if (G->adj[v][t] != 0) {if (G->color[t] == -1) {//tree link: t是v的孩子节点if (!dfsRcolor(G, t, 1-c)) {return 0;}}else if (G->color[t] == c) {//parent link: t是v的父节点}else if (G->color[t] != c) {//back edge: t是v的祖先，且t不是v的父节点return 0;}}}return 1;
}int GRAPHtwocolor(Graph G) {int v;G->color = malloc(G->V * sizeof(int));for (v = 0; v < G->V; v++) {G->color[v] = -1;}for (v = 0; v < G->V; v++) {if (G->color[v] == -1) {if (!dfsRcolor(G, v, 0)) {return 0;}}}return 1;
}

示例

示例1 判定下图是否为二分图？请画出对应的DFS递归树增强版。

TestTwoColorabilityForAdjacenyMatrix

示例2 判定下图是否为二分图？请画出对应的DFS递归树增强版。

TestTwoColorabilityForAdjacenyMatrix