图论在化学能量和网络方面的应用

摘要

对图能量的研究是图论中一个很活跃的研究方向。设G是有限、简单、无向图，n个点，m条边。A(G)=(aij)n×n是图G的邻接矩阵，λ1,λ2,…,λn是A(G)的n个特征值，也称为图G的特征值，则称E(G)=∑i=n i=1｜λi｜为图G的能量。在化学领域中，共轭分子生成产生的热能几乎等于该分子的π-电子总能量，而分子的π-电子总能量的计算又可归咎于E(G)=∑i=n i=1｜λi｜的计算。本文根据几种图能量的一些主要结果，讨论了单圈图的能量。单圈图是图论中比较特殊的一类的图，若从其圈上去掉一条边则其就变成了树，它的能量计算有比其它图较为简便的算法。本文通过对单圈图的特点的研究，找到了一对同谱的等能量图。 在图论中，另一活跃的研究方向是网络中的路由算法。在计算机的网络拓扑模型图中，由于超立方体图Qn具有的良好的拓扑性质，所以它能够成为计算机超大规模并行计算互联网的结构模型。在超立方体中，在研究它的容错路由方面，安全向量起着很重要的角色，在吴杰的文章[1]中，每一个节点的安全向量都要经过n-1轮的计算，计算比较麻烦。本文在此基础上，改进了安全向量的定义，并通过节点的安全矩阵来确定节点的安全向量。这种方法，计算方面不仅简单些，而且，也可以判断与节点距离为k的所有节点间是否存在最优通路。 本文第一章是绪论部分。第二章给出了能量的概念，并给了几种特殊类图的能量计算以及性质。通过计算比较，给出了部分图能量的计算方法，并给出一些等能量的几对图。并着重讨论了单圈图的能量。第三章分析了超立方体的结构特点。根据安全向量的定义，改进了超立方体中的安全向量，并给出了通过节点的安全矩阵来求节点安全向量的方法。第四章进行总结。

目录

文摘

英文文摘

声明

第一章绪论

第二章图的能量

2.1基本概念

2.2主要定理及引理

2.3一些能量结果

2.4能量的上下界

2.5主要结果

第三章超立方体网络算法

3.1超立方体基本概念

3.2路由算法

3.2.1无错路由算法

3.2.2容错路由算法

3.3改进的扩展安全向量模型

结论

参考文献

攻读硕士学位期间发表的论文

致谢