圖頂點(diǎn)m著色的改進(jìn)算法

《圖頂點(diǎn)m著色的改進(jìn)算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、維普資訊http://www.cqvip.com第14卷第3期天津理工學(xué)院學(xué)報(bào)V01．14No．31998年9月JOURNALOFTIANJININSTITUTEOFTECHNOLOGYSep．1998圖頂點(diǎn)772著色的改進(jìn)算法李文王哲明t／一劉林0

2、t摘要對于解決圖頂點(diǎn)著色問題，目前較常使用DFS算法，而由于該算法存在效率不高問題，故提出DFS改進(jìn)算法，極大提高了該算法的效率，對于較難的圖頂點(diǎn)著色問題，利用該改進(jìn)算法更為有利．關(guān)鍵詞NP完全問題Christofides算法分婁"船嘰·肴已圉點(diǎn)色I(xiàn)mprovedAlgorithmsOilhowtoP

3、utmColorsontheVertexesofChartsLiWenWangZheminLuLin(TianjinInsitituteofTechnologyTianiin300191)AbstractNowadays，thepopularmethodtotheproblemofhowtOputmcolorsonthevertexesofchartsisDFSalgorithm，butitisinefficient，andneedtobeimproved．Theimprovedalgorithmisgiv—en．Theimprovedonehas

4、moreadvantageinsolvingdifficultcoloringprobleminapplication．KeywordsNPcompleteproblemChristofidesalgorithmDFSalgorithmmaximumindependenceset1問題的提出圖頂點(diǎn)著色問題是對一個(gè)Ⅳ頂點(diǎn)的圖G(V，E)，用種顏色給圖G中所有頂點(diǎn)，，?逐一著上m色中的一種顏色，并且使任兩個(gè)相鄰頂點(diǎn)異色．該問題是一個(gè)NP完全問題．對圖頂點(diǎn)m著色問題抽象為一般組合模型，就是求出對應(yīng)于，，?的一個(gè)元組X一(，，?)，其中．∈M，M一{1，2

5、．3，?，卅}，且X滿足于給定的約束條件，BoundN(，一)，即對所有的，，11≤iJN，若與相鄰，則Il≠．求解該問題的算法有兩類：Christofides算法和DFS算法(回朔算法)r】]1．1Christofides算法1)用代數(shù)法求出G的所有極大獨(dú)立集(7，7}，?)；2)對其中之一，1≤it≤^，求出G一的所有極大獨(dú)立集(，，?7)i3)類似于步驟2)，可以求出一組極大獨(dú)立集(，坪，?)，對應(yīng)G的一種典型上色；若m，算法正常結(jié)束；否則，回步驟2，直至算法正常結(jié)束．Christofides算法，不易實(shí)現(xiàn)，并且計(jì)算代價(jià)高，故使用較少．1．2

6、DFS回溯算法：1)假設(shè)m種顏色對應(yīng)M一{1，2，3，?m，；2)按遞增選色序．首先確定．r的值，井按約束條件逐一確定．r一，≈一．的值．若在給IJ定值時(shí)找不到滿足約束條件Boundj(，．r”≈一，IJ)的任一值，則回溯到上一層，給≈一重新定一滿足Bound／(，一IJ·)的值．若I一的下一“合適”值存在，則向下試探；否則，再回朔．收稿日期：1998一O3—051；乍出生．jj}=師維普資訊http://www.cqvip.com60天津理工學(xué)院學(xué)報(bào)l4卷DFS回溯算法簡單易行，常被人們使用．但該算法的效率較低，這是因?yàn)闆]有利用回溯過程的失敗經(jīng)驗(yàn)

7、．以下用圖G中硬點(diǎn)3著色為倒說明．假設(shè)用DFS算法已給G的、，?逐～著上一種滿足約束條件的顏色，現(xiàn)對著色，由于"19，著1色將與、?口的當(dāng)前色“沖突”，。著2色將與、。的當(dāng)前色“沖突”，著3色將與的當(dāng)前色“沖突”，按照DFS，先調(diào)整的著色，再調(diào)整的著色，然后，試給著色，??，這樣，經(jīng)過漫長的過程才能對的著色調(diào)整)．事實(shí)上，由于口，、、已分別著上1、2、3色，且與它們均相鄰，若-、、．的著色不調(diào)整，，就無法選擇一個(gè)合適的著色．而對、，、的反復(fù)調(diào)整全身無用功．這是DFS法的·大弱點(diǎn)0]，因而采用“智能”回溯策略取代DFS的逐層回期策略，實(shí)現(xiàn)多次回溯．y

8、-(3)圍1圈G頂點(diǎn)著色的一種格局田2田G點(diǎn)著色的一十解(v1．v2?．vI為著色)(括號中的色表示顏色標(biāo)號)2DFS的改進(jìn)算法假定給定問題有個(gè)頂點(diǎn)．有m種色可選，并假定“智能回溯法按深度優(yōu)先順序逐一對-，．?試著色，這與DFS法相同，以下是實(shí)現(xiàn)方法．2．1定義經(jīng)驗(yàn)矩陣并置初值定義經(jīng)驗(yàn)矩陣E[1：N，1：m]，并將Eli，。]一，(1Ⅳ)，即E的第i行全置為i，這里E中單元E[，力意睬著頂點(diǎn)著色(1≤i≤N；1≤Jm)．2．2簿記經(jīng)驗(yàn)每當(dāng)頂點(diǎn)，是著J色(1≤i≤N；1J≤m)時(shí)，按下列公式將ED，力置相應(yīng)值．i，可著j色．著j色，與k個(gè)頂點(diǎn)rain

9、{index('e11)，index(2)，?．index(vn)}lr著色“沖突”時(shí)，E[i，力(1ki—1)，(1r)