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

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

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

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

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