化学图论算法和大规模图染色算法研究

发布时间：2020-05-17 09:36

【摘要】：图论是数学的一个重要分支,也是计算机等基础学科的基础,它是以图作为研究对象,现实中很多问题都可以抽象为图,从而转化为图论的应用问题来解决,例如由著名的数学家哈密尔顿提出的周游世界的问题,旅行商问题、数独游戏;在工程上,经常遇到的资源分配与调度问题、组合优化问题;通信领域的通信信道分配、电路布线问题等,这些问题都可以利用图论的知识来解决。随着社会的发展、科学技术的进步,图论的研究不仅仅限于数学上的推理与证明,而是与众多学科交叉融合发展,近年来图论研究取得了很大的发展,广泛的应用于计算机科学、通信网络、信信息科学、人工智能、图像处理、物理以及化学等领域,并取得了很多重要的研究成果。图论的一个常用应用就是在有机化学领域,早在半个多世纪前Gunthard和Primas在研究化学中的Huckel理论时提出了'哪些图是谱确定的?',这一问题的解决涉及到图谱理论,主要通过图矩阵的数量特征来确定图是否由谱唯一确定,否则寻找其同谱偶的问题。后来,著名的数学化学家Gutman提出了图能量的理论,就是借助于谱来研究化学分子的相关性质的理论。本文设计算法求得了两种特殊图的同谱图和给定点数下的非完全-拉普拉斯界能图。图的染色问题是图论的一个重要研究方向,而且具有极强的应用性。传统的染色是利用数学的方法进行染色,随着计算机的逐渐发展,利用计算机设计算法实现染色,这是图染色问题的一大飞跃。例如传统的智能算法:遗传算法、粒子群优化算法、神经网络等应用于图染色问题,但是这些智能算法一般仅能解决单目标的染色。虽然近年来出现了新的染色算法,但是仅能实现规模较小的图染色。随着社会的发展,为了满足日常研究需要大规模图出现了,此时,已有的算法已经不能满足需求,本文针对此问题设计了算法,求得了大规模图的邻点可区别全染色,经过大量的实验得出了确切的结论,为以后图论的发展奠定了基础。论文分为三大部分,文章的主要内容如下:(1)第一部分介绍了图论和图染色的基本概念、相关理论以及图论在化学领域的应用,如同分异构问题和能量问题。同时对已有研究方法的优缺点进行了总结。(2)在第二部分中包含两类,第一类给出了两种特殊图(Π-型图和星图)的生成算法以及同谱偶求解算法,具体思想是第一步输入顶点数目,按照基本规则生成连通图,然后根据本文需要设计规则和判断函数,生成Π-型图和星图;第二步设计求谱算法,并对第一步所生成的Π-型图和星图求谱,求得谱后进行比较,最后得出谱相同的图的结构;第二类给出了固定阶数下的所有图的生成算法和拉普拉斯能量求解算法,具体思想是首先生成给定阶数下的所有图;然后设计拉普拉斯能量算法,针对所生成的所有图求能量,最后找出本文所需要的图。这两大部分算法为后续图论在其他学科领域的研究和证明提供基础研究数据,尤其为图论在化学领域的研究奠定良好的基础。(3)在第三部分中,设计并实现了大规模图的生成算法和分割算法、邻点可区别全染色算法,同时设计了正常全染色算法、染色冲突调整算法等子算法。具体思想是生成随机连通图,然后按照分割规则将大图分割为多个子图,在对子图进行邻可区别全染色,最终确保相邻顶点的颜色不同,相邻边的颜色不同,相邻顶点与边的颜色不同,相邻顶点的色集合不同。本文通过大量的实验验证了算法的正确性,同时得到了一定数量的结果。
【图文】：

程序运行,文本输出,硕士学位论文,交通大学

兰州交通大学硕士学位论文 00010110001001010000101101110100011010010101101010111000010000008765432112345678vvvvvvvvvvvvvvvv图 5.7 分割后子图2G 的邻接矩阵断，，分割后的两个子图大小满足分割要求，因此大图分割成功，完成 2，程序运行结果及文本输出结果如下：

连通图,输出结果,全染色,邻点

图 5.9 分割程序文本输出结果.4 算法分析(1) 算法正确性本算法是寻找图中的二度及以上的点断开，符合分割的基本思想，由分割测试达到了无损分割的要求，分割后的子图能重新还原为大图，证明了分割的正确(2) 算法实用性算法能够实现 5000 个点的大图的无损分割，解决了大图无法处理的问题，降复杂度，提高了处理效率，为图论的研究提供了很好的思路，同时在复杂网络物理等学科的应用提供了基础研究数据。大规模图的邻点可区别全染色算法.1 邻点可区别全染色的定义及相关概念定义 5.1 对于一个简单连通图 G (V ,E)，其阶数不小于 2， V (G)是图的顶点集)是图的边集合。其 k 正常全染色是指对于图 , 存在一个
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】