【摘要】：現(xiàn)實(shí)生活中許多復(fù)雜的問題都可通過分類、抽象、簡(jiǎn)化的思想轉(zhuǎn)化成圖論問題進(jìn)行研究解決,如最大支配集、加工調(diào)度、任務(wù)分配、排課表等典型的組合類問題,而圖染色作為圖論中一個(gè)重要的研究分支,是解決實(shí)際問題的一個(gè)重要途徑。近些年來,一些經(jīng)典的智能算法被用來研究和嘗試解決圖染色問題,如粒子群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法等,但目前這些算法普遍僅應(yīng)用于解決圖的正常點(diǎn)染色和正常邊染色,而對(duì)于圖染色問題中多約束條件的染色問題,公開發(fā)表的文獻(xiàn)中尚不多見,因此尋求新的智能算法來解決圖的多約束條件染色問題是國內(nèi)外圖論研究者都感興趣的一個(gè)重要課題。圖的鄰點(diǎn)色和可區(qū)別染色問題,在已公開發(fā)表的文獻(xiàn)中對(duì)它們的研究都局限于如正則圖、星圖、完全圖等的特殊圖,尚無解決一般圖的鄰點(diǎn)色和可區(qū)別染色、點(diǎn)和可區(qū)別染色問題的方法。本文根據(jù)兩種圖的色和可區(qū)別染色的定義,分別設(shè)計(jì)了基于多目標(biāo)優(yōu)化的染色算法,對(duì)算法的正確性、收斂性和復(fù)雜度進(jìn)行了分析,并通過大量的實(shí)例測(cè)試,得到了一些很有意義的結(jié)果。本文的具體工作如下:⑴介紹了一些基本染色概念及相關(guān)猜想,并同時(shí)給出有關(guān)內(nèi)容的研究背景及目前國內(nèi)外的研究動(dòng)態(tài)。⑵介紹了兩個(gè)經(jīng)典的智能算法(粒子群算法、遺傳算法)的基本思想、流程,及其在圖染色中的應(yīng)用,并對(duì)這些算法在解決圖染色問題的性能上進(jìn)行了分析。⑶給出了隨機(jī)圖的生成算法和生成有限點(diǎn)數(shù)所有偽非同構(gòu)圖的算法,詳細(xì)描述了算法步驟,并分別對(duì)這兩種算法進(jìn)行了算法測(cè)試,為之后染色算法的研究提供了基礎(chǔ)數(shù)據(jù)支持。⑷設(shè)計(jì)并實(shí)現(xiàn)了圖的色和可區(qū)別染色問題中的鄰點(diǎn)和可區(qū)別邊染色、鄰點(diǎn)和可區(qū)別全染色、點(diǎn)和可區(qū)別邊染色和點(diǎn)和可區(qū)別全染色四個(gè)智能優(yōu)化算法。四個(gè)算法的整體思路都是將其染色問題分解為多個(gè)特定功能模塊的子問題,依次按序通過對(duì)子問題的逐步迭代調(diào)整直到子問題解決成功,之后以不改變前一子問題的成功狀態(tài)為前提解決后一個(gè)子問題,當(dāng)所有子問題都成功解決后,即代表該染色成功,算法結(jié)束。文中給出了算法的詳細(xì)流程及測(cè)試案例,分析了算法的正確性、收斂性和時(shí)間復(fù)雜度,測(cè)試實(shí)例為7個(gè)點(diǎn)以內(nèi)所有偽非同構(gòu)圖和1000個(gè)點(diǎn)以內(nèi)邊密度較小的1萬個(gè)隨機(jī)連通圖,通過對(duì)實(shí)驗(yàn)結(jié)果的分析,表明算法具有較好的執(zhí)行效率和不算高的時(shí)間復(fù)雜度,同時(shí)給出了若干有意義的經(jīng)過驗(yàn)證的結(jié)論。
[Abstract]:In real life, many complex problems can be solved through classification, abstraction and simplification of ideas into graph theory problems, such as maximal dominating set, processing scheduling, task assignment, scheduling and other typical combinatorial class problems. As an important branch of graph theory, graph coloring is an important way to solve practical problems. In recent years, some classical intelligent algorithms have been used to study and try to solve graph coloring problems, such as particle swarm optimization algorithm, genetic algorithm, neural network algorithm and so on. However, these algorithms are generally only used to solve the problem of normal point coloring and normal edge coloring of graphs. However, there are few published literatures on the problem of multi-constraint coloring in graph coloring problems. Therefore, finding a new intelligent algorithm to solve the multi-constraint coloring problem of graphs is an important topic of interest to graph theorists both at home and abroad. The problems of adjacent vertex coloring and discernible coloring of graphs are confined to the special graphs such as regular graphs, star graphs, complete graphs, etc. In the published literatures, there is no solution to the adjacent coloring and distinguishing coloring of general graphs. The method of point and distinguishing coloring problem. According to the definition of color and distinguishing coloring of two kinds of graphs, this paper designs a coloring algorithm based on multi-objective optimization, and analyzes the correctness, convergence and complexity of the algorithm. Some meaningful results have been obtained. The specific work of this paper is as follows: 1. Some basic coloring concepts and related conjectures are introduced, and the research background and current research trends at home and abroad are also given. 2 two classical intelligent algorithms (particle swarm optimization algorithm) are introduced. The basic idea, flow, and application of genetic algorithm in graph coloring, The performance of these algorithms in solving the problem of graph coloring is analyzed. 3 the generating algorithm of random graph and the algorithm of generating all pseudo-nonisomorphic graphs with finite number of points are given, and the steps of the algorithm are described in detail. The two algorithms are tested respectively, which provides basic data support for the research of later coloring algorithms. 4. The design and implementation of adjacent points and distinguishing edge coloring, adjacent points and differentiable total coloring in the chromatic and discernible coloring problem of graphs are carried out. Point and distinguishing edge coloring and point and differentiable total coloring are four intelligent optimization algorithms. The whole idea of the four algorithms is to decompose the coloring problem into subproblems of several specific function modules, and then adjust the subproblems step by step through the iterative adjustment of the sub-problems in order until the sub-problems are solved successfully. After that, the successful state of the former sub-problem is not changed as the premise to solve the latter sub-problem. When all the sub-problems are solved successfully, the coloring is successful, and the algorithm ends. In this paper, the detailed flow and test cases of the algorithm are given, and the correctness, convergence and time complexity of the algorithm are analyzed. The test examples are all pseudo-nonisomorphic graphs within 7 points and 10,000 random connected graphs with less edge density within 1000 points. Through the analysis of the experimental results, it is shown that the algorithm has good execution efficiency and not high time complexity. At the same time, some meaningful and verified conclusions are given.
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

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

1 Ai Jun DONG;Guang Hui WANG;;Neighbor Sum Distinguishing Total Colorings of Graphs with Bounded Maximum Average Degree[J];Acta Mathematica Sinica(English Series);2014年04期

2 馬春燕;王治文;陳祥恩;楊芳;姚兵;;若干完全四部圖的可區(qū)別正常邊染色[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2013年21期

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

4 姚兵;陳祥恩;鐔松齡;;ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES[J];Acta Mathematica Scientia;2013年03期

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

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

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

8 ;On the adjacent-vertex-strongly-distinguishing total coloring of graphs[J];Science in China(Series A:Mathematics);2008年03期

9 ;D(β)-vertex-distinguishing total coloring of graphs[J];Science in China(Series A:Mathematics);2006年10期

10 馬剛,劉華,唐國梅,張忠輔;圈和扇的聯(lián)圖的全染色[J];華東交通大學(xué)學(xué)報(bào);2005年04期

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

1 程軍;基于生物行為機(jī)制的粒子群算法改進(jìn)及應(yīng)用[D];華南理工大學(xué);2014年

2 何嘉;基于遺傳算法優(yōu)化的中文分詞研究[D];電子科技大學(xué);2012年

，

本文編號(hào)：2323107