Kn-E(H)圖和大規(guī)模隨機(jī)圖的染色算法研究.pdf

1、圖論是組合和離散數(shù)學(xué)的最重要的研究分支之一，也是計算機(jī)基礎(chǔ)理論科學(xué)的重要組成部分，它以圖為研究對象，在計算機(jī)理論、運(yùn)籌學(xué)、系統(tǒng)科學(xué)中都有著重要的研究價值。當(dāng)前，計算機(jī)技術(shù)的革新已經(jīng)成為經(jīng)濟(jì)發(fā)展和科學(xué)研究的重要動力，由此大大推動了以圖為研究對象的圖論的快速發(fā)展。
　　圖染色起源于一個經(jīng)典的問題:“四色猜想”，是圖論的一個主要研究方向之一，很多實(shí)際的問題都與圖染色問題相關(guān)，對其的研究有著很好的理論背景和應(yīng)用價值。現(xiàn)實(shí)生活中的很多問題如

2、交通定向、組合優(yōu)化、計算機(jī)通信等都可以用圖染色來解決。近現(xiàn)代以來，國內(nèi)外的很多專家和學(xué)者嘗試使用各種工具和方法來研究圖染色問題，鄰點(diǎn)可區(qū)別邊染色、鄰點(diǎn)可區(qū)別全染色、點(diǎn)可區(qū)別全染色、均勻染色、弱染色等一系列的概念被提出，并且得到了一系列的定理、推論和猜想，同時還有其它圖染色新概念被提出。
　　圖染色問題一直是一個難題，常見的智能算法如遺傳算法、模擬退火算法、粒子群優(yōu)化算法、神經(jīng)網(wǎng)絡(luò)等應(yīng)用于解決圖的染色問題，但一般僅限于解決單目標(biāo)的正

3、常點(diǎn)染色、正常邊染色等圖染色問題，而面對如鄰點(diǎn)可區(qū)別均勻全染色、Smart點(diǎn)可區(qū)別全染色這樣的多目標(biāo)優(yōu)化的圖染色問題時，傳統(tǒng)的智能優(yōu)化算法會陷入困境，其局限性就顯而易見了。
　　Kn\E(H)圖的染色問題是一個很有研究價值的課題，一方面，通過傳統(tǒng)的數(shù)學(xué)方法很難實(shí)現(xiàn)對其染色，因此利用計算機(jī)算法來作為解決此類圖的染色是一個全新的方法，由此可以開啟相關(guān)圖的一系列染色。另一方面，以往對于圖的染色算法，主要針對頂點(diǎn)數(shù)較小的圖，算法難以實(shí)現(xiàn)對

4、大規(guī)模隨機(jī)圖的染色。本文針對Kn\E(H)圖的點(diǎn)可區(qū)別全染色、鄰點(diǎn)可區(qū)別全染色問題以及大規(guī)模隨機(jī)圖的分割和鄰點(diǎn)可區(qū)別邊染色問題，分別設(shè)計了的計算機(jī)算法，來驗(yàn)證Kn\E(H)圖和大規(guī)模隨機(jī)圖染色相關(guān)的定理、推論和猜想的正確性，并為相關(guān)的研究提供基礎(chǔ)研究數(shù)據(jù)支持。論文的主要研究工作包括以下幾個部分。
　　(1)設(shè)計并完成了Kn\E(H)圖的生成算法，并驗(yàn)證了圖的正確性，為后續(xù)染色算法做準(zhǔn)備。實(shí)現(xiàn)了對Kn\E(H)圖的點(diǎn)可區(qū)別全染色、鄰