回溯算法 --- 例题7.图的m着色问题

一.问题描述

给定无向连通图G和m种不同的颜色.用这些颜色为图G的各项点着色,每个项点画一种颜色.是否有一种着色法,使G中每条边的2个顶点有着不同颜色?

二.解题思路

图的m色判定问题:
给定无向连通图G和m种颜色。用这些颜色为图G的各顶点着色. 问是否存在着色方法, 使得G中任2邻接点有不同颜色。

图的m色优化问题:
给定无向连通图G,为图G的各顶点着色, 使图中任2邻接点着不同颜色,问最少需要几种颜色。所需的最少颜色的数目m称为该图的色数

若图G是可平面图,则它的色数不超过4色(4色定理).
4色定理的应用:在一个平面或球面上的任何地图能够只用4种颜色来着色使得相邻的国家在地图上着有不同颜色

例如:

[这里有一个适用于任意图着色的Welch Powell法,感兴趣的同学可以看看.](#Welch Powell)

回到该问题,我们可以很清晰地看出问题的解空间树是一棵排列树,因为我们确定n个元素满足某种性质的排列,这个性质就是一条边的两个点颜色不相同.而不是说找到n个元素的一个子集,这是要做的第一步.

具体的算法实现上:
设图G=(V, E), |V|=n, 颜色数= m, 用邻接矩阵a表示G, 用整数1, 2…m来表示m种不同的颜色。顶点i所着的颜色用x[i]表示。

问题的解向量可以表示为n元组x={ x[1],...,x[n] }. x[i]?{1,2,...,m},解空间树为排序树,是一棵n+1层的完全m叉树.在解空间树中做深度优先搜索, 约束条件: x[i] ≠ x[j], 如果a[j].[i] = 1.

代码如下:

// 图的m着色问题
#include
using namespace std;
class Color
{
    friend int mColoring(int, int, int **);
    private:
        bool CanDraw(int k);
        void Backtrack(int i);
        int n,          //图的顶点数
            m,          //可用颜色数
            **a,        //图的邻接矩阵
            *x;         //当前解
        long sum;       //当前已经找到的可m着色方案数
};
bool Color::CanDraw(int i)      //检查第i层填写的颜色x[i]是否可用
{
    for(int j=1; j n)
    {
        sum++;
        cout<<"第"<>n>>m && n && m)
    {
        cout<<"请输入邻接矩阵"<>a[i][j];
        int ans = mColoring(n, m, a);
        cout<<"图的"<