图染色软件系统（GCSS）的研究与实现

发布时间：2018-06-29 14:05

本文选题：图染色 + 点可区别均匀全染色　；参考：《兰州交通大学》2017年硕士论文

【摘要】：随着信息科学与网络技术的快速发展,图论因其直观的图形性和严密的逻辑性,在广大的专家学者中受到了越来越多的关注和研究。许多问题都可以找到与之相匹配的图的模型,例如大规模信息通讯、社交网络、大数据采集及分析、物联网等问题,都有着复杂的网络化、结构化的特点。而图论具有把复杂结构问题抽象转化成以顶点和边表示的清晰结构的特性,以图为工具成为解决这些领域问题的新型且有效的方案,进而抽象为图染色的方法予以解决。因此,对图染色问题的研究与创新是非常有意义的。图的染色问题属于NP完全问题,一些经典的智能算法如遗传算法、粒子群算法、神经网络算法等被用来解决图的染色问题时,仅能解决如正常点染色和正常边染色等单约束条件染色问题,而对于全染色和可区别染色等多约束条件染色问题则到目前为止也没有好的成果发表。本文首先设计并实现了三个解决多约束条件染色问题的染色算法,然后结合已公开发表的部分可区别图染色算法,设计并实现了图染色软件系统(GCSS)。该系统可以为图论研究的学者、爱好者以及应用图染色技术解决现实问题的科研工作者提供一个良好的研究平台。在该系统中,用户只需选择染色方法、图的点数、边密度等参数,就能够正确得到有限点数(100点)以内所有简单连通图的5种可区别染色结果。这些结果为图染色学者和爱好者提供了基础研究数据,也为科研工作者打算采用图论技术解决计算机通信、排课表、任务调度、仓储分配等组合优化问题提供帮助。本文的具体工作如下:(1)介绍了K_p\E(k_(1,m))图的点可区别边色数猜想,针对该猜想设计并实现了图的点可区别边色数猜想证明算法。详细描述了算法步骤,并对算法的正确性进行了测试,同时对2000个顶点以内的所有K_p\E(k_(1,m))图的点可区别边色数进行测试,测试结果表明该猜想是成立的。(2)设计并实现了随机图的点可区别均匀全染色算法。算法的整体思路是根据约束条件将染色问题分解成多个子目标问题,当所有子目标问题都被成功解决后,即代表该染色成功,算法结束。文中给出了算法的详细流程及测试案例,并分析了算法的正确性和时间复杂度。(3)基于OpenMP技术设计并实现了随机有向图弧染色并行算法。算法中通过多线程并行搜索染色解空间,从而降低染色成功所需要的时间,提高染色效率。实验结果表明该算法能有效的缩短染色所需时间。(4)基于JNI技术实现图染色算法与Java平台的结合、基于JGraph技术实现染色结果的可视化,进而设计并实现了图染色软件系统。该系统包括以下六个功能模块:图染色介绍模块、图的显示模块、图的生成模块、图染色验证模块、图染色算法模块、图染色猜想证明模块,其中图染色算法模块囊括了目前图染色领域绝大多数的图染色算法,所以该系统可以为图论研究的学者、爱好者以及应用图染色技术解决现实问题的科研工作者提供一个研究平台。
[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

【参考文献】