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

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

【摘要】：圖染色問(wèn)題是一種典型的組合優(yōu)化問(wèn)題,現(xiàn)實(shí)生活中的很多問(wèn)題如加工調(diào)度、任務(wù)分配、負(fù)載平衡等都可以用圖染色的方法來(lái)解決。近些年來(lái),隨著計(jì)算機(jī)技術(shù)的發(fā)展和解決實(shí)際問(wèn)題的需要,一些經(jīng)典的智能算法被用來(lái)研究和嘗試解決圖染色問(wèn)題,如蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)等,但限于染色問(wèn)題的多樣性和復(fù)雜性,目前這些算法普遍應(yīng)用于解決圖的正常點(diǎn)染色和正常邊染色,而對(duì)于圖染色問(wèn)題中多約束條件的染色問(wèn)題,公開(kāi)發(fā)表的文獻(xiàn)中尚不多見(jiàn),因此尋求新的智能算法來(lái)解決圖的多約束條件染色問(wèn)題是一個(gè)具有理論和實(shí)際意義的課題。圖的均勻染色是指圖中任意兩個(gè)色類的顏色個(gè)數(shù)最大相差1,在解決生產(chǎn)調(diào)度、任務(wù)分配和負(fù)載均衡等問(wèn)題方面有很好的應(yīng)用,從已公開(kāi)發(fā)表的文獻(xiàn)看,有關(guān)圖的均勻染色算法的成果少見(jiàn)。本文所做的核心工作就是根據(jù)四種均勻染色的定義,分別設(shè)計(jì)并實(shí)現(xiàn)了四種均勻染色算法,以及為了測(cè)試算法而設(shè)計(jì)的隨機(jī)圖生成算法,同時(shí)給出對(duì)上述算法的分析過(guò)程,最后利用設(shè)計(jì)的測(cè)試圖集對(duì)算法進(jìn)行了全面測(cè)試,通過(guò)對(duì)大量測(cè)試結(jié)果的分析給出了幾個(gè)有意義的結(jié)論。本文主要工作如下:(1)從隨機(jī)圖染色的角度切入,根據(jù)具體的情況將染色問(wèn)題進(jìn)行分類;介紹一些圖的基礎(chǔ)染色概念,如正常邊染色、全染色和在此基礎(chǔ)上衍生出的點(diǎn)可區(qū)別染色和鄰點(diǎn)可區(qū)別染色的概念;以遺傳算法和模擬退火算法作為經(jīng)典智能算法的代表,介紹其在圖染色問(wèn)題中的應(yīng)用,同時(shí)總結(jié)遺傳算法和模擬退火算法在解決圖染色問(wèn)題中的優(yōu)點(diǎn)和不足,為研究解決圖的均勻染色問(wèn)題提供思路和參考。(2)設(shè)計(jì)并實(shí)現(xiàn)四種均勻染色算法。根據(jù)圖的均勻邊染色、均勻全染色、點(diǎn)可區(qū)別均勻邊染色和鄰點(diǎn)可區(qū)別均勻邊染色的定義,設(shè)計(jì)了四種算法,每種算法的基本思想是將目標(biāo)問(wèn)題分解成幾個(gè)子問(wèn)題,設(shè)計(jì)相應(yīng)的子約束函數(shù),然后根據(jù)這些子約束函數(shù)進(jìn)行迭代調(diào)整,逐步解決每個(gè)子問(wèn)題,最終使得總目標(biāo)函數(shù)的值為0,染色成功,算法結(jié)束。文中給出了針對(duì)算法的正確性、有效性和時(shí)間復(fù)雜度的分析過(guò)程。(3)設(shè)計(jì)了兩類測(cè)試圖集對(duì)算法進(jìn)行測(cè)試,一類為7個(gè)點(diǎn)以內(nèi)的所有圖,一類為15個(gè)點(diǎn)以內(nèi)的特殊圖。通過(guò)對(duì)測(cè)試結(jié)果的分析,得到了有意義的結(jié)論�；谡＞鶆蜻吶旧惴▽�(duì)無(wú)線傳感器網(wǎng)絡(luò)廣播調(diào)度進(jìn)行時(shí)隙分配,得到了較為理想的結(jié)果。
【關(guān)鍵詞】：隨機(jī)圖 圖染色 均勻邊染色 均勻全染色
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：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 隨機(jī)圖的生成算法22-25
• 3.2.1 隨機(jī)圖的定義和模型22
• 3.2.2 算法描述及流程圖22-24
• 3.2.3 算法測(cè)試24-25
• 3.3 生成有限點(diǎn)數(shù)所有圖算法25-31
• 3.3.1 定義主要數(shù)據(jù)結(jié)構(gòu)及生成樹(shù)25-26
• 3.3.2 算法描述及流程圖26-29
• 3.3.3 算法測(cè)試29-31
• 3.3.4 實(shí)驗(yàn)結(jié)果31
• 3.4 本章小結(jié)31-32
• 4 隨機(jī)圖的正常均勻邊染色及正常均勻全算法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 算法測(cè)試36-41
• 4.2.6 算法分析41-42
• 4.2.7 實(shí)驗(yàn)結(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 算法測(cè)試47-50
• 4.3.5 算法分析50-52
• 4.3.6 實(shí)驗(yàn)結(jié)果52-53
• 4.4 本章小結(jié)53-55
• 5 隨機(jī)圖的可區(qū)別均勻邊染色算法55-75
• 5.1 引言55
• 5.2 鄰點(diǎn)可區(qū)別均勻邊染色算法55-64
• 5.2.1 鄰點(diǎn)可區(qū)別均勻邊染色的相關(guān)定義和猜想55
• 5.2.2 目標(biāo)函數(shù)的構(gòu)建55-56
• 5.2.3 鄰點(diǎn)可區(qū)別均勻邊染色算法描述及流程圖56-59
• 5.2.4 算法測(cè)試59-62
• 5.2.5 算法分析62-63
• 5.2.6 實(shí)驗(yàn)結(jié)果63-64
• 5.3 點(diǎn)可區(qū)別均勻邊染色算法64-74
• 5.3.1 點(diǎn)可區(qū)別均勻邊染色的相關(guān)定義和猜想64-65
• 5.3.2 目標(biāo)函數(shù)的構(gòu)建65
• 5.3.3 點(diǎn)可區(qū)別均勻邊染色算法描述及流程圖65-67
• 5.3.4 算法測(cè)試67-71
• 5.3.5 算法分析71-72
• 5.3.6 實(shí)驗(yàn)結(jié)果72-74
• 5.4 本章小結(jié)74-75
• 6 基于均勻邊染色的無(wú)線傳感網(wǎng)絡(luò)廣播調(diào)度算法75-79
• 6.1 引言75-76
• 6.2 TDMA時(shí)隙分配76
• 6.3 均勻邊染色算法解決廣播調(diào)度問(wèn)題76-78
• 6.3.1 步驟描述77
• 6.3.2 算法結(jié)果及分析77-78
• 6.4 本章小結(jié)78-79
• 結(jié)論79-80
• 致謝80-81
• 參考文獻(xiàn)81-84
• 攻讀學(xué)位期間的研究成果84

【參考文獻(xiàn)】

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

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

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

3 李敬文;張?jiān)坪?陳志鵬;孫亮;;圖的點(diǎn)可區(qū)別邊染色算法研究[J];計(jì)算機(jī)應(yīng)用研究;2014年03期

4 馮珊珊;張?jiān)虑?郭旭敏;;基于改進(jìn)圖著色理論的聚類算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2013年05期

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1061167