圖著色問題

圖的著色問題,主講人：XXX,內(nèi) 容,問題來源 基本概念 常用算法 回溯法 程序演示,問題來源四色問題,圖的著色問題是由地圖的著色問題引申而來的：用m種顏色為地圖著色，使得地圖上的每一個區(qū)域著一種顏色，且相鄰區(qū)域顏色不同。 四色問題：“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色?！?問題處理：如果把每一個區(qū)域收縮為一個頂點，把相鄰兩個區(qū)域用一條邊相連接，就可以把一個區(qū)域圖抽象為一個平面圖。 例：圖（a）所示的區(qū)域圖可抽象為圖（b）所表示的平面圖。區(qū)域用城市名表示，顏色用數(shù)字表示，則圖中表示了不同區(qū)域的不同著色問題 。,圖著色問題的分類,頂點著色:給定無向圖G=(V,E)，用m種顏色為圖中的每個頂點著色，要求每個頂點著一種顏色，并使相鄰兩頂點之間有著不同的顏色，這個問題稱為圖的頂點著色問題。 邊著色:給定無環(huán)圖G=(V,E)，用m種顏色為圖中的每條邊著色，要求每條邊著一種顏色，并使相鄰兩條邊有著不同的顏色，這個問題稱為圖的邊著色問題。,頂點著色問題的基本概念,m可著色：若一個圖最少需要m種顏色才能使圖中每條邊連接的兩個頂點著不同的顏色，則稱m為該圖的色數(shù)。 求m的問題稱為圖的m可著色優(yōu)化問題。 獨立集：對圖G=(V,E)，設(shè)S是V的一個子集，其中任意兩個頂點在G中均不相鄰，則稱S為G的一個獨立集。 最大獨立集：如果G不包含適合|S|S|的獨立集S，則稱S為G的最大獨立集。 極大覆蓋：設(shè)K是G的一個獨立集，并且對于V-K的任一頂點v，K+v都不是G的獨立集，則稱K是G的一個極大覆蓋。 極小覆蓋：極大獨立集的補集稱為極小覆蓋。 V的子集K是G的極小覆蓋當且僅當：對于每個頂點v或者v屬于K，或者v的所有鄰點屬于K（但兩者不同時成立）。,獨立集：S1=A，D，S2=B，C 找不到比它們更大的獨立集，故S1、S2是最大獨立集。 極大覆蓋：A ，B，C，D S1 = B，C，對于任意的vB，C，加入集合S1之后，S1不再是一個獨立集。S1是一個極大覆蓋。,例 子,頂點著色的算法思想,由“每個同色頂點集合中的兩兩頂點不相鄰”可以看出，同色頂點集實際上是一個獨立集，當我們用第1種顏色上色時，為了盡可能擴大顏色1的頂點個數(shù)，逼近所用顏色數(shù)最少的目的，事實上就是找出圖G的一個極大獨立集并給它涂上顏色1。用第2種顏色上色時，同樣選擇另一個極大獨立集涂色，.，當所有頂點涂色完畢，所用的顏色數(shù)即為所選的極大獨立集的個數(shù)。 當然，上述顏色數(shù)未必就是X（G），而且其和能夠含所有頂點的極大獨立集個數(shù)未必唯一。,頂點著色問題的常用算法,目前解決該問題的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、布爾代數(shù)法、蟻群算法、貪婪算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法以及模擬退火算法等。 通常的解決著色問題的算法采用蠻力法、貪婪法、深度優(yōu)先或廣度優(yōu)先等思想可以得到最優(yōu)解，但時間復雜性太大，如回溯法，其計算時間復雜性為指數(shù)階的；有的在多項式時間內(nèi)能得到可行解，但不是最優(yōu)解，如Welsh-Powell算法和貪婪算法。而對于像遺傳算法和神經(jīng)網(wǎng)絡(luò)這樣復雜的啟發(fā)式算法，通常算法本身復雜性較大，并且算法效率難以分析，最終得到的是近似解，其是否最優(yōu)解也不能保證。,窮舉法WELCH POWELL著色法,步驟： I將圖G中的結(jié)點按度數(shù)的遞減順序進行排列(這種排列可能不是唯一的，因為有些結(jié)點的度數(shù)相同)。 II用第一種顏色對第一結(jié)點著色，并按排列順序?qū)εc前面著色結(jié)點不鄰接的每一結(jié)點著上同樣的顏色。 III用第二種顏色對尚未著色的結(jié)點重復II，用第三種顏色繼續(xù)這種做法，直到所有的結(jié)點全部著上色為止。,貪心法,貪心策略：選擇一種顏色，以任意頂點作為開始頂點，依次考察圖中的未被著色的每個頂點，如果一個頂點可以用顏色1著色，換言之，該頂點的鄰接點都還未被著色，則用顏色1為該頂點著色，當沒有頂點能以這種顏色著色時，選擇顏色2和一個未被著色的頂點作為開始頂點，用第二種顏色為盡可能多的頂點著色，如果還有未著色的頂點，則選取顏色3并為盡可能多的頂點著色，依此類推。,回溯法,局部有效著色：如果其中i個頂點已經(jīng)著色，滿足相鄰兩個頂點的顏色都不一樣并且仍有顏色未被使用，就稱當前的著