本文選題：生成樹 + 生成圖　； 參考：《蘭州交通大學(xué)》2017年碩士論文

【摘要】：圖論中的一個經(jīng)典難題——圖染色問題,屬于圖論的一個分支,也是科學(xué)計算與工程設(shè)計中的基本問題�，F(xiàn)實世界中有很多問題都可以轉(zhuǎn)化為圖的問題來解決,例如比賽安排問題、網(wǎng)絡(luò)通信問題、排課表問題、物資存儲問題、無線通訊頻道分配,印刷電路板設(shè)計及變址寄存器數(shù)目分配等等,這些問題的解決都涉及到圖的染色理論,所以染色問題是圖論中極具研究意義的領(lǐng)域之一。隨著現(xiàn)實世界中交通運輸、計算機網(wǎng)絡(luò)通信、軍事、生產(chǎn)管理等實際問題需求的發(fā)展,以及經(jīng)典智能優(yōu)化算法所存在的不足以及局限性的演變,我們對快速而準確地實現(xiàn)染色結(jié)果并將其應(yīng)用于實際的需求也逐步增大。圖的強可區(qū)別染色問題是一種多條件約束染色,是在可區(qū)別全染色的基礎(chǔ)之上再增加約束條件,使得色集合的包含元素更多,共包括兩種染色概念:鄰點強可區(qū)別全染色、點強可區(qū)別全染色。目前在已公開發(fā)表的文獻中對強可區(qū)別全染色的研究僅局限于圈圖、輪圖、完全圖、樹等特殊圖,而對于一般隨機圖的強可區(qū)別染色研究尚無可行的解決方法。本文結(jié)合多目標(biāo)優(yōu)化的研究思想,設(shè)計了基于多目標(biāo)優(yōu)化的強可區(qū)別染色算法,算法通過設(shè)定多個子目標(biāo)函數(shù)逐步尋優(yōu),使其最終的目標(biāo)函數(shù)得到Pareto最優(yōu)解,實現(xiàn)局部最優(yōu)化到整體最優(yōu)化的過程。同時文中還設(shè)計實現(xiàn)了有限點以內(nèi)所有生成樹算法以及所有簡單連通圖生成算法,為各類染色算法的研究及結(jié)果集測試奠定基礎(chǔ)。本文的主要工作如下:(1)介紹了圖論以及圖染色理論的基本概念、多目標(biāo)優(yōu)化問題的相關(guān)概念、遺傳算法的基本思想以及應(yīng)用于解決正常邊染色的算法執(zhí)行過程,同時對其優(yōu)缺點進行分析總結(jié)。(2)給出了兩類隨機圖生成算法,第一類是輸入頂點數(shù)目依照規(guī)則隨機連邊生成隨機簡單連通圖算法;第二類是基于生成樹生成有限點數(shù)內(nèi)所有偽非同構(gòu)圖算法,因此第二類算法又包含了生成樹算法;兩種隨機圖生成算法為后續(xù)一系列染色算法的結(jié)果集測試、統(tǒng)計以及相關(guān)引理、猜想的證明提供基礎(chǔ)研究數(shù)據(jù),為各種染色算法的研究奠定良好的基礎(chǔ)。(3)設(shè)計并實現(xiàn)了基于多目標(biāo)優(yōu)化的圖的鄰點強可區(qū)別全染色算法、基于多目標(biāo)優(yōu)化的圖的點強可區(qū)別全染色算法,同時設(shè)計了兩類正常邊染色算法、頂點染色算法、色集合調(diào)整算法等一系列子算法。強可區(qū)別全染色算法的最終目的是要確保頂點的色集合不同,色集合除了頂點顏色,頂點與其關(guān)聯(lián)邊顏色之外還加入了相鄰頂點的顏色,所以色集合調(diào)整的難度變得更大。所以本文設(shè)計了更詳細的的強色集調(diào)整規(guī)則,以及相應(yīng)的過程評估函數(shù)來及時生成新的預(yù)染色組,從而更快速地搜索到最優(yōu)解,在不提高算法時間復(fù)雜度的情況下,提高算法的運行效率。(4)測試結(jié)果集為7個點以內(nèi)所有的偽非同構(gòu)圖,15個頂點以內(nèi)的特殊圖、14個頂點以內(nèi)的所有生成樹以及1000個點以內(nèi)部分隨機連通圖;并通過大量實驗結(jié)果集的分析,給出了若干有意義的結(jié)論及猜想。
[Abstract]:A classic problem in graph theory, graph dyeing problem, belongs to a branch of graph theory, and it is also a basic problem in scientific computing and engineering design. There are many problems in the real world that can be transformed into graphs, such as competition arrangement, network communication, scheduling, material storage, and wireless communication channels. Distribution, printed circuit board design and the number allocation of variable address registers and so on. The solution of these problems involves the theory of graph dyeing, so the problem of dyeing is one of the most important fields in the graph theory. With the real world traffic, computer network communication, military, production management and other practical problems, and the classic The shortcomings of the intelligent optimization algorithm and the evolution of its limitations, we have gradually increased the demand for fast and accurate implementation of the dyeing results and applied it to actual conditions. There are more elements, including two kinds of coloring concepts: strong distinguishable full coloring from adjacent points, and strong distinguishable total coloring. In the published literature, the study of strongly distinguishable total coloring is limited to special graphs, such as circle graph, wheel diagram, complete graph, tree and so on, but there is no feasible solution for the strong distinguishable dyeing of general random graphs. In this paper, based on the research idea of multi-objective optimization, a strong distinguishable dyeing algorithm based on multi-objective optimization is designed. The algorithm is optimized by setting multiple sub objective functions, and the final objective function is obtained by Pareto optimal solution to achieve the path of local optimization to the overall optimization. The main work of this paper is as follows: (1) the basic concepts of graph theory and graph coloring theory, the related concepts of multi-objective optimization problem, the basic idea of the relic algorithm and the application to solve the normal dyeing are introduced. The advantages and disadvantages of color algorithm are analyzed and analyzed. (2) two classes of random graph generation algorithms are given. The first class is the number of the input vertices to generate random simple connected graphs in accordance with regular random edges; the second class is based on the generation tree to generate the pseudo non isomorphic graph algorithm in the finite number of points, so the second kind of algorithm also contains the algorithm. The algorithm of spanning tree is used. Two random graph generation algorithms are tested for the result set of a series of successive dyeing algorithms, statistics and related lemma, and the proof of conjecture provides basic research data, which lays a good foundation for the study of all kinds of dyeing algorithms. (3) design and implement a strong distinguishable full coloring algorithm based on multi-objective optimization. At the same time, a series of sub algorithms, such as two normal edge coloring algorithms, vertex coloring algorithms and color set adjustment algorithms, are designed based on the multi-objective optimization. The final purpose of the strong distinguishable total coloring algorithm is to ensure that the color set of the vertex is different, the color set is the vertex color, the vertex and its associated edge. In addition to the color of adjacent vertices, it is more difficult to adjust the color set, so this paper designs a more detailed rule of the strong color set adjustment, and the corresponding process evaluation function to generate a new pre dyed group in time, so that the optimal solution can be searched more quickly, without improving the time complexity of the algorithm. The running efficiency of the high algorithm. (4) the test result set is all the pseudo non isomorphic graphs within 7 points, the special graphs within 15 vertices, all the spanning trees within the 14 vertices and the partial random connected graphs within 1000 points, and some meaningful conclusions and conjectures are given through the analysis of a large number of experimental results set.

【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18;O157.5

【參考文獻】

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

1 強會英;王洪申;;圖的鄰點強可區(qū)別全色數(shù)的一個上界[J];數(shù)學(xué)進展;2013年06期

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

3 趙煥平;;圈圖的點可區(qū)別強全染色算法[J];計算機與現(xiàn)代化;2013年09期

4 Jing-wen LI;Cong WANG;Zhi-wen WANG;;On the Adjacent Vertex-distinguishing Equitable Edge Coloring of Graphs[J];Acta Mathematicae Applicatae Sinica(English Series);2013年03期

5 陳祥恩;王治文;趙飛虎;魏甲靜;姚兵;;若干強積圖及合成圖的鄰點可區(qū)別一般邊染色[J];山東大學(xué)學(xué)報(理學(xué)版);2013年06期

6 趙煥平;李冬梅;李敬文;;一種應(yīng)用于完全圖的點可區(qū)別強全染色新算法[J];計算機應(yīng)用與軟件;2013年03期

7 陸尚輝;;圖的鄰點強可區(qū)別全色數(shù)的新上界[J];中央民族大學(xué)學(xué)報(自然科學(xué)版);2013年01期

8 盧建立;任鳳霞;馬美琳;;中間圖的鄰點強可區(qū)別全染色[J];河南師范大學(xué)學(xué)報(自然科學(xué)版);2012年05期

9 趙煥平;劉平;李敬文;;完全圖的點可區(qū)別強全染色算法[J];計算機工程;2012年17期

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

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

1 魏靜萱;解決單目標(biāo)和多目標(biāo)優(yōu)化問題的進化算法[D];西安電子科技大學(xué);2009年

2 霍紅衛(wèi);遺傳算法在圖論和優(yōu)化中的應(yīng)用[D];西安電子科技大學(xué);2000年

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

1 胡騰云;隨機圖的D（β）染色算法研究[D];蘭州交通大學(xué);2016年

2 尹波;隨機圖的色和可區(qū)別染色算法研究[D];蘭州交通大學(xué);2016年

3 代素敏;隨機圖的均勻染色算法研究[D];蘭州交通大學(xué);2016年

4 董威;隨機有向圖的染色算法研究[D];蘭州交通大學(xué);2015年

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

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

7 胡志濤;圖的點強可區(qū)別全染色的研究[D];西北師范大學(xué);2013年

8 趙煥平;若干圖的點可區(qū)別強全染色的算法研究[D];蘭州交通大學(xué);2009年

9 王魯;基于遺傳算法的多目標(biāo)優(yōu)化算法研究[D];武漢理工大學(xué);2006年

10 杜慧江;基于子樹生成的堆枚舉算法[D];華東師范大學(xué);2006年

，

本文編號：1892343