论文部分内容阅读
图论是目前发展迅速、应用广泛的一个数学分支。在许多学科领域中,如运筹学、信息论、控制论、量子化学以及计算机科学等,其研究对象都可以抽象为图论中相关的概念,因此图论研究为这些学科中离散性问题的解决提供了新的办法。随着计算机技术高速发展,计算机技术与图论的交叉研究领域成为目前国际上图论研究的重要发展方向。本文旨在探索如何有效地使用计算机工具解决图论中的相关问题,推广和发展国内外图论的一些结果。主要成果如下:
(1)在计算机网络研究中,网络拓扑结构可以抽象为图论中的图,网络防病毒能力与图最大谱半径大小成反比。本文研究具有最大谱半径的图的判定问题。本文根据两类图C(n,k,d,t)和H(n,k)的特征,提出了图G(n,k,d,t)与图n(n,k)的邻接矩阵构造算法,编程计算了e=n+(d-l/2)+t-1,e≦2n-3时两类特殊图G(n,k,d,t)和H(n,k)的谱半径,确定了n≤200时w(n,e)中具有最大谱半径的图,并得到结论:当(n,e)取值为(60,69),(68,88),(80,85)时,图G(n,k,d,t)与图H(n,k)谱半径相同;当n∈[4,24]时,图G(n,k,d,t)具有最大谱半径。这部分结论推广了已有的研究成果。
(2)对于n阶反正则序列实现的连通图An和非连通图Anc,在Behzad(1967)和Merris(2003)研究的基础上,本文证明了反正则连通图An中含有K3子图数目△n。的递推公式△n=△n-2+en-2以及反正则非连通图Anc中含有K3子图数目△nc的递推公式△nc=△n-1+en-l-enc.
(3)提出了2-反正则图的概念,并根据度序列判定定理和同构图定义,实现了序列可图化和同构图的判定算法,得到n阶(n≤20)2-反正则可图化序列和对应的所有n阶(n≤10)非同构简单连通图。
本文所做的工作进一步完善了图谱理论的相关结论,为解决Cvetkovic的猜想创造了条件,发现并证明反正则图中含有K3子图数目的递推公式,以及获得部分2-反正则序列的所有非同构简单连通图,为进一步研究2-反正则图奠定了一定的基础。