本文關(guān)鍵詞：隨機圖的均勻染色算法研究

  更多相關(guān)文章： 隨機圖 圖染色 均勻邊染色 均勻全染色

【摘要】：圖染色問題是一種典型的組合優(yōu)化問題,現(xiàn)實生活中的很多問題如加工調(diào)度、任務(wù)分配、負載平衡等都可以用圖染色的方法來解決。近些年來,隨著計算機技術(shù)的發(fā)展和解決實際問題的需要,一些經(jīng)典的智能算法被用來研究和嘗試解決圖染色問題,如蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)等,但限于染色問題的多樣性和復(fù)雜性,目前這些算法普遍應(yīng)用于解決圖的正常點染色和正常邊染色,而對于圖染色問題中多約束條件的染色問題,公開發(fā)表的文獻中尚不多見,因此尋求新的智能算法來解決圖的多約束條件染色問題是一個具有理論和實際意義的課題。圖的均勻染色是指圖中任意兩個色類的顏色個數(shù)最大相差1,在解決生產(chǎn)調(diào)度、任務(wù)分配和負載均衡等問題方面有很好的應(yīng)用,從已公開發(fā)表的文獻看,有關(guān)圖的均勻染色算法的成果少見。本文所做的核心工作就是根據(jù)四種均勻染色的定義,分別設(shè)計并實現(xiàn)了四種均勻染色算法,以及為了測試算法而設(shè)計的隨機圖生成算法,同時給出對上述算法的分析過程,最后利用設(shè)計的測試圖集對算法進行了全面測試,通過對大量測試結(jié)果的分析給出了幾個有意義的結(jié)論。本文主要工作如下:(1)從隨機圖染色的角度切入,根據(jù)具體的情況將染色問題進行分類;介紹一些圖的基礎(chǔ)染色概念,如正常邊染色、全染色和在此基礎(chǔ)上衍生出的點可區(qū)別染色和鄰點可區(qū)別染色的概念;以遺傳算法和模擬退火算法作為經(jīng)典智能算法的代表,介紹其在圖染色問題中的應(yīng)用,同時總結(jié)遺傳算法和模擬退火算法在解決圖染色問題中的優(yōu)點和不足,為研究解決圖的均勻染色問題提供思路和參考。(2)設(shè)計并實現(xiàn)四種均勻染色算法。根據(jù)圖的均勻邊染色、均勻全染色、點可區(qū)別均勻邊染色和鄰點可區(qū)別均勻邊染色的定義,設(shè)計了四種算法,每種算法的基本思想是將目標(biāo)問題分解成幾個子問題,設(shè)計相應(yīng)的子約束函數(shù),然后根據(jù)這些子約束函數(shù)進行迭代調(diào)整,逐步解決每個子問題,最終使得總目標(biāo)函數(shù)的值為0,染色成功,算法結(jié)束。文中給出了針對算法的正確性、有效性和時間復(fù)雜度的分析過程。(3)設(shè)計了兩類測試圖集對算法進行測試,一類為7個點以內(nèi)的所有圖,一類為15個點以內(nèi)的特殊圖。通過對測試結(jié)果的分析,得到了有意義的結(jié)論�；谡＞鶆蜻吶旧惴▽o線傳感器網(wǎng)絡(luò)廣播調(diào)度進行時隙分配,得到了較為理想的結(jié)果。
【關(guān)鍵詞】：隨機圖 圖染色 均勻邊染色 均勻全染色
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-10
• 1 緒論10-14
• 1.1 引言10-11
• 1.2 研究背景、目的及意義11-12
• 1.3 本文的主要工作12
• 1.4 本文的組織結(jié)構(gòu)12-14
• 2 圖染色相關(guān)概念及經(jīng)典算法概述14-22
• 2.1 引言14
• 2.2 圖染色基本定義和猜想14-16
• 2.3 遺傳算法在圖染色中的應(yīng)用16-19
• 2.3.1 遺傳算法的基本思想16
• 2.3.2 遺傳算法的基本步驟16
• 2.3.3 遺傳算法的圖染色中的應(yīng)用16-19
• 2.4 模擬退火算法19-21
• 2.4.1 模擬退火算法的基本思想19
• 2.4.2 模擬退火算法的基本步驟19-20
• 2.4.3 模擬退火算法在圖染色中的應(yīng)用20-21
• 2.5 本章小結(jié)21-22
• 3 圖的生成算法22-32
• 3.1 引言22
• 3.2 隨機圖的生成算法22-25
• 3.2.1 隨機圖的定義和模型22
• 3.2.2 算法描述及流程圖22-24
• 3.2.3 算法測試24-25
• 3.3 生成有限點數(shù)所有圖算法25-31
• 3.3.1 定義主要數(shù)據(jù)結(jié)構(gòu)及生成樹25-26
• 3.3.2 算法描述及流程圖26-29
• 3.3.3 算法測試29-31
• 3.3.4 實驗結(jié)果31
• 3.4 本章小結(jié)31-32
• 4 隨機圖的正常均勻邊染色及正常均勻全算法32-55
• 4.1 引言32
• 4.2 正常均勻邊染色算法32-43
• 4.2.1 正常均勻邊染色的相關(guān)定義和猜想32
• 4.2.2 目標(biāo)函數(shù)的構(gòu)建32-33
• 4.2.3 主要數(shù)據(jù)結(jié)構(gòu)的定義33-34
• 4.2.4 正常均勻邊染色算法描述及流程圖34-36
• 4.2.5 算法測試36-41
• 4.2.6 算法分析41-42
• 4.2.7 實驗結(jié)果42-43
• 4.3 正常均勻全染色算法43-53
• 4.3.1 正常均勻全染色的相關(guān)定義和猜想43-44
• 4.3.2 目標(biāo)函數(shù)的構(gòu)建44-45
• 4.3.3 正常均勻全染色算法描述及流程圖45-47
• 4.3.4 算法測試47-50
• 4.3.5 算法分析50-52
• 4.3.6 實驗結(jié)果52-53
• 4.4 本章小結(jié)53-55
• 5 隨機圖的可區(qū)別均勻邊染色算法55-75
• 5.1 引言55
• 5.2 鄰點可區(qū)別均勻邊染色算法55-64
• 5.2.1 鄰點可區(qū)別均勻邊染色的相關(guān)定義和猜想55
• 5.2.2 目標(biāo)函數(shù)的構(gòu)建55-56
• 5.2.3 鄰點可區(qū)別均勻邊染色算法描述及流程圖56-59
• 5.2.4 算法測試59-62
• 5.2.5 算法分析62-63
• 5.2.6 實驗結(jié)果63-64
• 5.3 點可區(qū)別均勻邊染色算法64-74
• 5.3.1 點可區(qū)別均勻邊染色的相關(guān)定義和猜想64-65
• 5.3.2 目標(biāo)函數(shù)的構(gòu)建65
• 5.3.3 點可區(qū)別均勻邊染色算法描述及流程圖65-67
• 5.3.4 算法測試67-71
• 5.3.5 算法分析71-72
• 5.3.6 實驗結(jié)果72-74
• 5.4 本章小結(jié)74-75
• 6 基于均勻邊染色的無線傳感網(wǎng)絡(luò)廣播調(diào)度算法75-79
• 6.1 引言75-76
• 6.2 TDMA時隙分配76
• 6.3 均勻邊染色算法解決廣播調(diào)度問題76-78
• 6.3.1 步驟描述77
• 6.3.2 算法結(jié)果及分析77-78
• 6.4 本章小結(jié)78-79
• 結(jié)論79-80
• 致謝80-81
• 參考文獻81-84
• 攻讀學(xué)位期間的研究成果84

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 彭煜q;;淺談無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)隱私保護技術(shù)[J];科技展望;2016年13期

2 岳鵬;王柯;鄭杰;;一種基于優(yōu)先級的TDMA時隙接入算法[J];無線互聯(lián)科技;2016年04期

3 李敬文;張云寒;陳志鵬;孫亮;;圖的點可區(qū)別邊染色算法研究[J];計算機應(yīng)用研究;2014年03期

4 馮珊珊;張月琴;郭旭敏;;基于改進圖著色理論的聚類算法[J];計算機工程與設(shè)計;2013年05期

5 李敬文;于自強;;基于立方體染色的排課表模型[J];計算機工程;2010年24期

6 馬剛;馬少仙;張忠輔;;一些聯(lián)圖的均勻全染色[J];應(yīng)用數(shù)學(xué)學(xué)報;2010年04期

7 鄧宇;汪黎;晏小波;王桂彬;唐滔;;基于超完美圖著色的存儲分配算法[J];計算機科學(xué);2008年09期

8 馬剛;馬少仙;張忠輔;;關(guān)于W_m∨S_n的均勻全染色[J];數(shù)學(xué)研究;2007年03期

9 文軍,李冰,王清蓉,杜文;機場停機位分配問題的圖著色模型及其算法[J];系統(tǒng)工程理論方法應(yīng)用;2005年02期

10 ;On adjacent-vertex-distinguishing total coloring of graphs[J];Science in China,Ser.A;2005年03期

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前5條

1 張佳麗;關(guān)于圖的若干染色問題的研究[D];中國礦業(yè)大學(xué);2014年

2 王聰;基于圖譜理論在圖弱染色方面的算法研究[D];蘭州交通大學(xué);2014年

3 王倩;隨機圖的Smarandachely點可區(qū)別染色算法研究[D];蘭州交通大學(xué);2014年

4 桂浩;圖的均勻點染色與均勻全染色[D];浙江師范大學(xué);2014年

5 李華龍;平面圖的鄰和可區(qū)別全染色[D];山東大學(xué);2014年

，

本文編號：1061167