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