论文部分内容阅读
图的某些参数,如连通度和直径,因为其在图论和组合中固有的重要性及其与通信网络的容错性和传输延迟的关系而得到广泛研究.超大规模集成电路技术和光纤材料科学的发展使我们有能力设计大型并行处理计算机系统和快速、复杂的通信网络.这些系统不仅要求我们研究网络的连通度和直径,而且要研究连接两个节点或两个点集间的内部点不交的多条路径.这自然引导人们把图的直径进行推广.本文主要研究了图的广义直径,特别是熟知的宽直径和Rabin数.主要工作包括以下几个方面:1.本文定义了图的广义直径,该定义统一了图的直径,宽直径和Rabin数的概念.2.研究了k-正则k-连通图、广义Petersen图和置换图的宽直径.3.图G的w-Rabin数及其广义直径gdw(G).4.环网络广泛应用于计算机局域网设计和各种并行处理系统.用N表示环网络节点的数目,记环网络为G(N;1.s2,…,st),其中每个节点i和i+1,i+s2,…,i+s1(mod N)分别相连.对l=2的情形,已经有了丰富的结果.本文重点研究了l=3的情形,即三环网络,给出其直径的上界,并给出N不太大时,三环网络取得最优的一个条件.5.网络的可嵌入性是衡量网络性能好坏的一个重要标准,因此如何将一个较小的网络嵌入到大的网络中去成为网络设计中需要考虑的一个重要问题.文献[68]中作者证明了如何将环网络嵌入到超立方体中,但不幸的是超立方体网络中不含有长为奇数的圈,因此不能将长为奇数的圈嵌入到超立方体中.本文定义了折叠式超立方体FH(n),证明了折叠式超立方体网络的直径约等于超立方体直径的一半,(n+1)-宽直径为n,比n-立方体的n-直径小1.还证明了FH(n)中包含长为奇数的圈,并给出了一个嵌入长为奇数的圈到折叠式超立方体网络中的方法.