算法設(shè)計(jì)課程設(shè)計(jì)--圖的m著色問(wèn)題

《算法設(shè)計(jì)課程設(shè)計(jì)--圖的m著色問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、圖的m著色問(wèn)題1．問(wèn)題描述給定無(wú)向量圖G頂點(diǎn)和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G圖中每條邊的兩個(gè)頂點(diǎn)著不同的顏色。這個(gè)問(wèn)題是圖的m可著色判定問(wèn)題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的兩個(gè)頂點(diǎn)著不同的顏色，則稱(chēng)這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù)m的問(wèn)題稱(chēng)為圖的m可著色問(wèn)題。圖的m著色問(wèn)題1．算法設(shè)計(jì)一般連通圖的可著色法問(wèn)題并不僅限于平面圖。給定圖G=（V，E）和m種顏色，果這個(gè)圖不是m可著色，給出否定回答，如果這個(gè)圖是m的可著色的，找出所有不同的著色法。下面根據(jù)回朔法的遞歸描

2、述框架backtrack設(shè)計(jì)圖的m著色算法。用圖的鄰接矩陣a表示無(wú)向量連通圖G=（V，E）。若（i，j）屬于圖G=（V，E）的邊集E，則a[i][j]=1，否則a[i][j]=0。整數(shù)1，2，…，m用來(lái)表示m種不同顏色。頂點(diǎn)i所有顏色用x[i]表示，數(shù)組x[1：n]是問(wèn)題的解向量。問(wèn)題的解空間可表示為一棵高度為n+1的完全m叉樹(shù)。解空間樹(shù)的第I（1<=i<=n）層中每一結(jié)點(diǎn)都有m個(gè)兒子，每個(gè)兒子相應(yīng)于x[i]的m個(gè)可能的著色之一。第n+1層結(jié)點(diǎn)均為葉結(jié)點(diǎn)。在算法backtrack中，當(dāng)i>n時(shí)，算法搜索至葉結(jié)點(diǎn)，得到新的m著色方案，當(dāng)前

3、找到的m著色方案數(shù)sum增1。當(dāng)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著色問(wèn)題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、色問(wèn)題1．圖的m著色的回朔算法的程序:程序名：圖的m著色法簡(jiǎn)要說(shuō)明：此程序?qū)崿F(xiàn)給定無(wú)向量圖頂點(diǎn)和m種不同的顏色。用這些顏色為圖的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色，并使圖中每條邊的兩個(gè)頂點(diǎn)著色不同。求有多少個(gè)圖色的方法？程序:importjava.io.*;//引入java.io包中的所有類(lèi)importjava.util.Scanner;/*傳入值:頂點(diǎn)數(shù)n，顏色數(shù)m輸出值:當(dāng)前解x，著色方案sum簡(jiǎn)要說(shuō)明:定義主類(lèi)和輸入輸出，并調(diào)用定義類(lèi)Coloring*/publicclassClass1//定義主類(lèi)，并調(diào)用定義類(lèi)Coloring{pu

6、blicstaticvoidmain(Stringargs[]){Scannerscan=newScanner(System.in);System.out.println("p為頂點(diǎn)數(shù)q為顏色數(shù)");System.out.println("p的值:");intp=scan.nextInt();//輸入p的值System.out.println("q的值:");intq=scan.nextInt();//輸入q的值ColoringmyColor=newColoring(p,q);//為Coloring類(lèi)創(chuàng)建一個(gè)新對(duì)象System.out.

7、println("sum="+myColor.mColoring(q));//輸出著色方案最后結(jié)果InputStreamReaderin;//使運(yùn)行結(jié)果的顯示暫停BufferedReaderreader;in=newInputStreamReader(System.in);reader=newBufferedReader(in);Strings="";圖的m著色問(wèn)題try{s=reader.readLine();}catch(IOExceptione){System.out.println();System.exit(0);}Syste

8、m.out.println("TheEnd!");}}/*函數(shù)名:Coloring傳入值:當(dāng)前解x，著色方案sum輸出值:當(dāng)前解x，著色方案sum簡(jiǎn)要說(shuō)明:圖的可著色方法的回朔算法*/classColori