论文部分内容阅读
众所周知，由已知的几个图按照图的运算合成新的图是构造图的重要方法，研究合成图的性质与因子图的性质之间的关系是一项非常有意义的工作.全文共分为六章，围绕图的直积、字典积和冠进行讨论，主要研究这三类合成图的性质，并讨论了基于直积互连网络的通信算法.下面是本文的一些主要结果: 1.第二章中，证明了图的直积满足交换律和结合律，推广了图的直积的Wiener指数的计算公式. 2.第三章中，首先给出了字典积的直径和连通度与因子图的直径和连通度的关系，然后证明了字典积的Laplacian谱与因子图的Laplacian谱的相关关系，最后给出了字典积的等周数的一个估计. 3.第四章中，证明了冠的Laplacian谱与因子图的Laplacian谱的相关关系. 4.第五章中，给出了由路和圈构成的合成图的一些性质，研究了与路和圈相关的几个多项式和行列式的性质. 5.第六章中，给出了网格和一般直积网络上的一个新的虫孔路由算法。