本文關(guān)鍵詞：圖的若干不完備可區(qū)別染色算法研究

  更多相關(guān)文章： 不完備可區(qū)別染色 鄰點(diǎn)可區(qū)別E-全染色 鄰點(diǎn)可區(qū)別V-全染色 鄰點(diǎn)可區(qū)別I-全染色 鄰點(diǎn)可區(qū)別VI-全染色

【摘要】：本學(xué)位論文主要考慮圖的不完備可區(qū)別染色問題。圖染色是圖論中一個(gè)非常重要的研究方向,在實(shí)際問題中有著很好的應(yīng)用,排課表問題、任務(wù)分配問題、集成電路布線等都可以從圖染色的角度來解決�？梢哉f,圖染色為一些實(shí)際問題的解決提供了一種新的思路和方法。由于實(shí)際問題的復(fù)雜性,單一的點(diǎn)染色或者邊染色并不能完全滿足問題的要求,研究者們便提出了各種各樣的染色問題,如點(diǎn)(鄰點(diǎn))可區(qū)別染色、均勻染色、可約染色等,并得到了很多有價(jià)值的理論成果,而不完備可區(qū)別染色便是由于實(shí)際問題的需要,在正�？蓞^(qū)別染色基礎(chǔ)上的弱化。由于圖的染色問題是一個(gè)NP-完全問題,目前解決圖染色問題的算法主要依賴于智能算法,但只限于解決特殊圖的點(diǎn)染色或者邊染色,不能解決全染色和可區(qū)別染色問題,而現(xiàn)實(shí)中的很多問題所轉(zhuǎn)化的圖都具有一定的隨機(jī)性,所以尋求針對任意一個(gè)圖的高效的染色算法已成為圖論研究者的一個(gè)重要的課題。對于不完備可區(qū)別染色,已發(fā)表的文獻(xiàn)中雖然得到了一些理論成果,卻沒有可行的染色算法,而算法的實(shí)現(xiàn)對相關(guān)問題的研究具有較高的實(shí)際意義。所以,本文根據(jù)不完備可區(qū)別染色的染色要求,設(shè)計(jì)出了針對任意一個(gè)簡單連通圖的染色算法,通過大量的測試分析,算法具有較高的染色效率。本文的工作如下:(1)介紹了與本文有關(guān)的一些基本染色概念及猜想,同時(shí)給出本文有關(guān)內(nèi)容的研究背景、國內(nèi)外研究動(dòng)態(tài)等。(2)介紹了粒子群算法、遺傳算法的基本思想、流程,及其在圖染色中的應(yīng)用,并對這些算法在解決圖染色問題的性能上進(jìn)行了分析。(3)針對任意簡單連通圖設(shè)計(jì)了四種不完備鄰點(diǎn)可區(qū)別全染色算法,包括一種基于正常點(diǎn)染色的鄰點(diǎn)可區(qū)別E-全染色算法,和三種基于正常邊染色的算法,分別為鄰點(diǎn)可區(qū)別V-全染色算法、鄰點(diǎn)可區(qū)別I-全染色算法和鄰點(diǎn)可區(qū)別VI-全染色算法。前者采用先頂點(diǎn)染色再邊染色的方法,而后者采用先邊染色再頂點(diǎn)染色的方法。其中,算法中設(shè)計(jì)的邊染色方法,可以解決任意一個(gè)圖的正常邊染色問題,而且根據(jù)染色條件的變化還可以解決其它基于正常邊染色的全染色或可區(qū)別染色問題。文中給出了算法的詳細(xì)流程及測試,并對算法的正確性、收斂性和時(shí)間復(fù)雜度進(jìn)行了分析,最后對算法做了總結(jié)。
【關(guān)鍵詞】：不完備可區(qū)別染色 鄰點(diǎn)可區(qū)別E-全染色 鄰點(diǎn)可區(qū)別V-全染色 鄰點(diǎn)可區(qū)別I-全染色 鄰點(diǎn)可區(qū)別VI-全染色
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-9
• 1 緒論9-12
• 1.1 引言9
• 1.2 研究背景9-10
• 1.3 本文的研究內(nèi)容及組織10-12
• 2 經(jīng)典優(yōu)化算法在圖染色中的應(yīng)用12-20
• 2.1 引言12
• 2.2 圖染色相關(guān)定義及猜想12-14
• 2.3 粒子群算法在圖染色中的應(yīng)用14-17
• 2.3.1 粒子群算法的基本思想14-16
• 2.3.2 粒子群算法在圖染色中的應(yīng)用16-17
• 2.3.3 粒子群算法總結(jié)17
• 2.4 遺傳算法在圖染色中的應(yīng)用17-19
• 2.5 本章小結(jié)19-20
• 3 圖的鄰點(diǎn)可區(qū)別E-全染色算法20-31
• 3.1 引言20
• 3.2 鄰點(diǎn)可區(qū)別E-全染色算法設(shè)計(jì)20-25
• 3.2.1 約束函數(shù)設(shè)計(jì)20-21
• 3.2.2 算法步驟及流程圖21-25
• 3.3 算法測試25-28
• 3.4 算法分析28-29
• 3.5 算法總結(jié)29-31
• 4 圖的鄰點(diǎn)可區(qū)別V-，I-，，VI-全染色算法31-57
• 4.1 引言31
• 4.2 鄰點(diǎn)可區(qū)別V-全染色算法設(shè)計(jì)31-39
• 4.2.1 約束函數(shù)設(shè)計(jì)31-32
• 4.2.2 算法步驟及流程圖32-36
• 4.2.3 算法測試36-39
• 4.3 鄰點(diǎn)可區(qū)別I-全染色算法設(shè)計(jì)39-46
• 4.3.1 約束函數(shù)設(shè)計(jì)40-41
• 4.3.2 算法描述及流程圖41-43
• 4.3.3 算法測試43-46
• 4.4 鄰點(diǎn)可區(qū)別VI-全染色算法設(shè)計(jì)46-54
• 4.4.1 約束函數(shù)設(shè)計(jì)46-47
• 4.4.2 算法描述及流程圖47-48
• 4.4.3 算法測試48-54
• 4.5 算法分析54-56
• 4.6 算法總結(jié)56-57
• 結(jié)論57-59
• 致謝59-60
• 參考文獻(xiàn)60-63
• 攻讀學(xué)位期間的研究成果及參加的科研項(xiàng)目63

【共引文獻(xiàn)】

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

1 王濤;趙宜賓;李德明;;路與路聯(lián)圖的鄰強(qiáng)邊染色和均勻鄰強(qiáng)邊染色(英文)[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年01期

2 朱恩強(qiáng);呂新忠;張玉紅;;關(guān)于C_m·C_n,C_m·S_n和C_m·K_n的鄰點(diǎn)可區(qū)別全色數(shù)[J];江西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年04期

3 李宜義;張衛(wèi)平;;圖染色思想在庫存管理中的一種應(yīng)用研究[J];電腦知識(shí)與技術(shù);2011年26期

4 強(qiáng)會(huì)英;張忠輔;;部分圖笛卡兒積圖的鄰點(diǎn)可區(qū)別VE-全染色[J];蘭州理工大學(xué)學(xué)報(bào);2009年05期

5 WOODALL Douglas R;;Adjacent strong edge colorings and total colorings of regular graphs[J];Science in China(Series A:Mathematics);2009年05期

6 辛小青;王治文;陳祥恩;姚兵;;點(diǎn)不交的m個(gè)C_3的并的點(diǎn)可區(qū)別全染色[J];吉林大學(xué)學(xué)報(bào)(理學(xué)版);2012年02期

7 孔令峰;蘇文龍;羅海鵬;黎貞崇;何建東;;圖P_(u,v)(n)的鄰強(qiáng)邊染色[J];計(jì)算機(jī)應(yīng)用研究;2008年06期

8 強(qiáng)會(huì)英;張忠輔;;一些聯(lián)圖的鄰點(diǎn)可區(qū)別-邊全染色[J];蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年06期

9 強(qiáng)會(huì)英;張忠輔;;若干圖廣義Mycielski圖的點(diǎn)邊鄰點(diǎn)可區(qū)別的全染色[J];蘭州交通大學(xué)學(xué)報(bào);2008年06期

10 王鴻杰;王治文;朱恩強(qiáng);文飛;;關(guān)于C_m×K_n的鄰點(diǎn)可區(qū)別全色數(shù)[J];蘭州交通大學(xué)學(xué)報(bào);2010年01期

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

1 劉彬;圖的點(diǎn)可區(qū)別染色、列表染色和線性染色[D];山東大學(xué);2010年

2 胡小蘭;極值和染色問題的一些新結(jié)果[D];南京大學(xué);2015年

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

1 文飛;若干圖類的Smarandachely鄰點(diǎn)全染色[D];蘭州交通大學(xué);2011年

2 孫婷婷;圖的點(diǎn)可區(qū)別的邊染色及點(diǎn)可區(qū)別的全染色[D];重慶大學(xué);2008年

3 周薇;若干圖的關(guān)聯(lián)著色與鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色研究[D];山東科技大學(xué);2009年

4 張琛;關(guān)于圖的鄰點(diǎn)可區(qū)別全染色的一些結(jié)果[D];西北師范大學(xué);2008年

5 張義瑛;平面圖鄰接點(diǎn)區(qū)分邊染色的一個(gè)結(jié)果[D];南京師范大學(xué);2013年

6 嚴(yán)丞超;平面圖的鄰點(diǎn)可區(qū)別邊染色[D];浙江師范大學(xué);2013年

7 薛國梁;字典積圖及其Mycielski圖的鄰點(diǎn)可區(qū)別的邊染色與全染色[D];西北民族大學(xué);2013年

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

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

10 楊超;關(guān)于具有一個(gè)或多個(gè)可區(qū)分約束條件的圖著色研究[D];西北師范大學(xué);2014年

本文編號(hào)：712246