图的m着色问题回溯法

《图的m着色问题回溯法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的m着色问题1．问题描述给定无向量图G顶点和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G图中每条边的两个顶点着不同的颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色问题。2．算法设计一般连通图的可着色法问题并不仅限于平面图。给定图G=（V，E）和m种颜色，果这个图不是m可着色，给出否定回答，如果这个图是m的可着色的，找出所有不同的着色法。下面根据回朔法的递归描述框架backtrack设计图的m着色算法。用图的邻接矩

2、阵a表示无向量连通图G=（V，E）。若（i，j）属于图G=（V，E）的边集E，则a[i][j]=1，否则a[i][j]=0。整数1，2，…，m用来表示m种不同颜色。顶点i所有颜色用x[i]表示，数组x[1：n]是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第I（1<=i<=n）层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。在算法backtrack中，当i>n时，算法搜索至叶结点，得到新的m着色方案，当前找到的m着色方案数sum增1。当I

3、=1,2,…，m共m个儿子结点.对当前扩展结点Z的每一儿子结点,有方法ok检查其可行性,并以深度优先的方式递归的对可行子树搜索,或减去不可行树.3.图的m着色的回朔算法的程序:/**********************************程序名：图的m着色法**版本：VJ++6.0**开发日期：2005.10.25**简要说明：此程序实现给定无向量图顶点和m种不同的颜色。用这些颜色为图的各顶点着色，每个顶点着一种颜色，**并使图中每条边的两个顶点着色不同。求有多少个图色的方法？***********************************/importjava.

4、io.*;//引入java.io包中的所有类/********************************************函数名:Class1**传入值:顶点数n，颜色数m**输出值:当前解x，着色方案sum**简要说明:定义主类和输入输出，并调用定义类Coloring*******************************************/publicclassClass1//定义主类，并调用定义类Coloring{publicstaticvoidmain(Stringargs[]){ColoringmyColor=newColoring(3,3);

5、//为Coloring类创建一个新对象System.out.println("sum="+myColor.mColoring(3));//输出着色方案最后结果InputStreamReaderin;//使运行结果的显示暂停BufferedReaderreader;in=newInputStreamReader(System.in);reader=newBufferedReader(in);Strings="";try{s=reader.readLine();}catch(IOExceptione){System.out.println();System.exit(0);}Sys

6、tem.out.println("TheEnd!");}}/********************************************函数名:Coloring**传入值:当前解x，着色方案sum**输出值:当前解x，着色方案sum**简要说明:图的可着色方法的回朔算法*******************************************/classColoring//定义类，表示图的m着色问题{intn,m;//图的顶点数，可用颜色数boolean[][]a;//图的邻接矩阵int[]x;//当前解longsum;//当前可找到的m着色方案数Col

7、oring(intnewn,intnewm)//定义构造函数，为对象的各属性赋初值{n=newn;m=newm;sum=0;x=newint[n+5];a=newboolean[n+5][m+5];}publiclongmColoring(intmm)//显示每次搜索后总搜索结果{m=mm;sum=0;backtrack(1);returnsum;}publicvoidbacktrack(intt)//对解空间树进行搜索{if(t>n)//搜索解空间树至叶节点{sum++;for(inti=