圖的m著色問題回溯法.doc_第1頁
圖的m著色問題回溯法.doc_第2頁
圖的m著色問題回溯法.doc_第3頁
圖的m著色問題回溯法.doc_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

圖的m著色問題1 問題描述給定無向量圖G頂點(diǎn)和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G圖中每條邊的兩個(gè)頂點(diǎn)著不同的顏色。這個(gè)問題是圖的m可著色判定問題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的兩個(gè)頂點(diǎn)著不同的顏色，則稱這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù)m的問題稱為圖的m可著色問題。2 算法設(shè)計(jì)一般連通圖的可著色法問題并不僅限于平面圖。給定圖G=（V，E）和m種顏色，果這個(gè)圖不是m可著色，給出否定回答，如果這個(gè)圖是m的可著色的，找出所有不同的著色法。下面根據(jù)回朔法的遞歸描述框架backtrack設(shè)計(jì)圖的m著色算法。用圖的鄰接矩陣a表示無向量連通圖G=（V，E）。若（i，j）屬于圖G=（ V，E）的邊集E，則aij=1，否則aij=0。整數(shù)1，2，m用來表示m種不同顏色。頂點(diǎn)i所有顏色用xi表示，數(shù)組x1：n是問題的解向量。問題的解空間可表示為一棵高度為n+1的完全m叉樹。解空間樹的第I（1=in時(shí)，算法搜索至葉結(jié)點(diǎn)，得到新的m著色方案，當(dāng)前找到的m著色方案數(shù)sum增1。當(dāng)I n )/搜索解空間樹至葉節(jié)點(diǎn) sum+;for ( int i=1; i );System.out.println();else/搜索解空間樹的內(nèi)結(jié)點(diǎn)for ( int i=1; i = m; i+ )xt=i;/保存填充的顏色if ( ok(t) )backtrack(t+1);private boolean ok( int k )/檢查顏色可用性for ( int j=1; j = n; j+ )if ( akj & (xj=xk) ) return false;else;return true; 4.比對程序5.算法效率圖的m可著色回朔法的計(jì)算時(shí)間上界可以通過解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)估計(jì). 圖的可著色問 n-1題的解空間數(shù)中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是mi. 對于每一個(gè)內(nèi)結(jié)點(diǎn),在最壞情況下,用方法ok檢查當(dāng)前t=0擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí)O(mn). 因此

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論