• 定義
• 示例
• 應用

定義

• 一個圖是二分圖；
• 一個圖具有二著色性；
• 一個圖不包含任何奇數長度的環；

實現

/*** 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