圖的m著色問題 講課 吳雙燕PPT制作 譚曉雅 目錄 問題產(chǎn)生的背景 問題描述 程序運(yùn)行及結(jié)果 四 一 二 三 算法設(shè)計(jì)與分析 圖的著色問題是由地圖的著色問題引申而來的 用m種顏色為地圖著色 使得地圖上的每一個(gè)區(qū)域著一種顏色 且相鄰區(qū)域顏色不同 一 產(chǎn)生背景 二 問題描述 給定無向連通圖G和m種不同的顏色 用這些顏色為圖G的各頂點(diǎn)著色 每個(gè)頂點(diǎn)著一種顏色 是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色 如果有則稱這個(gè)圖是m可著色 否則稱這個(gè)圖不是m可著色 若一個(gè)圖最少需要k種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著不同顏色 則稱這個(gè)數(shù)k為該圖的色數(shù) 三 算法設(shè)計(jì) 輸入 顏色種類m輸出 如果這個(gè)圖不是m可著色 給出否定回答 如果這個(gè)圖是m可著色的 找出所有不同的著色法 1 4 2 3 可以用一下鄰接矩陣來表示 1111011111111101111101011 鄰接矩陣中通常用二維數(shù)組來存放邊之間的關(guān)系 用一維數(shù)組來存放頂點(diǎn)的信息 所以在接下來的求解問題中我們將用到二維數(shù)組a來存放兩邊是否相鄰 用一維數(shù)組x來存放每個(gè)頂點(diǎn)的顏色 x i j表示第i個(gè)節(jié)點(diǎn)圖第j中顏色 5 我們可以把問題簡(jiǎn)化為3個(gè)點(diǎn)來分析 現(xiàn)給定如下圖 怎樣求解呢 1 2 3 該圖的色數(shù)是多少 怎樣用解空間樹來表示呢 由圖可知 對(duì)于每一個(gè)頂點(diǎn)可選的顏色可以有3種不同的選擇 所以每一個(gè)節(jié)點(diǎn)有3個(gè)兒子節(jié)點(diǎn) 有4層 判斷條件是什么 新加入來得節(jié)點(diǎn)t取某一種顏色i時(shí) 依次和上層的每一個(gè)節(jié)點(diǎn)j j t 比較 如果a t j 1并且x t x j 那么它是不可著色的 intOK intt inti intj for j 1 j t j if a t j 2020 3 10 10 可編輯 模擬演示 t 1 t 2 t 3 t 4 voidBacktrace intt intm 當(dāng)前節(jié)點(diǎn) 顏色的種類 當(dāng)搜索的當(dāng)前節(jié)點(diǎn)t N時(shí) m種顏色依次試用 調(diào)用函數(shù)OK進(jìn)行判斷 如果當(dāng)前顏色可以 則進(jìn)入下一層搜索 當(dāng)搜索到最葉子節(jié)點(diǎn)時(shí) t N 即可輸出一種方案 for i 1 i m i if OK t i x t i Backtrace t 1 m if t N sum printf 第 d種方案 n sum for i 1 i N i printf d x i 四 程序代碼 include include defineN3 圖中節(jié)點(diǎn)的個(gè)數(shù)inta N 1 N 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 鄰接矩陣intx N 1 記錄顏色intsum 0 保存可以著色的方案數(shù)intOK intt inti 判斷函數(shù) intj for j 1 j t j if a t j voidBacktrace intt intm inti if t N 算法搜索至葉子節(jié)點(diǎn) sum printf 第 d種方案 n sum for i 1 i N i printf d x i printf n else for i 1 i m i if OK t i x t i Backtrace t 1 m intmain intm inti printf 請(qǐng)輸入顏色種類 n scanf d 運(yùn)行結(jié)果 當(dāng)N 5時(shí) 色數(shù)又是多少呢 X 1 1 X 1 4 X 1 2