图着色问题¶

概述¶

图着色问题是为图的顶点（或边）分配颜色，使得相邻顶点（或边）颜色不同的组合优化问题。图着色在调度、寄存器分配等领域有广泛应用。

图着色类型¶

类型	定义	约束条件
顶点着色	为顶点分配颜色	相邻顶点颜色不同
边着色	为边分配颜色	相邻边颜色不同
面着色	为面分配颜色	相邻面颜色不同

色数¶

色数 χ(G)：图G顶点着色所需的最少颜色数。

色数性质¶

χ(G) ≥ ω(G)（ω为最大团大小）
χ(G) ≤ Δ(G) + 1（Δ为最大度数）
χ(G) ≤ n（n为顶点数）
完全图Kₙ：χ(Kₙ) = n
二分图：χ(G) = 2（非平凡二分图）

回溯法求图着色¶

基本实现¶

C
#define MAX_V 100

typedef struct {
    int adj[MAX_V][MAX_V];
    int vertexCount;
    int color[MAX_V];
    int chromaticNumber;
} GraphColoring;

void initGraphColoring(GraphColoring *gc, int n) {
    gc->vertexCount = n;
    gc->chromaticNumber = n;
    
    for (int i = 0; i < n; i++) {
        gc->color[i] = 0;
        for (int j = 0; j < n; j++) {
            gc->adj[i][j] = 0;
        }
    }
}

int isSafe(GraphColoring *gc, int v, int c) {
    for (int i = 0; i < gc->vertexCount; i++) {
        if (gc->adj[v][i] && gc->color[i] == c) {
            return 0;
        }
    }
    return 1;
}

int graphColoringUtil(GraphColoring *gc, int m, int v) {
    if (v == gc->vertexCount) {
        return 1;
    }
    
    for (int c = 1; c <= m; c++) {
        if (isSafe(gc, v, c)) {
            gc->color[v] = c;
            
            if (graphColoringUtil(gc, m, v + 1)) {
                return 1;
            }
            
            gc->color[v] = 0;
        }
    }
    
    return 0;
}

int graphColoring(GraphColoring *gc, int m) {
    for (int i = 0; i < gc->vertexCount; i++) {
        gc->color[i] = 0;
    }
    
    return graphColoringUtil(gc, m, 0);
}

int findChromaticNumber(GraphColoring *gc) {
    for (int m = 1; m <= gc->vertexCount; m++) {
        if (graphColoring(gc, m)) {
            gc->chromaticNumber = m;
            return m;
        }
    }
    return gc->vertexCount;
}

贪心着色算法¶

顺序着色¶

C
void greedyColoring(GraphColoring *gc) {
    gc->color[0] = 1;
    
    for (int v = 1; v < gc->vertexCount; v++) {
        int usedColors[MAX_V + 1] = {0};
        
        for (int i = 0; i < gc->vertexCount; i++) {
            if (gc->adj[v][i] && gc->color[i] != 0) {
                usedColors[gc->color[i]] = 1;
            }
        }
        
        int c = 1;
        while (usedColors[c]) {
            c++;
        }
        
        gc->color[v] = c;
    }
}

DSATUR算法（度饱和法）¶

C
typedef struct {
    int vertex;
    int degree;
    int saturation;
    int color;
} VertexInfo;

int getSaturation(GraphColoring *gc, int v) {
    int colors[MAX_V + 1] = {0};
    int count = 0;
    
    for (int i = 0; i < gc->vertexCount; i++) {
        if (gc->adj[v][i] && gc->color[i] != 0) {
            colors[gc->color[i]] = 1;
        }
    }
    
    for (int i = 1; i <= MAX_V; i++) {
        if (colors[i]) count++;
    }
    
    return count;
}

int selectVertexDSATUR(GraphColoring *gc) {
    int maxSat = -1;
    int maxDeg = -1;
    int selected = -1;
    
    for (int v = 0; v < gc->vertexCount; v++) {
        if (gc->color[v] == 0) {
            int sat = getSaturation(gc, v);
            int deg = 0;
            
            for (int i = 0; i < gc->vertexCount; i++) {
                if (gc->adj[v][i]) deg++;
            }
            
            if (sat > maxSat || (sat == maxSat && deg > maxDeg)) {
                maxSat = sat;
                maxDeg = deg;
                selected = v;
            }
        }
    }
    
    return selected;
}

void dsaturColoring(GraphColoring *gc) {
    for (int i = 0; i < gc->vertexCount; i++) {
        gc->color[i] = 0;
    }
    
    for (int i = 0; i < gc->vertexCount; i++) {
        int v = selectVertexDSATUR(gc);
        
        int usedColors[MAX_V + 1] = {0};
        for (int j = 0; j < gc->vertexCount; j++) {
            if (gc->adj[v][j] && gc->color[j] != 0) {
                usedColors[gc->color[j]] = 1;
            }
        }
        
        int c = 1;
        while (usedColors[c]) {
            c++;
        }
        
        gc->color[v] = c;
    }
}

Welsh-Powell算法¶

C
typedef struct {
    int vertex;
    int degree;
} VertexDegree;

int compareDegree(const void *a, const void *b) {
    return ((VertexDegree*)b)->degree - ((VertexDegree*)a)->degree;
}

void welshPowellColoring(GraphColoring *gc) {
    VertexDegree vd[MAX_V];
    
    for (int i = 0; i < gc->vertexCount; i++) {
        vd[i].vertex = i;
        vd[i].degree = 0;
        gc->color[i] = 0;
        
        for (int j = 0; j < gc->vertexCount; j++) {
            if (gc->adj[i][j]) {
                vd[i].degree++;
            }
        }
    }
    
    qsort(vd, gc->vertexCount, sizeof(VertexDegree), compareDegree);
    
    int currentColor = 1;
    
    for (int i = 0; i < gc->vertexCount; i++) {
        int v = vd[i].vertex;
        
        if (gc->color[v] == 0) {
            gc->color[v] = currentColor;
            
            for (int j = i + 1; j < gc->vertexCount; j++) {
                int u = vd[j].vertex;
                
                if (gc->color[u] == 0) {
                    int canUse = 1;
                    
                    for (int k = 0; k < gc->vertexCount; k++) {
                        if (gc->adj[u][k] && gc->color[k] == currentColor) {
                            canUse = 0;
                            break;
                        }
                    }
                    
                    if (canUse) {
                        gc->color[u] = currentColor;
                    }
                }
            }
            
            currentColor++;
        }
    }
}

边着色¶

Vizing定理¶

对于简单图G：Δ(G) ≤ χ'(G) ≤ Δ(G) + 1

其中χ'(G)是边色数，Δ(G)是最大度数。

边着色实现¶

C
typedef struct {
    int adj[MAX_V][MAX_V];
    int edgeColor[MAX_V][MAX_V];
    int vertexCount;
} EdgeColoring;

void initEdgeColoring(EdgeColoring *ec, int n) {
    ec->vertexCount = n;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ec->adj[i][j] = 0;
            ec->edgeColor[i][j] = 0;
        }
    }
}

int getEdgeColorUsed(EdgeColoring *ec, int v, int c) {
    for (int i = 0; i < ec->vertexCount; i++) {
        if (ec->adj[v][i] && ec->edgeColor[v][i] == c) {
            return 1;
        }
    }
    return 0;
}

void edgeColoring(EdgeColoring *ec) {
    int maxDegree = 0;
    
    for (int i = 0; i < ec->vertexCount; i++) {
        int deg = 0;
        for (int j = 0; j < ec->vertexCount; j++) {
            if (ec->adj[i][j]) deg++;
        }
        if (deg > maxDegree) maxDegree = deg;
    }
    
    int numColors = maxDegree + 1;
    
    for (int i = 0; i < ec->vertexCount; i++) {
        for (int j = i + 1; j < ec->vertexCount; j++) {
            if (ec->adj[i][j]) {
                for (int c = 1; c <= numColors; c++) {
                    if (!getEdgeColorUsed(ec, i, c) && !getEdgeColorUsed(ec, j, c)) {
                        ec->edgeColor[i][j] = ec->edgeColor[j][i] = c;
                        break;
                    }
                }
            }
        }
    }
}

C++ 实现¶

C++
class GraphColoring {
private:
    vector<vector<int>> adj;
    int n;
    vector<int> color;
    
    bool isSafe(int v, int c) {
        for (int u = 0; u < n; u++) {
            if (adj[v][u] && color[u] == c) {
                return false;
            }
        }
        return true;
    }
    
    bool solve(int m, int v) {
        if (v == n) return true;
        
        for (int c = 1; c <= m; c++) {
            if (isSafe(v, c)) {
                color[v] = c;
                if (solve(m, v + 1)) return true;
                color[v] = 0;
            }
        }
        
        return false;
    }
    
public:
    GraphColoring(int n) : n(n), adj(n, vector<int>(n, 0)), color(n, 0) {}
    
    void addEdge(int u, int v) {
        adj[u][v] = adj[v][u] = 1;
    }
    
    vector<int> greedyColoring() {
        color.assign(n, 0);
        color[0] = 1;
        
        for (int v = 1; v < n; v++) {
            set<int> usedColors;
            for (int u = 0; u < n; u++) {
                if (adj[v][u] && color[u] > 0) {
                    usedColors.insert(color[u]);
                }
            }
            
            int c = 1;
            while (usedColors.count(c)) c++;
            color[v] = c;
        }
        
        return color;
    }
    
    int findChromaticNumber() {
        for (int m = 1; m <= n; m++) {
            color.assign(n, 0);
            if (solve(m, 0)) {
                return m;
            }
        }
        return n;
    }
    
    vector<int> getColoring() const { return color; }
};

时间复杂度分析¶

算法	时间复杂度	空间复杂度	着色质量
回溯法	O(mⁿ)	O(n)	最优
顺序贪心	O(n²)	O(n)	≤ Δ + 1
Welsh-Powell	O(n²)	O(n)	≤ Δ + 1
DSATUR	O(n²)	O(n)	通常较好

色数上下界¶

上界¶

简单上界：χ(G) ≤ n
Brooks定理：χ(G) ≤ Δ(G)，除非G是完全图或奇环
贪心上界：χ(G) ≤ Δ(G) + 1

下界¶

团下界：χ(G) ≥ ω(G)
独立集下界：χ(G) ≥ n / α(G)

应用场景¶

寄存器分配：编译器优化
调度问题：课程安排、考试安排
频率分配：无线信道分配
地图着色：四色定理应用
数独问题：转化为图着色

寄存器分配示例¶

C
void registerAllocation(int interferenceGraph[MAX_V][MAX_V], int numVars, int numRegs) {
    GraphColoring gc;
    initGraphColoring(&gc, numVars);
    
    for (int i = 0; i < numVars; i++) {
        for (int j = 0; j < numVars; j++) {
            gc.adj[i][j] = interferenceGraph[i][j];
        }
    }
    
    if (graphColoring(&gc, numRegs)) {
        printf("Register allocation successful:\n");
        for (int i = 0; i < numVars; i++) {
            printf("Variable %d -> Register %d\n", i, gc.color[i]);
        }
    } else {
        printf("Spilling required: need %d registers\n", 
               findChromaticNumber(&gc));
    }
}

四色定理¶

四色定理：任何平面图可以用四种颜色着色，使得相邻区域颜色不同。

C
int isPlanar(GraphColoring *gc) {
    return 1;
}

void fourColorTheorem(GraphColoring *gc) {
    if (isPlanar(gc)) {
        graphColoring(gc, 4);
        printf("Planar graph can be colored with at most 4 colors\n");
    }
}

参考资料¶

《算法导论》
Graph Coloring - Wikipedia
四色定理
《图论及其应用》- J.A. Bondy