图的m着色问题

阳光穿透心脏的1/2处 2022-05-22 20:50 175阅读 0赞

**问题描述**

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

**四色猜想**：四色问题是m图着色问题的一个特例，根据四色原理，证明平面或球面上的任何地图的所有区域都至多可用四种、颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。这个问题可转换成对一平面图的４－着色判定问题(平面图是一个能画于平面上而边无任何交叉的图)。将地图的每个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。多年来，虽然已证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。直到1976年这个问题才由爱普尔，黑肯和考西利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。

![1365563218_1670.jpg][]

**算法设计**

**     **考虑所有的图，讨论在至多使用m种颜色的情况下，可对一给定的图着色的所有不同方法。通过回溯的方法，不断的为每一个节点着色，在前面n-1个节点都合法的着色之后，开始对第n个节点进行着色，这时候枚举可用的m个颜色，通过和第n个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。

用m种颜色为无向图G=(V,E)着色，其中，V的顶点个数为n，可以用一个n元组x=(x1,x2,…,xn)来描述图的一种可能着色，其中，xi∈\{1, 2, …, m\}，(1≤i≤n)表示赋予顶点i的颜色。例如，5元组(1, 2, 2, 3, 1)表示对具有5个顶点的无向图（a）的一种着色，顶点A着颜色1，顶点B着颜色2，顶点C着颜色2，如此等等。如果在n元组X中，所有相邻顶点都不会着相同颜色，就称此n元组为可行解，否则为无效解。容易看出，每个顶点可着颜色有m种选择，n个顶点就有mn种不同的着色方案，问题的解空间是一棵高度为n的完全m叉树，这里树高度的定义为从根节点到叶子节点的路径的长度。每个分支结点，都有m个儿子结点。最底层有mn个叶子结点。例如，表示用3种颜色为3个顶点的图着色的状态空间树。如图所示，对第i（i>=1）层上的每个顶点，从其父节点到该节点的边上的标号表示顶点i着色的颜色编号。

![1365563682_7404.jpg][]

\#include <iostream>  
\#include <cmath>  
\#include <cstdio>  
\#include <algorithm>  
  
  
using namespace std;  
  
  
const int N = 5;//图的顶点数  
const int M = 3;//色彩数  
class Color  
\{  
    friend int mColoring(int, int, int \*\*);  
private:  
    bool Ok(int k);  
    void Backtrack(int t);  
    int n,      //图的顶点数  
        m,      //可用的颜色数  
        \*\*a,    //图的邻接矩阵  
        \*x;     //当前解  
    long sum;   //当前已找到的可m着色方案数  
\};  
int mColoring(int n,int m,int \*\*a);  
int main()  
\{  
    int \*\*a = new int \*\[N+1\];  
    for(int i=1; i<=N; i++)  
    \{  
        a\[i\] = new int\[N+1\];  
    \}  
  
  
    cout<<"请输入图G的邻接矩阵:"<<endl;  
    for(int i=1; i<=N; i++)  
    \{  
        for(int j=1; j<=N; j++)  
        \{  
            cin>>a\[i\]\[j\];  
  
  
        \}  
        cout<<endl;  
    \}  
    cout<<"图G的着色方案如下："<<endl;  
    cout<<"当m="<<M<<"时，图G的可行着色方案数目为："<<mColoring(N,M,a)<<endl;  
    for(int i=1; i<=N; i++)  
    \{  
        delete\[\] a\[i\];  
    \}  
    delete \[\]a;  
\}  
  
  
void Color::Backtrack(int t)  
\{  
    if (t>n)  
    \{  
        sum++;  
        for (int i=1; i<=n; i++)  
            cout << x\[i\] << " ";  
        cout << endl;  
    \}  
    else  
    \{  
        for (int i=1; i<=m; i++)  
        \{  
            x\[t\]=i;  
            if (Ok(t)) Backtrack(t+1);  
            x\[t\]=0;  
        \}  
    \}  
\}  
  
  
bool Color::Ok(int k)// 检查颜色可用性  
\{  
    for (int j=1; j<=n; j++)  
    \{  
        if ((a\[k\]\[j\]==1)&&(x\[j\]==x\[k\])) //相邻且颜色相同  
        \{  
            return false;  
        \}  
    \}  
    return true;  
\}  
  
  
int mColoring(int n,int m,int \*\*a)  
\{  
    Color X;  
  
  
    //初始化X  
    X.n = n;  
    X.m = m;  
    X.a = a;  
    X.sum = 0;  
    int \*p = new int\[n+1\];  
    for(int i=0; i<=n; i++)  
    \{  
        p\[i\] = 0;  
    \}  
    X.x = p;  
    X.Backtrack(1);  
    delete \[\]p;  
    return X.sum;  
\}  
/\*  
0 1 1 1 0  
1 0 1 1 1  
1 1 0 1 0  
0 1 1 0 1  
0 1 0 1 0  
\*/

[1365563218_1670.jpg]: https://img-my.csdn.net/uploads/201304/10/1365563218_1670.jpg
[1365563682_7404.jpg]: https://img-my.csdn.net/uploads/201304/10/1365563682_7404.jpg