图的m着色问题

算法分析与设计实验报告第六次附加实验cout<<endl;}elsefor(int i=1;i<=m;i++){x[t]=i;if(ok(t)) Backtrack(t+1);//回溯，继续寻找下一层x[t]=0;//回到最初状态，使x[1]继续尝试其他填色的可能解}}测试结果当输入图如下时：结果如下：12435只要输入边即可当输入的图如下时：结果如下：附录：完整代码（回溯法）//图的m着色问题回溯法求解#include<iostream>using namespace std;class Color{friend void mColoring(int,int,int **);private:bool ok(int k);void Backtrack(int t);int n, //图的顶点个数m, //可用颜色数**a, //图的邻接矩阵*x; //当前解long sum; //当前已找到的可m着色的方案数};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;}void Color::Backtrack(int t){if(t>n) //到达叶子节点{sum++; //可行解+1cout<<"着色： ";for(int i=1;i<=n;i++) //输出可行解方案cout<<x[i]<<" ";cout<<endl;}elsefor(int i=1;i<=m;i++){x[t]=i;if(ok(t)) Backtrack(t+1);//回溯，继续寻找下一层x[t]=0;//回到最初状态，使x[1]继续尝试其他填色的可能解 }}void mColoring(int n,int m,int **a){Color X;//初始化XX.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;cout<<"顶点： ";for(int i=1;i<=n;i++) //用于输出结果cout<<i<<" " ;cout<<endl;X.Backtrack(1); //从顶点1开始回溯delete []p;cout<<"解法个数："<<X.sum<<endl;}int main(){int n;int m;cout<<"please input number of node:";cin>>n;cout<<"please input number of color:";cin>>m;int **a=new int*[n+1];for(int i=0;i<=n;i++)a[i]=new int[n+1];for(int i=0;i<=n;i++) //利用抽象图实现图的邻接矩阵for(int j=0;j<=n;j++)a[i][j]=0;int edge;cout<<"please input adjacent edge number:";cin>>edge;int v,w;cout<<"please inout adjacent edge:"<<endl; //只要输入边即可for(int i=0;i<edge;i++){cin>>v>>w; //由于是无向图，所以对应的邻接矩阵对应的边都有，即v->m,m->v都有边a[v][w]=1;a[w][v]=1;}mColoring(n,m,a);system("pause");return 0;}。

图的着色问题一、题目简述(1) 图的m-着色判定问题给定一个无向连通图 G 和 m 种不同的颜色。

用这些颜色为图 G 的各顶点着色，每个顶点着一种颜色，是否有一种着色法使 G 中任意相邻的两个顶点着不同颜色？(2) 图的m-着色优化问题若一个图最少需要 m 种颜色才能使图中任意相邻的两个顶点着不同颜色，则称这个数 m 为该图的色数。

求一个图的最小色数 m 的问题称为m-着色优化问题。

二、算法思想1. m-着色判定问题总体思想：通过回溯的方法，不断为每一个节点着色，每个点的颜色由一个数字代表，初始值为1。

在对前面 step - 1 个节点都合法的着色之后，开始对第 step 个节点进行着色。

如果 n 个点均合法，且颜色数没有达到 m 种，则代表存在一种着色法使 G中任意相邻的两个顶点着不同颜色。

具体步骤：1. 对每个点 step ，有 m 种着色可能性，初始颜色值为1。

2. 检查第 step 个节点颜色的可行性，若与某个已着色的点相连且颜色相同，则不选择这种着色方案，并让颜色值加1，继续检查该点下一种颜色的可行性。

3. 如果第 step 点颜色值小于等于 m ，且未到达最后一个点，则进行对第 step + 1 点的判断。

4. 如果第 step 点颜色值大于 m ，代表该点找不到合适的分配方法。

此时算法进行回溯，首先令第 step 节点的颜色值为0，并对第 step - 1 个点的颜色值+1后重新判断。

5. 如果找到一种颜色使得第 step 个节点能够着色，说明 m 种颜色的方案是可行的。

6. 重复步骤2至5，如果最终 step 为0则代表无解。

2. m-着色优化问题基于问题1，对于一个无向图 G ，从1开始枚举染色数，上限为顶点数，第一个满足条件的颜色数即为所求解。

三、实现过程（附代码）1. m-着色判定问题#include<iostream>using namespace std;int color[100]; // 每个点的颜色int mp[100][100]; // 图的邻接矩阵int n, m, x; // n顶点，m种颜色方案，x条边bool check(int step) {// 判断与step点相邻的点，颜色是否与step点相同，若相同则返回falsefor (int i=1; i<=n; i++) {if (mp[step][i] ==1&&color[i] ==color[step]) {return false;}}return true;}bool Solve(int m) {// 求解是否可以找到一种可行的染色方案int step=1; // step指示当前节点while (step>=1) {color[step] +=1; // 假定颜色值从1开始，若为回溯，选择下一种方案while (color[step] <=m) { // 按照问题条件选择第step点颜色if (check(step)) {break;} else {color[step]++; // 搜索下一个颜色}}if (color[step] <=m&&step==n) { // 如果找完n个点，且染色方法小于等于m种 return true;} else if (color[step] <=m&&step<n) {step++; // 求解下一个顶点} else { // 如果染色数大于m个，回溯color[step] =0; // 回溯，该点找不到合适的分配方法，对上一点进行分析step--;}}// 如果step退到0，则代表无解return false;}int main() {int i, j;bool ans=false;cout<<"输入顶点数n和着色数m"<<endl;cin>>n>>m;cout<<"输入边数"<<endl;cin>>x;cout<<"具体输入每条边"<<endl;for (int p=0; p<x; p++) { // 以无向邻接矩阵存储边cin>>i>>j;mp[i][j] =1;mp[j][i] =1;}if (Solve(m)) {cout<<"有解";} else {cout<<"无解";}return0;}2. m-着色优化问题#include<iostream>using namespace std;int color[100]; // 每个点的颜色int mp[100][100]; // 图的邻接矩阵int n, m, x; // n顶点，m种颜色方案，x条边bool check(int step) {// 判断与step点相邻的点，颜色是否与step点相同，若相同则返回falsefor (int i=1; i<=n; i++) {if (mp[step][i] ==1&&color[i] ==color[step]) {return false;}}return true;}bool Solve(int m) {// 求解是否可以找到一种可行的染色方案int step=1; // step指示当前节点while (step>=1) {color[step] +=1; // 假定颜色值从1开始，若为回溯，选择下一种方案while (color[step] <=m) { // 按照问题条件选择第step点颜色if (check(step)) {break;} else {color[step]++; // 搜索下一个颜色}}if (color[step] <=m&&step==n) { // 如果找完n个点，且染色方法小于等于m种 return true;} else if (color[step] <=m&&step<n) {step++; // 求解下一个顶点} else { // 如果染色数大于m个，回溯color[step] =0; // 回溯，该点找不到合适的分配方法，对上一点进行分析step--;}}// 如果step退到0，则代表无解return false;}int main() {int i, j;bool ans=false;cout<<"输入顶点数n"<<endl;cin>>n;cout<<"输入边数"<<endl;cin>>x;cout<<"具体输入每条边"<<endl;for (int p=0; p<x; p++) { // 以无向图邻接矩阵存储边 cin>>i>>j;mp[i][j] =1;mp[j][i] =1;}for (m=1; m<=n; m++) { // 从小到大枚举着色数mif (Solve(m)) { // 如果有解，输出答案并跳出循环cout<<"最小色数m为 "<<m;break;}}return0;}四、结果及分析问题1测试用例：问题2测试用例：经检验，最少着色数的范围为2-4，意味着使 G 中任意相邻的两个顶点着不同颜色最多需要4种颜色。

《算法设计与分析》课程实验报告实验序号：10实验项目名称：实验十一回溯法（二）一、实验题目1.图的着色问题问题描述：给定无向连通图G和m种不同的颜色。

用这些颜色为图G的各顶点着色，每个顶点着一种颜色。

如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。

图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

2.旅行商问题问题描述：给出一个n个顶点的带权无向图，请寻找一条从顶点1出发，遍历其余顶点一次且仅一次、最后回到顶点1的最小成本的回路——即最短Hamilton回路。

3.拔河比赛问题描述：某公司的野餐会上将举行一次拔河比赛。

他们想把参与者们尽可能分为实力相当的两支队伍。

每个人都必须在其中一只队伍里，两队的人数差距不能超过一人，且两队的队员总体重应该尽量接近。

4.批处理作业调度问题描述：给定n个作业的集合J=(J1,J2, .. Jn)。

每个作业J都有两项任务分别在两台机器上完成。

每个作业必须先由机器1处理，再由机器2处理。

作业i需要机器j的处理时间为tji(i=1,2, ..n; j=1,2)。

对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间，则所有作业在机器2上完成处理的时间和，称为该作业调度的完成时间和。

批处理作业调度问题要求，对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

二、实验目的（1）通过练习，理解回溯法求解问题的解状态空间树与程序表达的对应关系，熟练掌握排列树、子集树的代码实现。

（2）通过练习，体会减少搜索解空间中节点的方法，体会解的状态空间树的组织及上界函数的选取对搜索的影响。

（3）通过练习，深入理解具体问题中提高回溯算法效率的方法。

（4）（选做题）：在掌握回溯法的基本框架后，重点体会具体问题中解的状态空间搜索时的剪枝问题。

三、实验要求（1）每题都必须实现算法、设计测试数据、记录实验结果，并给出时间复杂度分析。

四、实验过程（算法设计思想、源码）1.图的着色问题(1)算法设计思想用邻接矩阵a[i][j]存储无向图，对于每一个顶点有m种颜色可以涂。

回溯算法---例题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<bits/stdc++.h>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<i; j++){if(a[i][j]==1 && x[j]==x[i])return false;}return true;}void Color::Backtrack(int i){if(i > n){sum++;cout<<"第"<<sum<<"个解:";for(int i=1; i<=n; i++)cout<<x[i]<<" ";cout<<endl;return;}for(int k=1; k<=m; k++) //依次从m种颜⾊中选择,由于每⼀个分⽀的处理⽅法⼀样,所以直接⽤⼀个循环,⽽不需要分别写{x[i] = k;if(CanDraw(i)){cout<<"颜⾊"<<k<<"可⾏,深⼊⼀层,将到达"<<i+1<<"层"<<endl;Backtrack(i+1);cout<<"回溯⼀层到达第"<<i<<"层"<<endl;}else{if(k==m) cout<<"当前层所有颜⾊选完,没有可⾏颜⾊,故将回溯⼀层到达第"<<i-1<<"层"<<endl;else cout<<"颜⾊"<<k<<"不可⾏,继续选择颜⾊"<<k+1<<endl;}x[i] = 0;}}int mColoring(int n, int m, int **a){Color X;// 初始化XX.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;}int main(){cout<<"请输⼊顶点个数和颜⾊种数:";int n, m;while(cin>>n>>m && n && m){cout<<"请输⼊邻接矩阵"<<endl;int **a = new int*[n+1];for(int i=0; i<=n; i++) a[i] = new int[n+1];for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)cin>>a[i][j];int ans = mColoring(n, m, a);cout<<"图的"<<m<<"着⾊⽅案共有"<<ans<<"种"<<endl;for(int i=0; i<=n; i++) delete[] a[i];delete[] a;cout<<"请输⼊顶点个数和颜⾊种数:";}system("pause");return 0;}运⾏结果:由此可以结合排列树看⼀看,⼗分清晰明了.参考毕⽅明⽼师《算法设计与分析》课件.欢迎⼤家访问个⼈博客⽹站---,和我⼀起加油吧!针对任意图着⾊问题,Welch Powell⽅法:将G的结点按照度数递减的次序排列⽤第⼀种颜⾊对第⼀个结点着⾊,并按照结点排列的次序对与前⾯着⾊点不邻接的每⼀点着以相同颜⾊⽤第⼆种颜⾊对尚未着⾊的点重复步骤2,⽤第三种颜⾊继续这种作法,直到所有点着⾊完为⽌例如:。

图着⾊问题⼀、图着⾊问题（1）图的m可着⾊判定问题给定⽆向连通图G和m种不同的颜⾊。

⽤这些颜⾊为图G的各顶点着⾊，每个顶点着⼀种颜⾊。

是否有⼀种着⾊法使G中每条边的2个顶点着不同颜⾊。

（2）图的m可着⾊优化问题若⼀个图最少需要m种颜⾊才能使图中每条边连接的2个顶点着不同颜⾊，则称这个数m为该图的⾊数。

⼆、m可着⾊判定问题的解法【算法】（1）通过回溯的⽅法，不断的为每⼀个节点着⾊，在前⾯cur-1个节点都合法的着⾊之后，开始对第cur-1个节点进⾏着⾊，（2）这时候枚举可⽤的m个颜⾊，通过和第cur-1个节点相邻的节点的颜⾊，来判断这个颜⾊是否合法（3）如果找到那么⼀种颜⾊使得第cur-1个节点能够着⾊，那么说明m种颜⾊的⽅案在当前是可⾏的。

（4）cur每次迭代加1，如果cur增加到N并通过了检测，说明m种颜⾊是可满⾜的。

（5）注意，这⾥只是要求判断m种颜⾊是否可满⾜，所以找到任何⼀种⽅案就可以了。

【代码实现】#include<iostream>#include<cstring>using namespace std;const int maxn = 105;int G[maxn][maxn];int color[maxn];bool ans;int n,m,k;void init(){ans = 0;memset(G, 0 , sizeof G);memset(color, 0 , sizeof color);}void dfs(int cur){if(cur > n) {ans = 1;return;}for(int i=1; i<=m; i++){ //对cur结点尝试使⽤每⼀种颜⾊进⾏涂⾊bool flag = 1;//cur之前的结点必被涂⾊for(int j=1; j<cur; j++){if(G[j][cur] == 1 && color[j] == i){flag = 0;//只要有⼀个冲突都不⾏break;}}//如果可以涂上i颜⾊，则考虑下⼀个结点的情况if(flag){color[cur] = i;dfs(cur + 1);}//如果到这⼀步第cur个结点⽆法着⾊，则返回探寻其他⽅案else color[cur] = 0;//回溯 ;}}int main(){while(cin>>n>>k>>m){init();for(int i=1; i<=k; i++){int x,y;cin>>x>>y;G[x][y] = G[y][x] = 1;}dfs(1);cout<<ans<<endl;}return0;}三、m可着⾊拓展【问题】在上述基础上，求出m种颜⾊能够给图G涂⾊的总总⽅案数量【算法】由于这个时候要求总⽅案数量，所以在找到⼀种可⾏⽅案后，总是进⾏回溯再搜索其他的解决⽅案，与上⾯不同，上⾯是只需要找出⼀种⽅案即可，所以如果找到了就不需要再回溯了，所以在这⾥只需要把回溯语句的位置写到dfs语句的后⾯即可。

实验二用回溯法求解图的m着色问题一、实验目的12、使用回溯法编程求解图的m着色问题。

二、实验原理回溯法是一个既带有系统性又带有跳跃性的的搜索算法。

回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树搜索。

否则，进入该子树，继续按深度优先的策略进行搜索。

回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可结束。

回溯法从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。

这个开始结点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点就成为一个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。

此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

三、问题描述给定一个无向连通图G和m种不同的颜色。

用这些颜色为图G的各顶点着色，每个顶点着一种颜色。

若一个图最少需要m种颜色才能使图中任何一条边连接的2个顶点着有不同的颜色，则称这个数m为该图的色数。

求一个图的色数m的问题称为图的m可着色优化问题。

设计一个算法，找出用m种颜色对一个图进行着色的不同方案。

四、算法设计与分析用邻接矩阵a来表示一个无向连通图G=(V,E)。

用整数1,2,…,m来表示m 种不同的颜色。

x[i]表示顶点i所着的颜色来，则问题的解向量可以表示为n元组x[1:n]。

问题的解空间可表示一棵高度为n+1的完全m叉树。

解空间树的第i层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一，第n+1层结点均为叶结点。

图着色问题论述在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

贪心法它适用于解一些组合数较大的问题。

根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。

换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。

【关键词】图着色回溯法贪心法1 图着色问题的分类1.1 回溯法回溯法是一种系统地搜索问题解的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。

否则，进入该子树，继续按深度优先的策略进行搜索。

用回溯法解题的一般步骤：（1）描述解的形式，定义一个解空间，它包含问题的所有解。

（2）构造状态空间树。

（3）构造约束函数（用于杀死节点）。

1.2 贪心算法贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对一些问题它能产生整体最优解或者是整体最优解的近似解。

贪心算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。

一定要注意，选择的贪婪策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略影响，也就是说某个状态以后的过程不会影响以前的状态，只与当前状态有关，也称为这种特性为无后效性。

因此，适应用贪婪策略解决的问题类型较少，对所采用的贪婪策略一定要仔细分析其是否满足无后效性。

图的着色问题是由地图的着色问题引申而来的：用m 种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。

图的m着⾊问题问题给定⽆向连通图G和m种颜⾊，⽤这些颜⾊给图的顶点着⾊，每个顶点⼀种颜⾊。

如果要求G的每条边的两个顶点着不同颜⾊。

给出所有可能的着⾊⽅案；如果不存在，则回答“NO”。

解析利⽤回溯法。

涂的时候从颜⾊1开始到m，每当涂上⼀个⾊，要判断第c个点是否可以涂这个⾊，不可以的话就不再往下涂了，改试另⼀个颜⾊，可以的话就继续。

当c>n的时候即前n个点都涂完了，然后输出结果并cout++计数。

设计if(c>n){//如果涂的数⽬⼤于n，则表⽰已经成功涂完输出color数组;return;}for(int i=1;i<=m;i++){color[c]=i;if(点c可以涂){draw(c+1);}color[c]=0;//回溯}分析有n个点，最坏情况下，每个点需要检查每⼀个⼦节点，复杂度为O(mn)，所以总的时间复杂度为O(nm^n)。

源码/*author: kekeproject name:图的m着⾊问题Time Complexity: O(nm^n)*/#include <bits/stdc++.h>using namespace std;#define ll long long#define db doubleconst int maxn = 1010;int n, m, f, t, sum, color[maxn];bool p[maxn][maxn];bool jud(int x) {for (int i = 1; i <= n; i++) {if (p[x][i] && color[x] == color[i]) return false;}return true;}void draw(int x) {if (x > n) {//如果涂⾊数⽬⼤于n，则表⽰已经完成全部涂⾊for (int i = 1; i <= n; i++) cout << color[i] << (i == n ? "\n" : "");++sum;return;}for (int i = 1; i <= m; i++) {color[x] = i;if (jud(x)) draw(x + 1);color[x] = 0;//回溯}}int main() {ios::sync_with_stdio(false);cout << fixed << setprecision(2);cin >> n >> m;while (cin >> f >> t) { //不断读取图的边，建图if (f == 0 && t == 0) break;p[f][t] = p[t][f] = true; //双向边}draw(1);cout << "总共有" << sum << "种涂⾊⽅案" << "\n";return0; // good job! }。

算法设计课程设计题目图着色问题姓名学号专业年级指导教师职称2014年 12月 4日图的m着色问题1 摘要 (3)2 图的着色问题 (4)2.1 图的着色问题的来源 (4)2.2 图的着色问题的描述 (4)3算法的基本思想 (4)3.1 求极小覆盖法----布尔代数法 (4)3.2 穷举法－Welch Powell着色法 (4)3.3 回溯法 (4)3.4 贪心法 (4)3.5 蚁群算法 (5)4算法步骤 (5)4.1 求极小覆盖法----布尔代数法 (4)4.2 穷举法－Welch Powell着色法 (4)4.3 回溯法 (4)4.4 贪心法 (4)4.5 蚁群法 (4)5 理论分析（复杂度比较）、实验性能比较 (7)5.1 复杂度分析 (4)5.2 实验性能比较 (4)6 心得体会 (8)7参考文献 (8)8 附录 (8)摘要图论是近年来发展迅速而又应用广泛的一门新兴学科，已广泛应用于运筹学、网络理论、信息论、控制论、博奕论以及计算机科学等各个领域。

一般说来，图的着色问题最早起源于著名的“四色问题”，染色问题不但有着重要的理论价值，而且，它和很多实际问题有着密切联系，例如通讯系统的频道分配问题，更有着广泛的应用背景. 本文首先讨论了人工智能的状态搜索方法在图着色中的具体应用，并用可视化方法展示了低维的着色空间和约束的具体意义。

关键词：图着色 c++代码2、图的着色问题2.1图的着色问题的来源1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)在一家科研单位从事地图着色工作时，发现“任何一张地图似乎只用四种颜色就能使具有共同边界的国家着上不同的颜色。

”用数学语言来表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。

”这就是源于地图着色的四色猜想问题。

这里所指的相邻区域，是指有一整段边界是公共边界。