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

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

溫馨提示

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

評論

0/150

提交評論