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

【摘要】：現(xiàn)實生活中有很多實際問題是將某種對象的集合按照一定的規(guī)則進行分類的,而圖染色問題恰好是按照某種規(guī)則對圖中的頂點、邊等元素進行分類的,所以很多實際問題都可以抽象成圖,并利用圖染色的方法解決。圖染色問題是圖論研究領(lǐng)域的主要方向,國內(nèi)外的專家學者們已經(jīng)做了大量的研究工作來尋求解決各種染色問題的具體方法。常見的有經(jīng)典的智能算法,如遺傳算法、模擬退火算法等。對于較小規(guī)模的圖來說,使用這些算法來解決圖染色問題時可以得到最優(yōu)解或次優(yōu)解。但是當要求解的圖的規(guī)模增大時,算法的時間復(fù)雜度及算法的效率都會受到很大影響。另外,這些算法只能用來解決點染色、邊染色這2個基本的染色問題,對于本文要研究的染色條件稍微復(fù)雜的可約染色,這些算法是解決不了的,所以需要尋求新的算法來解決。對于圖的可約染色問題,在已公開發(fā)表的文獻中只是給出了相關(guān)的定義,或是針對特殊圖如星扇輪等給出了一些有用的結(jié)論,具體解決問題的方法目前還沒有。所以本文針對隨機圖(無向簡單連通圖)的點可約邊染色、點可約全染色、鄰點可約邊染色、鄰點可約全染色4個問題,提出了相應(yīng)的解決方案。本文的主要研究工作有以下幾個方面。(1)介紹了圖論及圖染色的發(fā)展過程,給出了本文的研究目的及意義。(2)介紹了經(jīng)典的智能算法在圖染色中的應(yīng)用,分析了這些算法的優(yōu)點及不足。(3)針對隨機圖,設(shè)計了4個啟發(fā)式多目標優(yōu)化算法,分別實現(xiàn)了點可約邊染色、點可約全染色、鄰點可約邊染色、鄰點可約全染色問題。對于點可約染色,其基本思想是將目標問題分解成幾個子問題,設(shè)計相應(yīng)的子約束函數(shù),然后根據(jù)這些子約束函數(shù)進行迭代調(diào)整,逐步解決每個子問題,最終使得圖中度數(shù)相同的所有頂點其色集合相同,此時總目標函數(shù)的值為0,染色成功,算法結(jié)束。相比點可約染色,鄰點可約染色算法的基本思想是通過逐步迭代調(diào)整使得圖中度數(shù)相同且相鄰的頂點其色集合相同。文中首先對算法都進行了詳細的描述;其次分別對4個算法進行了測試,同時也給出了部分實驗的結(jié)果;再次從正確性、收斂性(單調(diào)性、有界性)以及時間復(fù)雜度3個方面對算法進行了詳細分析,得到算法的時間復(fù)雜度為O(n3);最后對4個算法進行了總結(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.
【學位授予單位】：蘭州交通大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5

【相似文獻】

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

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

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

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

4 譚利;侯振挺;;一類無標度隨機圖的度序列[J];應(yīng)用數(shù)學學報;2011年03期

5 王漢興;馬馳;;一類隨機圖的演化(英文)[J];運籌學學報;2006年01期

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

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

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

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

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

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

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

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

1 顏云志;有向無標度圖與二項隨機圖圖因子[D];上海大學;2007年

2 尚軼倫;隨機圖及對個體系統(tǒng)的一致性問題[D];上海交通大學;2010年

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

4 于娜;獨立馬氏鏈邊隨機圖過程與隨機分枝樹研究[D];上海大學;2012年

5 郇瀟;圖中匹配的可擴性研究[D];南開大學;2010年

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

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

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

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

4 賀國卿;隨機圖上頂點度數(shù)序列及樹分圖的分布[D];天津大學;2010年

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

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

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

8 劉紅;稀疏隨機圖中孤立點的個數(shù)的偏差不等式與中偏差[D];武漢大學;2005年

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

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

，

本文編號：1459324