本文關(guān)鍵詞： 隨機(jī)圖 圖染色 點(diǎn)可約染色 鄰點(diǎn)可約染色　出處：《蘭州交通大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

【摘要】：現(xiàn)實(shí)生活中有很多實(shí)際問(wèn)題是將某種對(duì)象的集合按照一定的規(guī)則進(jìn)行分類的,而圖染色問(wèn)題恰好是按照某種規(guī)則對(duì)圖中的頂點(diǎn)、邊等元素進(jìn)行分類的,所以很多實(shí)際問(wèn)題都可以抽象成圖,并利用圖染色的方法解決。圖染色問(wèn)題是圖論研究領(lǐng)域的主要方向,國(guó)內(nèi)外的專家學(xué)者們已經(jīng)做了大量的研究工作來(lái)尋求解決各種染色問(wèn)題的具體方法。常見的有經(jīng)典的智能算法,如遺傳算法、模擬退火算法等。對(duì)于較小規(guī)模的圖來(lái)說(shuō),使用這些算法來(lái)解決圖染色問(wèn)題時(shí)可以得到最優(yōu)解或次優(yōu)解。但是當(dāng)要求解的圖的規(guī)模增大時(shí),算法的時(shí)間復(fù)雜度及算法的效率都會(huì)受到很大影響。另外,這些算法只能用來(lái)解決點(diǎn)染色、邊染色這2個(gè)基本的染色問(wèn)題,對(duì)于本文要研究的染色條件稍微復(fù)雜的可約染色,這些算法是解決不了的,所以需要尋求新的算法來(lái)解決。對(duì)于圖的可約染色問(wèn)題,在已公開發(fā)表的文獻(xiàn)中只是給出了相關(guān)的定義,或是針對(duì)特殊圖如星扇輪等給出了一些有用的結(jié)論,具體解決問(wèn)題的方法目前還沒有。所以本文針對(duì)隨機(jī)圖(無(wú)向簡(jiǎn)單連通圖)的點(diǎn)可約邊染色、點(diǎn)可約全染色、鄰點(diǎn)可約邊染色、鄰點(diǎn)可約全染色4個(gè)問(wèn)題,提出了相應(yīng)的解決方案。本文的主要研究工作有以下幾個(gè)方面。(1)介紹了圖論及圖染色的發(fā)展過(guò)程,給出了本文的研究目的及意義。(2)介紹了經(jīng)典的智能算法在圖染色中的應(yīng)用,分析了這些算法的優(yōu)點(diǎn)及不足。(3)針對(duì)隨機(jī)圖,設(shè)計(jì)了4個(gè)啟發(fā)式多目標(biāo)優(yōu)化算法,分別實(shí)現(xiàn)了點(diǎn)可約邊染色、點(diǎn)可約全染色、鄰點(diǎn)可約邊染色、鄰點(diǎn)可約全染色問(wèn)題。對(duì)于點(diǎn)可約染色,其基本思想是將目標(biāo)問(wèn)題分解成幾個(gè)子問(wèn)題,設(shè)計(jì)相應(yīng)的子約束函數(shù),然后根據(jù)這些子約束函數(shù)進(jìn)行迭代調(diào)整,逐步解決每個(gè)子問(wèn)題,最終使得圖中度數(shù)相同的所有頂點(diǎn)其色集合相同,此時(shí)總目標(biāo)函數(shù)的值為0,染色成功,算法結(jié)束。相比點(diǎn)可約染色,鄰點(diǎn)可約染色算法的基本思想是通過(guò)逐步迭代調(diào)整使得圖中度數(shù)相同且相鄰的頂點(diǎn)其色集合相同。文中首先對(duì)算法都進(jìn)行了詳細(xì)的描述;其次分別對(duì)4個(gè)算法進(jìn)行了測(cè)試,同時(shí)也給出了部分實(shí)驗(yàn)的結(jié)果;再次從正確性、收斂性(單調(diào)性、有界性)以及時(shí)間復(fù)雜度3個(gè)方面對(duì)算法進(jìn)行了詳細(xì)分析,得到算法的時(shí)間復(fù)雜度為O(n3);最后對(duì)4個(gè)算法進(jìn)行了總結(jié)。
[Abstract]:In real life, there are many practical problems in classifying the set of certain objects according to certain rules, while the problem of graph coloring happens to classify the vertex and edge elements in a graph according to some rules. So many practical problems can be abstracted and solved by the method of graph coloring, which is the main direction of graph theory research. Experts and scholars at home and abroad have done a lot of research to find specific solutions to various dyeing problems. Classical intelligent algorithms such as genetic algorithms are common. For smaller graphs, the optimal solution or suboptimal solution can be obtained by using these algorithms to solve the graph coloring problem. However, when the size of the graph required for the solution increases. The time complexity and efficiency of the algorithm will be greatly affected. In addition, these algorithms can only be used to solve the two basic coloring problems: point coloring and edge coloring. For the reducible coloring with slightly complicated coloring conditions, these algorithms cannot be solved, so we need to find new algorithms to solve the problem of reducible coloring of graphs. In the published literature, only the relevant definitions are given, or some useful conclusions are given for special graphs such as star fan wheels. At present, there are no specific solutions to the problem, so this paper deals with four problems: vertex reducible edge coloring, vertex reducible total coloring, adjacent point reducible edge coloring and adjacent point reducible total coloring for random graphs (undirected simple connected graphs). The main research work in this paper is as follows: (1) the development process of graph theory and graph coloring is introduced. The purpose and significance of this paper are given. (2) the application of classical intelligent algorithms in graph coloring is introduced, and the advantages and disadvantages of these algorithms are analyzed. Four heuristic multi-objective optimization algorithms are designed to realize the problem of point-reducible edge coloring, point-reducible total coloring, adjacent point-reducible edge coloring and adjacent point-reducible total coloring respectively. The basic idea is to decompose the objective problem into several sub-problems, design the corresponding sub-constraint functions, and then iteratively adjust them according to these sub-constraint functions to solve each sub-problem step by step. Finally, all the vertices with the same degree in the graph have the same chromatic set, the total objective function is 0, the coloring is successful, and the algorithm ends. The basic idea of the adjacent point reducible coloring algorithm is to adjust the degree of the graph to the same degree and the adjacent vertices to the same chromatic set by iterating step by step. Firstly, the algorithm is described in detail. Secondly, four algorithms are tested, and some experimental results are given. Thirdly, the algorithm is analyzed in detail from three aspects: correctness, convergence (monotonicity, boundedness) and time complexity. Finally, four algorithms are summarized.
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 林妤;許道云;;隨機(jī)圖G(2n,p)中k-匹配的相變性質(zhì)[J];貴州大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年01期

2 黃斌;吳春旺;鄭豐華;藺冰;;復(fù)雜網(wǎng)絡(luò)中隨機(jī)圖模型研究[J];計(jì)算機(jī)工程與科學(xué);2014年07期

3 王冰杰;;隨機(jī)圖在信息傳遞系統(tǒng)中的應(yīng)用[J];吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年04期

4 譚利;侯振挺;;一類無(wú)標(biāo)度隨機(jī)圖的度序列[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2011年03期

5 王漢興;馬馳;;一類隨機(jī)圖的演化(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2006年01期

6 陳志;范益政;杜文學(xué);;隨機(jī)圖的譜矩(英文)[J];應(yīng)用數(shù)學(xué);2011年04期

7 李木梓;徐柱;李志林;張紅;怓鵬;;基于層次隨機(jī)圖的道路選取方法[J];地球信息科學(xué)學(xué)報(bào);2012年06期

8 馬文麒,馬文麒,楊俊忠,胡崗;耦合映象格子凍結(jié)化隨機(jī)圖樣模式的動(dòng)力學(xué)特征(英文)[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1999年01期

9 郭子政;崔彥;吳曉薇;趙保利;;具有冪率度分布的隨機(jī)圖上的幸存者統(tǒng)計(jì)和平均位損傷[J];內(nèi)蒙古師范大學(xué)學(xué)報(bào)(自然科學(xué)漢文版);2008年04期

10 蔣輝;;頂點(diǎn)著色隨機(jī)圖邊數(shù)的中偏差[J];數(shù)學(xué)雜志;2008年01期

相關(guān)會(huì)議論文 前1條

1 萬(wàn)超崗;趙杰煜;張媛媛;;基于隨機(jī)圖的情感產(chǎn)生模型[A];第十四屆全國(guó)圖象圖形學(xué)學(xué)術(shù)會(huì)議論文集[C];2008年

相關(guān)博士學(xué)位論文 前5條

1 顏云志;有向無(wú)標(biāo)度圖與二項(xiàng)隨機(jī)圖圖因子[D];上海大學(xué);2007年

2 尚軼倫;隨機(jī)圖及對(duì)個(gè)體系統(tǒng)的一致性問(wèn)題[D];上海交通大學(xué);2010年

3 丁雪;隨機(jī)圖中若干矩陣的譜性質(zhì)[D];吉林大學(xué);2010年

4 于娜;獨(dú)立馬氏鏈邊隨機(jī)圖過(guò)程與隨機(jī)分枝樹研究[D];上海大學(xué);2012年

5 郇瀟;圖中匹配的可擴(kuò)性研究[D];南開大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 劉亮;基于指數(shù)隨機(jī)圖的社會(huì)網(wǎng)絡(luò)構(gòu)建關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

2 李小慧;隨機(jī)圖的可約染色算法研究[D];蘭州交通大學(xué);2015年

3 田甜;基于層次隨機(jī)圖模型的復(fù)雜腦網(wǎng)絡(luò)鏈路預(yù)測(cè)研究[D];太原理工大學(xué);2015年

4 賀國(guó)卿;隨機(jī)圖上頂點(diǎn)度數(shù)序列及樹分圖的分布[D];天津大學(xué);2010年

5 畢偉;具有隨機(jī)頂點(diǎn)權(quán)重的廣義隨機(jī)圖的極限定理[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

6 陳志;隨機(jī)圖的譜矩和Estrada指數(shù)[D];安徽大學(xué);2012年

7 鄭萬(wàn)吉;利用溫度序列隨機(jī)圖的演化探究全球變暖的影響[D];上海交通大學(xué);2011年

8 劉紅;稀疏隨機(jī)圖中孤立點(diǎn)的個(gè)數(shù)的偏差不等式與中偏差[D];武漢大學(xué);2005年

9 趙文飛;Ramsey理論中的構(gòu)造與隨機(jī)圖方法[D];國(guó)防科學(xué)技術(shù)大學(xué);2010年

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

，

本文編號(hào)：1459324