本文選題：圖染色 + 點可區(qū)別均勻全染色　； 參考：《蘭州交通大學》2017年碩士論文

【摘要】：隨著信息科學與網(wǎng)絡技術的快速發(fā)展,圖論因其直觀的圖形性和嚴密的邏輯性,在廣大的專家學者中受到了越來越多的關注和研究。許多問題都可以找到與之相匹配的圖的模型,例如大規(guī)模信息通訊、社交網(wǎng)絡、大數(shù)據(jù)采集及分析、物聯(lián)網(wǎng)等問題,都有著復雜的網(wǎng)絡化、結構化的特點。而圖論具有把復雜結構問題抽象轉(zhuǎn)化成以頂點和邊表示的清晰結構的特性,以圖為工具成為解決這些領域問題的新型且有效的方案,進而抽象為圖染色的方法予以解決。因此,對圖染色問題的研究與創(chuàng)新是非常有意義的。圖的染色問題屬于NP完全問題,一些經(jīng)典的智能算法如遺傳算法、粒子群算法、神經(jīng)網(wǎng)絡算法等被用來解決圖的染色問題時,僅能解決如正常點染色和正常邊染色等單約束條件染色問題,而對于全染色和可區(qū)別染色等多約束條件染色問題則到目前為止也沒有好的成果發(fā)表。本文首先設計并實現(xiàn)了三個解決多約束條件染色問題的染色算法,然后結合已公開發(fā)表的部分可區(qū)別圖染色算法,設計并實現(xiàn)了圖染色軟件系統(tǒng)(GCSS)。該系統(tǒng)可以為圖論研究的學者、愛好者以及應用圖染色技術解決現(xiàn)實問題的科研工作者提供一個良好的研究平臺。在該系統(tǒng)中,用戶只需選擇染色方法、圖的點數(shù)、邊密度等參數(shù),就能夠正確得到有限點數(shù)(100點)以內(nèi)所有簡單連通圖的5種可區(qū)別染色結果。這些結果為圖染色學者和愛好者提供了基礎研究數(shù)據(jù),也為科研工作者打算采用圖論技術解決計算機通信、排課表、任務調(diào)度、倉儲分配等組合優(yōu)化問題提供幫助。本文的具體工作如下:(1)介紹了K_p\E(k_(1,m))圖的點可區(qū)別邊色數(shù)猜想,針對該猜想設計并實現(xiàn)了圖的點可區(qū)別邊色數(shù)猜想證明算法。詳細描述了算法步驟,并對算法的正確性進行了測試,同時對2000個頂點以內(nèi)的所有K_p\E(k_(1,m))圖的點可區(qū)別邊色數(shù)進行測試,測試結果表明該猜想是成立的。(2)設計并實現(xiàn)了隨機圖的點可區(qū)別均勻全染色算法。算法的整體思路是根據(jù)約束條件將染色問題分解成多個子目標問題,當所有子目標問題都被成功解決后,即代表該染色成功,算法結束。文中給出了算法的詳細流程及測試案例,并分析了算法的正確性和時間復雜度。(3)基于OpenMP技術設計并實現(xiàn)了隨機有向圖弧染色并行算法。算法中通過多線程并行搜索染色解空間,從而降低染色成功所需要的時間,提高染色效率。實驗結果表明該算法能有效的縮短染色所需時間。(4)基于JNI技術實現(xiàn)圖染色算法與Java平臺的結合、基于JGraph技術實現(xiàn)染色結果的可視化,進而設計并實現(xiàn)了圖染色軟件系統(tǒng)。該系統(tǒng)包括以下六個功能模塊:圖染色介紹模塊、圖的顯示模塊、圖的生成模塊、圖染色驗證模塊、圖染色算法模塊、圖染色猜想證明模塊,其中圖染色算法模塊囊括了目前圖染色領域絕大多數(shù)的圖染色算法,所以該系統(tǒng)可以為圖論研究的學者、愛好者以及應用圖染色技術解決現(xiàn)實問題的科研工作者提供一個研究平臺。
[Abstract]:With the rapid development of information science and network technology, graph theory has attracted more and more attention and research in the vast majority of experts and scholars because of its intuitive graphics and strict logic. Many problems can be found to match the model of the graph, such as large-scale information communication, social network, large data collection and analysis, material association. Network and other problems have complex network and structural characteristics. And graph theory has the characteristics of transforming complex structural problems into clear structures which are expressed by vertices and edges. As a tool, graph is a new and effective solution to solve the problems in these fields, and then it is abstracted to solve the problem of graph dyeing. The research and innovation of the problem is of great significance. The problem of graph dyeing belongs to the NP complete problem. Some classical intelligent algorithms, such as genetic algorithm, particle swarm algorithm, neural network algorithm, are used to solve the problem of single constraint coloring such as normal point dyeing and normal edge dyeing, but for full dyeing and the other. No good results have been published so far. In this paper, three dyeing algorithms are designed and implemented to solve the problem of multi constraint condition dyeing, and then a graph dyeing software system (GCSS) is designed and realized. This system provides a good research platform for researchers, enthusiasts and researchers using graph dyeing technology to solve practical problems. In this system, users can correctly obtain 5 distinct dyes for all simple connected graphs within a finite number of points (100 points) by selecting only the parameters of the dyeing method, the number of points and the edge density. These results provide basic research data for graph dyeing scholars and enthusiasts, and also help researchers to use graph theory to solve the combinatorial optimization problems of computer communication, scheduling, task scheduling and warehousing allocation. The specific work of this paper is as follows: (1) the point distinguishing color number of K_pE (k_ (1, m)) is introduced. In view of the conjecture, the point distinguishable edge color number conjecture algorithm is designed and implemented. The algorithm steps are described in detail, and the correctness of the algorithm is tested. At the same time, the point distinguishing edge color number of all K_pE (k_ (1, m)) graphs within 2000 vertices is tested. The test results show that the conjecture is established. (2) design and Implementation The whole idea of the point distinguishable uniform total coloring algorithm of random graph. The whole idea of the algorithm is to decompose the dyed problem into multiple sub target problems according to the constraint conditions. When all the sub target problems are successfully solved, that is, it represents the success of the dyeing and the algorithm is over. The detailed detailed flow and test case of the algorithm are given, and the algorithm is analyzed. Accuracy and time complexity. (3) a parallel algorithm for random directed graph arc dyeing is designed and implemented based on OpenMP technology. In this algorithm, the algorithm can reduce the time needed for dyeing success and improve the dyeing efficiency by multi thread parallel search. The experimental results show that the algorithm can effectively shorten the time required for dyeing. (4) based on the technology of dyeing, the algorithm can effectively shorten the dyeing time. This paper realizes the combination of graph dyeing algorithm and Java platform, realizes the visualization of dyeing results based on JGraph technology, and then designs and implements a graph dyeing software system. The system includes the following six functional modules: graph dyeing introduction module, graph display module, graph generating module, graph dyeing verification module, graph dyeing algorithm module, graph dyeing guess The graph dyeing algorithm module covers most of the graph dyeing algorithms in the field of graph dyeing, so the system can provide a research platform for researchers, enthusiasts and scientific researchers using graph dyeing technology to solve practical problems.
【學位授予單位】：蘭州交通大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5

【參考文獻】

相關期刊論文 前10條

1 谷宇航;趙偉;李力;張昊;孟瑩;;基于OpenMP的矢量空間數(shù)據(jù)并行拓撲算法設計與實現(xiàn)[J];測繪工程;2015年11期

2 鄒競;馬華;謝鯤;;一種基于OpenMP的并行混合PVS算法[J];計算機應用研究;2016年01期

3 李敬文;李小慧;董威;賈西貝;杜永文;;隨機圖的點可區(qū)別全染色算法[J];計算機應用研究;2015年06期

4 李敬文;賈西貝;董威;李小慧;閆光輝;;圖的鄰點可區(qū)別全染色算法[J];山東大學學報(理學版);2015年02期

5 胡榮;鄒承明;;基于OpenMP的文件壓縮與解壓的并行設計模型[J];中南大學學報(自然科學版);2014年08期

6 高瑛;嚴正國;;OpenMP多核并行程序的設計與實現(xiàn)[J];電子測試;2014年05期

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

8 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期

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

10 強會英;王洪申;;圖K_(2n)\E(K_(2,m))(n≥9,m≥3)的點可區(qū)別邊染色[J];數(shù)學的實踐與認識;2012年24期

相關碩士學位論文 前2條

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

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

，

本文編號：2082355