算法設(shè)計與分析第五章-資料下載頁
2025-01-18 20:55本頁面
【正文】 0 1 1 1 1 0 0 0 R T U V W 1 P Q 1 0 1 S 0 1 0 1 0 1 0 M 0 1 0 G N O 1 0 0 1 0 1 0 Bestn=3 1 2 4 3 Bestn=3 167。 5 . 8 圖的 m 著色問題 蓋思里 (Guthrie) “四色猜想 ” 阿佩爾 (K . Appel)和哈肯 (W .Haken) 科赫 (J. Koch) 圖著色問題 (GCPGraph Coloring Problem) 給定無向連通圖 G 和 m 種不同的顏色。用這些顏色 為圖 G 的各頂點著色，是否有一種著色法使 G 中每 條邊的 2 個頂點著有不同的顏色。 }4,3,2,1{?C1 2 5 4 3 (a) r y g b 1 2 5 4 3 (b) ? }3,2,1{1 ?C? 圖著色問題 (GCPGraph Coloring Problem) 給定 無向連通 圖),( EVG ?，圖著色問題就是要 用最少的顏色))(( G?對圖 G 的頂點進行正常著 色，滿足相鄰的頂點著不同顏色的約束條件。 圖著色問題 (GCP) 設(shè)圖 ),( EVG ? , nV ?, 顏色數(shù) m , 用鄰接矩陣 A 表示 連通無向 G , 用整數(shù) m,2,1 ? 來表示 m 種不同 的顏色。頂點 i 所著的顏色用 )1( mxxii ??表示。 4 (a) 1 2 3 5 (1,2,3,1,3) 圖著色問題 (GCP) 問題的解向量可以表示為 n 元組 ),(21 nxxxx ??, 解空間樹為排序樹 , 是一棵 1?n 層的完全 m 叉樹 。 約束條件 : 1, ??ijji axx。 3,3 ?? mn例 1 1 2 3 ???????????011101110A圖著色問題 (GCP) A 11 ?x21 ?x31 ?x12 ?x13 ?x???????????011101110A回溯法的效率分析 (1) 產(chǎn)生][ kx的時間； (2) 滿足顯約束的][ kx值的個數(shù)； (3) 計算約束函數(shù) c o n s t r a i n t 的時間； (4) 計算上界函數(shù) b o u n d 的時間； (5) 滿足約束函數(shù)和上界函數(shù)約束的所有][ kx的個數(shù)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1