（计算数学专业论文）网络（图）广义直径的研究.pdf

摘要 摘要 图的某些参数，如连通度和直径，因为其在图论和组合中固有的重要性 及其与通信网络的容错性和传输延迟的关系而得到广泛研究超大规模集成 电路技术和光纤材料科学的发展使我们有能力设计大型并行处理计算机系 统和快速、复杂的通信网络这些系统不仅要求我们研究网络的连通度和直 径，而且要研究连接两个节点或两个点集间的内部点不交的多条路径这自 然引导人们把图的直径进行推广本文主要研究了图的广义直径，特别是熟 知的宽宣径和r a n n 数 主要工作包括以下几个方面： 1 本文定义了图的广义直径，该定义统一了图的直径，宽直径和r a b i n 数的概念 2 研究了 一正则女连通图、广义p e t e r s e n 图和置换图的宽直径 ( 1 ) 令 、 ，( n k ) = m a x d k ( g ) ：g 是有n 个顶点的 一正则一连通图) h s u 和l u c z a k 在文一剖中对函数，( n ，k ) 的取值作了讨论本文给出一个 作图的算法，利用该算法可以构造有2 m 个顶点的具有最大一直径的一正 则k - 连通图，并且利用该算法得到了函数，( 礼k ) 的未知的值 ( 2 ) p e t e i s e n 图是图论中我们熟知的图，广义p e t e r s e n 图，记为尸( m ，a ) ， 是有2 m 个顶点的图，其顶点集为 u o 缸“w o w l 、，叫。一1 ) ，边有 点对( 让。，w 。) ( ，u 卜1 ) ，( 让；u 件1 ) ，( u 叫件。) ，和( 加，w 。) 绐。出，0si 冬 m l ，这里下标的运算都是在模m 下的运算本文证明了p ( m ，2 ) 的直径 和3 一直径分别为o ( t ) 和o ( 罢) ( 3 ) 用g 表示有限简单图，其顶点集为q ”2 ，用表示集合 1 2 - n ) 上的对称群，o s n 图g 的m 生成图，记为只( g ) ，有g 的两个不交的拷贝，分别记为g 和g ，组成g 和g 7 有边e i = 地 “1 相 连，r ( g ) 也称为置换图文i m ；) 中对置换图的连通度、直径等参数做 了研究本文用图g 的宽直径作参数给出了只( g ) 宽直径的上界，并且给 出尸0 ( g ) 的2 一直径和图g 的直径之间的关系 3 图g 的 r a b i n 数及其广义直径9 叱( g ) ， 摘要 ( 1 1 网络g 的叫r a b i n 数，记为r w ( g ) ，是指最小的f ，使得对任意的w + 1 个顶点z h ，蚰，存在枷条长至多为f 的从r 分别到y 1 9 2 ，y 。的内部 点不交的路左文对一般的。正则连通图的r a b i n 敷作了研究证明了n 个顶点的正则琏通图的k - r a b i n 数至多为j 并且当n = 2 k - 3 + i ( k 一2 ) 时，该上界是不能改进的 f 2 ) 研究了k 一正则连通图的广义直径给出g d k ( g ) 的一些性质 并且证明了n 个顶点的正则k - 连通图的广义直径至多为n 2 ，当n = 2 一3 + i ( k 一2 ) 时，该上界是可以达到的 4 环网络广泛应用于计算机局域网设计和各种并行处理系统用 表示环网络节点的数目，记环网络为g ( ；l 觇，：日) ，其中每个节点i 和 i + 1 ，i + s 2 ，i + s f( m o dn ) 分别相连对f = 2 的情形，已经有了丰富 的结果本文重点研究了2 = 3 的情形，即三环网络，给出其直径的上界， 并给出不太大时。三环网络取得最优的一个条件 5 网络的可嵌入性是衡量网络性能好坏的一个重要标准，因此如何将 一个较小的网络嵌入到大的网络中去成为网络设计中需要考虑的一个重要 问题文献【叫j 中作者证明了如何将环网络嵌入到起立方体中，但不幸的是 超立方体网络中不含有长为奇数的圈，因此不能将长为奇数的圈嵌入到超立 方体中本文定义了折叠式超立方体f h ( n ) ，证明了折叠式超立方体网络的 直径约等于超立方体直径的一半，( n + 1 ) - 宽直径为n ，比n - 立方体的n 一直 径小1 还证明了f h ( n ) 中包含长为奇数的圈，并给出了一个嵌入长为奇数 的圈到折叠式超立方体网络中的方法 1 1 a b s t r a c t a b s t r a c t g r a p hp a r a m e t e r ss u c ha sc o n n e c t i v i t ya n dd i a m e t e rh a v eb e e ns t u d i e d e x t e n s i v e l yd u et ot h e i ri n t r i n s i ci m p o r t a n c ei ng r a p ht h e o r y ，c o m b i n a t o r i c s a n dt h p i rr e l a t i o a st of a n da p p l i c a t i o n si n ) f a u l tt o l e r a n c ea n dt r a n s m i s s i o n d e l a yi nc o m m u n i c a t i o n sn e t w o r k s t h ea d v e n to fv l s i t e c h n o l o g ya n df i b e r o p t i c sm a t e r i a l s c i e n c eh a se n a b l e du st od e s i g nm a s s i v e l yp a r a l l e lp r o c e s s i n g c o m p u t e rs y s t e m sa n df a s ta n dc o m p l i c a t e dc o m m u n i c a t i o n sn e t w o r k s a l l t h e s es y s t e m si n c r e a s et h e i rr e l i a b i l i t yb ys t u d y i n g ( a m o n go t h e r ) t h ee x i s t e n c eo ft w o ( o rm o r e ) d i s j o i n tp a t h sc o n n e c t i n ga n yt w on o d e s t os a r i s f ya l l t h e s ed e m a n d , h w eg e n e r a l i z ed i a m e t e ro fg r a p h st og e n e r a l i z e dd i a m e t e ro f g r a p h s i nt h i sp a p e r ，w em a i n l ys 1 ( 1 yg e n e r a l i z e dw i d ed i a m e t e ro fg r a p h s e s p e c i a l l yw i d ed i a m e t e ra n dr a b i nn u m b e r o fg r a p h s ， i nt h ef o l l o w i n g ，w el i s tt h em a i nw o r k so fo u rp a p e r 1 w ed e f i n et h eg e n e r a l i z e dd i a m e t e ro fg r a p h sw h i c hu n i f i e st h ed e f t n i t i o n so fd i a m e t e r lw i d ed i a m e t e ra n dr a b i nn u m b e ro fg r a p h s 2 k - r e g u l a rk - c o n n e c t e ( 1g r a p h s ，g e n e r a l i z e dp e t e r s e ng r a p h sa n dp e r m u t a t i o ng r a p h sa r es t u d i e de x t e n s i v e l yi nt h ed e s i g no fn e t w o r k s ( 1 ) l e t ，( 凡，女) = m a x 以( g ) ：gi s ak - r e g u l a rk - c o n n e c t e dg r a p hw i t hnv e r t i c e s h s ua n dl u c z a k l 4 6 1s t u d i e dt h ef u n c t i o n ，( n ni nt h i sp a p e r ，w eg i v ea na l - g m i t h , na n dp lo 、et h a rw ec ai lc o n s t r u c tk r e g u l a rk - c o n n e c t e dg r a p h so n2 m v e r t i c e sw i t h 山pm a x i m u mk - d i a m e t e ru s i n gi tw ea l s op r o v es o m ek n o w n r e s u l t sa b o u t ，( 2 m ，) a n dv e r i f yt h a tw ec a ng e tn e wv a l u e so ff ( 2 m ，k ) b y o u ra l g o r i t h m ( 2 ) p e t e i s e ng r a p hi sw e l lk n o w n i ng r a p ht h e o r y , a g e n e r a l i z e dp e t e r s e n g r a p h d e n o t e db yp ( m ，d ) ，i sd e f i n e d a sf o l l o w s ：i t sv e r t e xs e ti suu w ， w h e r eu = “i j “l ，一，“m 一【) ：w = ( t o o ，叫l ，t f m l ，i t se d g e sa r eg i v e n b y ( 札。，叫。) ，( u ，f f ：。1 ) ，( u t ，u i + i ) ，( w l ，u ) i + 4 ) a n d ( 训t ，叫t 一口) ，f o r0s is r n 一1 ， w i t ht h ea d d i t i o no fs u b s c r i p t sb e i n gp e r f o r m e du n d e rm o d u l om i nt h i s l u a b s t r a c t p a p e r ，w es h o wt h a tt h ed i a m e t e lo fg e n e r a l i z e dp e t e r s e ng r a p h 尸( m ，2 ) i s o ( 寻) a n d r b e3 - i d ed i a m e t e r 。 ，) ( ，2 ) i s0 ( 予) ( 3 ) 。l e tgb eac o n n e c t e dg l a p hw l t j 霞v e r t i c e s a n d0 _ & ，t h e s y m m e t r i cg r o u po n l ，2 ，7 l t h en g e n e r a l i z e dg r a p ho v e rg d e n o t e d b yr ( g ) ，c o n s i s t so ft w od i s j o i n t , i d e n t i c a lc o p i e so fga l o n gw i t he d g e s 口扣) i nt h i sp a p e r ，w ei n v e s t i g a t e dt h er e l a t i o nb e t w e e n 仰一w i d ed i a m e t e ro f ga n d 一w i d ed i a m e t e ro fr ( g 1f o ra n ) p e r m u t a t i o n 口s na n d 1w e a l s os t u d i e dt h er e l a t i o nb e t w e e i j2 - w i d ed i a m e t e ro f 只( g ) a n dt h ed i a m e t e r o fg 3 t h e 叫一r a b i nn u m b e ra n dg e n e r a l i z e dd i a m e t e ro fg r a p h s ( 1 ) t h ew r a b i nn u m b e r o f lg r a p hd e n o t e db ，( g ) ，i st h em i n i m u m fs u c ht h a tf o ra n yw + 1d i s t i mr 、，e l t i c e s0 ，1 一，y ，t h e r ea r ewv e r t e x - d i s j o i n rp a t h so fl e n g t h sa tm o s t c o n n e c t i n g 。t oy 1 y 2 ，t ，f r e s p e c t i v e l y i nt h i sp a p e r ：w es t u d yt h er a b i un l l lr ) e ro fk - r e g u l a rk - c o n n e c t e dg r a p h s a n dp r o v et h a te x t e r y k - r e g u l a r “c o n n e c t e dg r a p ho n 礼v e r t i c e sh a sr a b i n n u m b e ra tm o s t 礼2a n dt h i su p p e rb o u n dc a n n o tb ei m p r o v e dw h e n 佗= 2 一3 + i ( 一2 ) ( 2 ) i nt h i sp a p e r w es t u d - r i l eg e n e r a l i z e dk - d i a m e t e r6 fk - r e g u l a r 一 c o n n e c t e dg r a p h s w ed e r i v es o n 】l 、”】) r n e so f9 d k ( g ) a n ds h o wt h a te v e r y k - r e g u l a rk - c o n n e c t e dg r a p h o n77 、1 e r d c p - h a sg e n e r a l i z e dk - d i a m e t e ra tm o s t 礼2a n dt h i su p p e rb o u n di st i g h tu h e n ， = 2 一3 + i ( k 一2 ) 4 c i r c u l a n tn e t w o r k sa r ehi d e ? u s e di nt i l e d e s i g no fl o c a ln e t w o r k s a n dv a r i o u sp a r a l l e lp r o c e s s i n gs 、s t e m sl e t , nb ea np o s i t i v ei n t e g e r 、l e t g ( ；1 ，8 2 ，一8 1 , ) b eac i r c u l a n tn e t w o r ko n n o d e s ，n o d e ii s a d j a c e n tt o n o d e s2 + 1 i + 5 2 ，一。i + s ( r o o d 1 r e s p e c t i v e b ，t h e r ea r em a n y r e s u l t s f o rt h ec a s pt h a t7 = 2i nt h i sp i j i e l p n l a i n l ) s t u d yt h ec a s ef = 3 t h a t i s t r i p l el o o pn e t w o r k s t h eu p l ”i b ( n nd sr e lt h ed i a m e t e r so ft r i p l el o o p n e t w o r k sa r eg i 、e n w h e nni sl i m i t e dt h ec o n d i t i o n sf o rt h eo p t i m a lt r i p l e l o o pn e t w o r k sa r eo b t a i n e d 5 m a p p i n gas m a l lt o p o l o g ) i m oa l a r g eo n ei s a ni m p o r t a n tp r o b l e m f o rd e s i g n i n ge f f i c i e n t n e t w o r k sh f 6 t 1 1 pa n t h e r sh a v es h o w nh o wt om a p a 丁 s t a c t r i n g so fe v ( i if e n g t h sa n dm e s h e si n t oh 、。p e r c u ) e s i n c en - c u b eq nc o n t a i n s r i oc y c l e so fo d dl e n g t h s c y c l e so fo d dl e n g t h sc a n n o tb em a p p e di n t oq n i nt h i sp a p e r ，w ed e f i n et h ef o h l c d1 1 j p e r ( u b ef 日( n ) a n dp r o v et h a tt h e d i a m e t e ro fi ti sa p p r o x i m a t eo n c h a l fo it h ed i a m e t e ro ft h eh y p e r e u b ea n d t h e ( 7 7 - 1 - d i a m e t e ro ff 日( n ) i sa ri n ( 1 s tmw h i c hi sl e s s1t h a nt h ew i d e d i a m e t e lo f7 l f u b ew ea l s op r m ( 1h a lt h e l d e d1 1 ) ，p e r c u b ec o n t a i n st h e c 3 ，c l e so fo d d l e n g t h sa n dg i v ea n 1 j 苷j ! i t h ms h ( ) 、i n gh o w t o m a pr i n g so f o d d l e n g t h si n t of b i d e dh y p e r c u b e s 第一章绪论 1 1 背景介绍 图论是近年来离散数学和组合数学领域较为活跃的分支之一自十八世 纪成为一门独立学科以来，图论的发展大体可分为三个阶段，第一个阶段是 从十八世纪中叶到十九世纪中叶，这时的图论处于萌芽阶段。主要是解决一 些由游戏产生的问题，例如所谓的哥尼斯堡七桥问题第二个阶段是从十九 世纪中叶到二十世纪中叶这个时期图论问题大量出现，例如h a m i l t o n 问 题，四色问题等二十世纪中叶以后是第三阶段，由于生产管理、军事、交通 运输、计算机网络等方面提出的实际问题的需要，特别是许多离散性问题的 出现，以及由于有了大型电子计算机，从而使大规模问题的求解成为可能， 图论及其应用的研究得到了飞速的发展 图的某些参数，如连通度和直径因为其在图论和组合中固有的重要性及 其与通信网络的容错性和传输廷迟的关系而得到广泛研究超大规模集成 电路技术和光纤材料科学的发展使我们有能力设计大型并行处理计算机系 统和快速、复杂的通信网络这些系统不仅要求我们研究网络的连通度和直 径，而且要研究连接两个节点或两个点集问的内部点不交的多条路径这自 然引导人们把图的直径进行推广，本文主要对两类广义直径作了研究，一类 是熟知的宽直径，关于宽直径的综述，可参阅文献【4u l ，一类是r a b i n 数， 主要考虑一个顶点和点集之间的广义直径，关于这方面的工作可参阅l i a w 和c h a n g 0 6 o 硼及h o u ( j 嘲 本文中图论术语和记法主要采自b o n d y 和、i u r t y i l 3 ，h a r a r v f 3 7 1 ，g o u l d 3 3 1 和徐俊明i ” 文中对图和网络不加区别，图中两点间的距离是指连接两点 的最短路的长，图的直径是指图中两点间距离的最大值图的连通度是指为 使图g 不连通或成孤立点而从图中去掉的最少的顶点数这两个参数在图 论领域中已经得到深入的研究，例如专著【1 4 l 引 图论在数学和非数学领域都有很多应用图论和组合在计算机科学和信 息技术特别是在并行或分布式计算机系统互连网络的设计中起着重要作用 当我们把网络看作图时用图的顶点表示处理器( 或站点) ，如果两个处理 器连通就用两点之间的边来表示在这个意义上，直径可看作信息最大传输 第一章绪论 延迟的度量，连通度是度量网络容错性的个很好参数( 当网络某些顶点发 生故障而失效时，网络还能保证无故障的顶点之间的数据通信，则说明该网 络能够容忍这些顶点的失效，所谓容错性即是网络能够容忍的失效顶点的最 大数目) 在并行和分布式计算系统的设计中，一个关键和基本的问题是设 计的互连网络有高效的通信能力象前面所讨论的，用图的连通度来度量网 络的可靠性和容错能力，用图的直径来度量信息从一个节点到另一个节点所 要经过的最多节点的数目考虑到这些因素，互连网络的一个好的设计必须 是一个稀疏的，同构型的( 为了实现容易和有效的路由方案而有一定程度的 对称性) 使得连通度尽可能大而直径尽可能小的图 由于超大规模集成电路和光纤技术的发展，使我们有能力为大型并行处 理系统设计复杂的和具有成千上万个节点的网络网络设计的两个中心问题 是； ( 1 ) 这么多的处理器之间如何互相通信? ( 2 ) 当有节点或连线出现故障或失效时，网络如何通信? 这两个和其他相关问题在离散数学、计算机科学和信息工程领域已经被 广泛而深入的研究本文关心的问题是图中两点或两个点集之间内部点不交 的多条路径而不仅仅考虑两点之间单一条最短路 除非另外说明，用g 表示不带自环和重边的简单图，t ( g ) 和e ( g ) 分 别表示图g 的顶点集和边集，( g 1 表示图g 的连通度，d ( g ) 表示图g 的直径j aj 表示集合a 中元索的数目， 尸表示路p 的长度对任意的 顶点集sc g ) 和? 1 7 ( g ) s 且1 s = l s isi t l = tsu ，sk ( g ) 用r ( s ，丁) 表示从点集s 到点集丁的叫条内部点不交的一族路，即 只，( s ，t ) = p i ，p 2 ，r ) ；p i 兰j p 2 i r j 其中只表示一个端点在s 中另一端点在r 中的路，并且s 和丁中每一顶 点至少是这些路的一个端点点集s 和了间的广义仆距离，记为9 d 。( s ，r ) 指最小的j r l 这里j 岛j 取遍所有的只，( s ，丁) ：图g 的广义伽一直径，记 为9 乩( g ) 指晟大的9 乩( s ，丁) 其中9 d 。( s 丁) 取遍v ( g ) 中所有点集对 s 丁) 使得1ss = l s l i t = ts t cs f g ) 显然，当l s = l t l = u = 1 时广义直径，f ，( g ) = d 【g ) 即为图的直 径因此易知g 南( g ) 矗( g ) 当i s = ；t ；= 1 ”】时，广义直径口d 。f g ) 2 鼾一举绪论 即为我们熟知的宽直径d 。( g ) 当i s i = 1 1 t i = u 时，广义直径g 此( g ) 即 为图g 的r a b i n 数 除了宽直径和r a b i n 数之外，还有一种和广义直径密切相关的直径值 得我们注意，就是错直径，定义图g 的一1 ) 一错直径为 d 。( g ) = m a x d ( g s ) f s i 一1 ) 错直径的一般定义由h s u ( 1 9 9 4 】给出，“：= ( g ) 的特殊情形由k r i s h n a m o o r t h y 和k r i s h n a m u r t h ) ( 1 9 8 7 ) 首先给出 对宽直径、错宣径和r a b i n 数有下面的基本性质： 性质1 1 1g 为“连通困，则 门j d l ( g ) sd 2 ( g ) s 茎d k ( g ) r 纠d l ( g ) d 2 ( g ) 曼d e ( g ) f 圳r l ( g ) sn ( g ) s - 曼r k ( g ) “，d 。( g ) c f 。( g ) 和d 。( g ) ( g ) 对l u k 1 2 几类常用的互连网络的广义直径 本节介绍几类常用的互连网络，这里只介绍有关这几类网络的主要结 果，要了解它们的详细定义和结果可参阅有关参考文献 1 n 维超立方体熟知q 。为礼- 连通m 正则图并且d ( q 。) = 乱s a a d 和s c h u l t z j ( 1 9 8 8 ) 证明了d 。( q 。) = d 。( q 。) = 十1 - n 3 ( 也可参看 5 2 1 ) r a b i n b s 证明了r 。( q ，) = n + 1 2 n 一维环面网络c ( d 1 d 2 ，如) 其顶点为礼元组( z 1 ，z 2 ，z 。) 其 中0s ：c i l 则g b ( d 礼) 是h a m i l t o n i a n 图，如果a = 1 则g 8 ( 2 ，扎) 不 是h a m i l t o n i a n 图 d u h s u 和h w a n g 等：拍】证明了如果a = 1 ，d 2 ，则 a s ( d 肠) 是h a m i h o n i a n 图，至此广义d eb r u i 曲网的h a m i l t o n 性问题被完 全解决了关于d eb r u i i n 网的直径、宽直径和错直径问题至今还没有完全 解决，已知l i ，s o t t e a u 和x u ( 1 9 9 6 ) ! d o i 给出了一l eb r u i j n 网的2 一直径 ( 2 ) 蝶形网 , b u t t e r f l yn e t w o r k j b 。c a o ，d - h s u 和w a n ( 1 9 9 5 ) 1b i 给 出了b 。的连通度。直径，错直径和宽直径及r a b i n 数的上下界，他们证明 了k ( b 。) = 2 d ( b 。) = 2 nd 2 ( b ，。) = 2 n + 2 ，2 n + 2s 也( b 。) 2 n + 4 和 2 n + 2 r 2 ( j ) 2 nj 一4 l i a w 和c h a n g ( j 9 9 9 ) 1 0 9 ，0 8 j 证明了d 2 ( b 。) = 2 n + 2 和7 2 ( b 。) = 2 n + 2 ( 3 ) c c c 网( c u b e c o n n e ：t e d c 、+ t i en e t w o t k i c 。可容易地证明( g k ) = 再一霉绪论 3 和d ( g ) = f 丑粤 k r i s h n a m o o r t h v 和k r i s 1 n a m u r t h y ( 1 9 8 7 ) 【5 l 】证明了 d 3 ( g ) 掣1 4 循环网络( c i r c u l a n tn e t w o r k ) g ( n ；a )熟知循环网络可看成加群 磊关于其子集的有向c a y l e y 图当n = d “，a = ( 1 ，d ，扩_ 时，记为g ( d “：4 ) h a m i d o , m e ( 1 9 8 4 ) 3 0 】证明了k ( g ( d 5 4 ) = n 易证 a ( g ( d _ ) ) = ”( f f 一1 ) h s u 和l v u u ( 1 9 9 4 ) 4 4 1 和d u h 和c h e n ( 1 9 9 7 ) 2 4 1 证明了d 。( g fr “。 ) ) = y n ( g ( “”4 ) ) = n ( d 一1 ) + 1 l i a w ，c a o ，c h a n g 等 ( 1 9 9 8 ) b u l 证明了 。c gc a “- ，= a 。c g c 扩：。a ，= ：；：二：；+ ，。l 3 5 第一章堵论 1 叫 扎一1 u = n 9 广义超立方体网络g h ( m 。- ，m o ) ( 参看t 1 2 ) 其直径为 d ( g h ( m 。一h 一，m o ) ) = n d u b c h e n 和h s u ( 1 9 9 6 ) 2 6 证明了 n 一1 ( g h ( m ，- ，m ) ) = ( m ，一1 ) = k i = 0 和d k ( g h ( m 。小、m o ) ) = 1 7 , + ll i a r 和c h a n g ( 1 9 9 9 ) 。u 完全解决了广 义超立方体网络的广义直径问题，证明了 d 。( g h ( m 。一1 、t o o ) ) = d 。( g h ( m 。一1 ，t o o ) ) = r 。( g h ( m 。一1 - - - m o ) ) f n ， l 叫n 一1 i n = n 并且至少存在两个m ，3 in + 1 、= n 并且至多存在一个m ：3 【n + 1 ，订+ 1 兰州s ：；l ( m 。一1 ) 1 0 折叠式超立方体网络( f o l d e dh ) ，p e r c u b e ：e t w o r k s ) f h ( n ) ( 参看 2 7 1 ) f h ( n ) 是超立方体网络q 。的加强，其连通度为 ：( f 日( n ) ) = n + l 是( n + 1 ) 正则图，e l a m a w 3 和l a t i f i ( 1 9 9 1 ) 引! 证明了d ( f h ( n ) ) = f ； ，1 9 9 5 年d u h ： c h e n 和f a n g ：2 5 证明了d d + ( f ( ) ) = f ；1 + 1l i a w 和c h a n g 5 9 证明了 。c f hc n ，= d 。c f h c ，= f ； + 。， i 兰翥! ： 1 1 扭立方体网络( 坩i s t e dn c u ) e ) f 3 0 在文献【8 0 中，作者证明了扭 立方体网络t n , 。为n 一正则九- 连通图且其直径为d ( t a _ ) = 学1 现在为 止还没有看到关于扭立方体网络广义直径的结果 1 2 w k 一递归网络w ( dt ) ( 可参看【7 0 ) c 1 l e n 和d u l l ( 1 9 9 4 ) 1 7 证明 了d ( h x ( dt ) ) = 2 一l ( 凡f d f ) ) = d 一1d , i l ( 1 1 k ( d ) ) = 32 一1 g + 一 一 ，j、 = n 了 硼 w 锄 = g ； 川 姻 斟 f a k c | | 和 ” n 抓 d l ed l l 一 + 1 n 瞪s 一 三 一 一 nfr 和 第章绪论 l a w 和c h a n g ( 1 9 9 9 1 证明了 。c w7 c a ，t ，= a 。c t r kc 一t ，= r 。c w k c d t ，= ；。j 。：l ，w ：= 叫1 1 s 。一。 1 3 有限群的c a ) l e ) 图关于这类网络直径和宽直径已知结果不多 特别是关于宽直径这方面的文献可参阅t 5 4 本论文内容安排如下： 第二章研究了一正则女- 连通图，广义p e t e r s c m 图和置换图的宽直径 ( 1 ) 令 ，( n ，k ) = m a x d ( g ) g 是有n 个顶点自0 一正则k - i g 女! i e ) h s u 和l u c z a k 在文h 州中对函数，( n k ) 的取值作了讨论，本文给出一个 作图的算法，利用该算法可以构造具有最大直径的一正则 一连通图，并 且得到了文一谚没有得到的，( ) 的值 ( 2 ) p e t e r s e n 图是圈论中我们熟知的图，广义p e t e r s e n 图，记为尸( m ，o ) ， 是有2 m 个顶点的图，其顶点集为 t j o ，“h - u 一“o ，h 一， 。一1 ) ，边有 点对( u i u ，) ( t l i “，一1 ) ( u , iu i 一1 j ( w i ，+ 。) 和( 。“，一。) 给出，0 is m 一1 这里下标的运算都是在模m 下的运算这个推广是c o x e t e r l l 8 1 1 9 5 0 年给出的显然：p ( s ，2 ) 就是p e t e r s e n 图，本文证明了p ( m ，2 ) 的直径和 3 一直径分别为0 ( 乎) 和o ( 罟) ( 3 ) 用g 表示有限简单图，其顶点集为。，t ，2 ，u 。，用r 表示集合 1 2 、n ) 上的对称群，o s 图g 的生成图，记为r ( g ) ，有g 的 两个不交的拷贝，分别记为g 和g 组成，g 和g7 有边e ：= 。抓1 相连， r ( g ) 也称为置换图文【姐：中对跫换图的连通度、直径等参数做了研 究本文研究了置换图只( g ) 的宽直径和图g 的宽直径之间的关系，也给 出p 口( g ) 的2 一直径和g 的直径之间的关系 第三章重点研究了k - 正则k - 连通图的k - r a b i n 数和一广义直径g d ( g ) ( 1 ) 网络g 的一r a b m 数记为r w i g ) ，是指最小的f 使得对任意的 + 1 个顶点r “ 轧，存在 条长至多为f 的从z 分别到l ，y 2 ， 的内部点不交的路 9 8 9 年，r a b i n 在文i b 。l 中对钳= k ( g ) 的情形作了 研究一般的定义有h s u1 9 9 4 首次给出近几年来，“a 、，和c h a n g 给出 舅一掌堵沦 了一些特殊网络的r a b i n 数，例如蝶形网、循环网络超立方体网络、广义 超立方体网络、折叠式超立方唪网络、d a r y 超立方体网络和w k 一递归网 络等 a 9 ，。8 1 本文对一般的正则k - 连通图的r a b i n 数作了研究，证明了n 个顶点的正则k - 连通图的r a b l n 数至多为；并且当几= 2 k 一3 + z ( k 一2 ) 时，该上界是不能改进的 ( 2 ) 设图g = g ( o je ) 为，个顶点的简单图且k ( c ) = k ，s ，t 为v ( g ) 的任意一对不交的子顶点集且【一= | s ! i t = f 曼设r ( s ，t ) 为连接s 和丁的u 条内部点不交的路族，即 r ( s t ) = ( p t p 2 ，t ，p ，j ) l p t i l 尸2 ls - i r 且s 和丁中每一顶点至少是这些路的一个端点s 和t 间的广义w - 宽距 离( 或简称为广义 距离) 记为9 d 。( s ，丁) ，指最小的i r | 1r 取遍所有的 只。( s 丁) ，图g 的广义w 一宽直径( 或简称为广义i f - 直径) 记为9 如( g ) ，定义 为最大的一宽距离口d 。( s ，r 1 g r z 。( s 丁) 取遍v i g ) 的所有不交子顶点集对 s ，r 且s = i s si t | = t ws ( g ) 我们主要考虑了正则k - 连通图的 广义“直径给出g d k ( g ) 的一些性质并且证明了n 个顶点的女一正则k - 连 通图的广义k 直径至多为n 2 当儿= 2 k 一3 + z ( k 一2 ) 时，该上界是可以 到达的 第四章研究丁三环网络环网络广泛应用于计算饥局域网设计和各种并 行处理系统由于有向单环网络连通性差( 连通度为1 ) 和传输延迟时间长 ( 直径可达n 一1 n 为其节点数目) 为了克服其缺点，引进了多环网络( 该网 络也就是具有多个生成元的循环群的c a y l e y 图) 用表示环网络节点的 数目，记环网络为g ( 。1 b 2 8c ) 其中每个节点f 和a + l ，十8 2 ，- - ，i + 8 1 ( m o dn 1 分别相连主要问题是找到一个好的网络拓扑g ( v ；1 q 2 - ，s f ) 使 得其直径最小1 9 7 4 年，v o n g 和c o p p e l s m i d l l 证明了环网络直径的 下界为、7 一业岩当= 2 时，环网络称为双环网络，f = 3 时称为3 环网络，以此类推1 9 8 7 年，f i o 和y e b r a 等p z 】利用l 一型瓦模型，改进 了双环网络直径的下界，对任给的| v ，得到优的双环网络1 9 9 3 年，李乔 和徐俊明等- f 4 提出一种找到紧洗和几乎紧优双环网络的构造方法 1 9 9 9 年，徐俊明在文i 中进一步发展了文【h l 的方法 1 9 9 2 年，e r d j s 和 h s u t 2 9 1 首次用数论和组合的方法来解决有最小悖输延迟和最大连通度的网 络，该方法不仅可以处理双环网络的情形而且可统一处理多环网络本文重 8 点研究了三环网络，给出其直径的上界，并给出不太大时，三环网络取 得最优的一个条件 第五章给出关于折叠式超立方体网络的一点注记网络的可嵌入性是衡 量网络性能好环的一个重要标准，因此如何将一个较小的网络嵌入到一个大 的网络中去成为网络设计中需要考虑的一个重要问题超立方体网络是一种 具有较好嵌入性的网络，文献：6 8 i 中作者证明了如何将环网络和平面网格结 构嵌入到超立方体中，但不幸的是超立方体网络中不含有长为奇数的圈，因 此我们不能将长为奇数的圈嵌入到超立方体中本文定义了折叠式超立方体 f h ( n ) ，证明了折叠式超立方体的直径约等于超互方漆直径的一半，( n + 1 ) 一 宽直径为n 比一立方体的n 一直径小1 我们还证明了f h ( n ) 中包含长为奇 数的圈，并给出了一个嵌入长为奇数的圈到折叠式超立方体网络中的算法 下面列出一些常用符号，如果没有特别说明，在本文中这些符号采用下 述意义 g ：有限连通简单图 g ) 图g 的顶点集 g ) 图g 的边集 k ( g ) ：图g 的连通度 d ( g 1 ：图g 的直径 g d e i g ) ：图g 的广义- 直径 比( g ) 。图g 的宽直径f 也称a 一直径) r o ( g ) ：图g 的k l ： a b i n 数 g s ：由顶点集 ( g ) s 生成的图g 的导出子图 ! 4j ：集合4 的基数 1 p i ：路尸的长 n ( z ) ：和顶点z 相邻的顶点的集合 f n b ：整数集合 x l o zsb 舅：，2 元集合上的置换群 9