算法设计课程设计--图的m着色问题

《算法设计课程设计--图的m着色问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、述框架backtrack设计图的m着色算法。用图的邻接矩阵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着色方案，当前

3、找到的m着色方案数sum增1。当I

4、turnsum;}privatestaticvoidbacktrack(intt){if(t>n){sum++;for(inti=1;i<=n;i++)System.out.println();}elsefor(inti=1;i<=m;i++)图的m着色问题x[t]=i;if(ok(t))backtrack(t+1);x[t]=0;}privatestaticbooleanok(intk){for(intj=1;j<=n;j++)if(a[k][j]&&(x[j]==x[k]))returnfalse;returntrue;}}图的m着

5、色问题1．图的m着色的回朔算法的程序:程序名：图的m着色法简要说明：此程序实现给定无向量图顶点和m种不同的颜色。用这些颜色为图的各顶点着色，每个顶点着一种颜色，并使图中每条边的两个顶点着色不同。求有多少个图色的方法？程序:importjava.io.*;//引入java.io包中的所有类importjava.util.Scanner;/*传入值:顶点数n，颜色数m输出值:当前解x，着色方案sum简要说明:定义主类和输入输出，并调用定义类Coloring*/publicclassClass1//定义主类，并调用定义类Coloring{pu

6、blicstaticvoidmain(Stringargs[]){Scannerscan=newScanner(System.in);System.out.println("p为顶点数q为颜色数");System.out.println("p的值:");intp=scan.nextInt();//输入p的值System.out.println("q的值:");intq=scan.nextInt();//输入q的值ColoringmyColor=newColoring(p,q);//为Coloring类创建一个新对象System.out.

7、println("sum="+myColor.mColoring(q));//输出着色方案最后结果InputStreamReaderin;//使运行结果的显示暂停BufferedReaderreader;in=newInputStreamReader(System.in);reader=newBufferedReader(in);Strings="";图的m着色问题try{s=reader.readLine();}catch(IOExceptione){System.out.println();System.exit(0);}Syste

8、m.out.println("TheEnd!");}}/*函数名:Coloring传入值:当前解x，着色方案sum输出值:当前解x，着色方案sum简要说明:图的可着色方法的回朔算法*/classColori