图的容错直径与宽直径及超立方体的（d,k）独立数的研究

摘要

计算机互连网络的拓扑结构是图,图论是设计和分析计算机网络的一个基本而又重要的数学工具.容错直径D<,k>宽直径d<,k>都是度量互连网络可靠性和有效性的重要参数.对于一般的图G,确定它的容错直径D<,k>困难很大,而确定它的宽直径d<,k>却是个NPC问题,因此讨论它们之间的关系显得很重要.对任何k连通图,它的容错直径D<,k>不超过宽直径d<,k>.到目前为止,关于容错直径与宽直径关系的结果很少.该论文证明了:当G为2连通图时,d<,2>≤max{(d-1)D<,2>-d/2-1)+1,D<,2>+1};并给出d=2时d<,2>=D<,2>+1的一个充分必要条件:即d<,2>=3或4且达到d<,2>值的任何两顶点必相邻.设G为3连通图:若d=2,则d<,3>=≤mzx{(D<,2>-1)(D<,3>-1/2D<,2>-1)+1,3D<,3>-5,D<,3>+1};若D<,2>=2,则d<,3>≤max{D<,3>+1,2D<,3>-2};若d≥2,且d<,2>≥3,则d<,3>≤(d-1)[2(D<,2>-1)(D<,3>-1)-d-2]+1.(d,k)独立数α<,d,k>(G)也是分析互连网络性能的一个重要参数.对于任意给定的图G和正整数d、k,确定G的(d,k)独立数问题是一个NPC问题.因此,确定一些特殊图的(d,k)独立数显得很重要,但是到目前为止,我们还没见到任何特殊图的(d,k)独立数的确定.该文确定了k维超立方体网络的(d,k)独立数等于2,如果d=k(≥4)或者d=k-1(≥6);以及α<,d,k-1>(Q<,k>)=α<,d,k>(Q<,k>),其中0≤t≤k-2,1≤d≤k-t-1.

目录

文摘

英文文摘

第一章绪论

一、计算机互连网络与图

二、图的基本概念

三、主要引理

第二章连通图的容错直径与宽直径

第一节引言

一、容错直径和宽直径及其定义

二、主要引理

三、主要结果

第二节2连通图的容错直径与宽直径

一、引理

二、主要结果的证明

第三节3连通图的容错直径与宽直径

一、引理

二、主要结果的证明

三、结论

第三章k维超立方体网络的(d，k)独立数

第一节(d，k)独立数及其主要性质

一、(d，k)独立数的定义

二、(d，k)独立数的主要性质

第二节超立方体网络的定义及其主要性质

一、超立方体网络的定义

二、超立方体网络的主要性质

第三节主要结果

一、引理

二、主要结果的证明

三、结论

参考文献

致谢

攻读学位期间发表的学术论文及已完成而未发表的学术论文