（应用数学专业论文）图的宽直径与相关参数的关系.pdf

电子科技大学硕士学位论文 摘要 图的某些参数，如连通度和直径，不仅在图论和组合数学本身十 分重要，而且因他们与通信网络的容错性和传输延迟密切相关而在其 它领域被广泛研究.随着超大规模集成电路技术和光纤材料科学的发 展，使我们有能力设计大型并行处理计算机系统和快速，复杂的通信 网络.这些系统不仅要求我们研究涉及图的的连通度和直径的网络中 两个节点间的单条路径， 而且要研究两个节点或两个节点集间的内部 点不交的多条路径这自然引导人们把图的直径推广，而宽直径，容 错直径和 r a b i n数等概念都是直径的推广. 本文主要研究网络图特别是环网络的宽直径及其相关参数之间 的关系.其主要工作包括以下几个方面 1 . 得到了双环网g ( n ; l , s ) 的2 一 宽直径和r a b i n 数. d 2 ( g ( n ;l , s ) ) 5 d l + 1 , r 2 ( g ( n ;l , s ) ) s d l + 1 2 . 得到了无向双环网c ( n ; a , b ) 其中a , b 是n 因子且互素) 的不同构 的图的个数和 4 一 宽直径 llj 月土 十 nl占 d 4(c (n;a,b)一 卫 十 竺一 2 3 . 根据双环网的对称性和传递性得到了另一类循环网 c ( n ; l , a ) 的 4 一 直径的上下限， 同时通过计算特殊点间( 0 到 1 , 2 , a ) 的宽距离的运算得 到当给定步长时c ( n ; l , a ) 的4 一 宽直径的准确值. 4 . 得到了循环网c ( 2 n ; i , n ) 的容错直径. 5 . 讨论了函数 h ( n , k , d ) 关键词连通度;直径;宽直径:r a b i n数 电子科技大学硕士学位论文 abs t r a c t g r a p h p a r a me t e r s s u c h a s c o n n e c t i v i t y a n d d i a me t e r h a v e b e e n s t u d i e d e x t e n s i v e l y d u e t o t h e i r i n t r i n s i c i n g r a p h t h e o r y , c o n b i n a t o r i c s a n d t h e i r r e l a t i o n s t o ( a n d a p p l i c a t i o n i n ) f a u l t t o l e r e n c e a n d t r a n s mi s s i o n d e l a y i n c o m mu n i c a t i o n n e t w o r k s . t h e a d v e n t o f vl s i t e c h n o l o g y a n d f i b e r o p t i c s m a t e r i a l s c i e n c e h a s e n a b l e d u s t o d e s i g n ma s s i v e l y p a r a l l e l p r o c e s s i n g n e t wo r k s . c o mp u t e r s y s t e ms a n d f a s t a n d c o mp l i c a t e d c o mmu n i c a t i o n s a l l t h e s e s y s t e ms i n c r e a s e t h e i r r e l i a b i l i t y b y s t u d y i n g ( a mo n g o t h e r ) t h e e x i s t e n c e o f t w o ( o r m o r e ) d i s j o i n t p a t h s c o n n e c t i n g a n y t w o n o d e s . t o s a t i s f y a l l t h e s e d e ma n d s , w e g e n e r a l i z e d i a me t e r o f g r a p h s . w i d e - d i a me t e r , f a u l t - d i a me t e r a n d r a b i n n u m b e r i s t h e g e n e r a l i z e d i a me t e r . i n t h i s p a p e r , w e ma i n l y s t u d y g e n e r a l i z e d w i d e - d i a me t e r o f d o u b l e l o o p n e t w o r k s a n d t h e r e l a t i o n s o f g r a p h p a r a me t e r s . i n t h e f o l l o w i n g , w e l i s t t h e ma i n w o r k s o f o u r p a p e r . 1 ， we s t u d y t h e w i d e - d i a me t e r a n d r a b i n n u mb e r o f d o u b l e l o o p n e t w o r k c ( n ; l , a ) . d 2 ( g ( n ;l , s ) ) 5 d c + 1 , r , ( g ( n ;l , s ) ) _ d r + 1 2 . we f i n d t h e n u m b e r o f d o u b l e l o o p n e t w o r k s c ( n ; a , b ) w h i c h n o t i s o m o r p h o u s a n d t h e p a r a me t e r s w h i c h a r e r e l a t e d t o w i d e - d i a m e t e r d , ( c ( n ; a , b ) ) = m a x n n。 刀 一十丁一乙 ， 丁+1 a d d 3 . b e c a u s e d o u b l e l o o p n e t wo r k i s s y mme t r i c a n d v e r t e x - t r a n s i t i v e we f i n d t h e v a l u e o f t h e 4 - w i d e d i a me t e r o f c ( n ; l , a ) i f w e c a n s o l v e wi d e - d i s t a n c e b e t we e n n o d e 0 a n d n o d e s 1 , 2 , a . are t he 4 . we a l s o s t u d y t h e f a u l t - d i a me t e r o f c ( 2 n ; l , n ) 5 . we d i s c u s s t h e f u n c t i o n k e y wo r d s c o n n e c t i v i t y ; d i a me t e r ; o f h ( n , k , d ) . wi d e - d i a me t e r ; r a b i n n u mb e r 1 1 电子科技大学硕士学位论文 常用符号表 如果没有特殊说明，在本文这些符号采用下述意义: g : 连通有限简单图 v ( g ) 图g的顶点集 e ( g )图g的边集 k ( g ) : 图g的连通度 d ( g ) :图g的直径 人( g ) : 图g的k - 宽直径 ( 也称k 一 直径) r k ( g ) : 图g的k - r a b i n 数 g - s :由顶点集v ( g ) s生成的图g的导出子图 ja i : 集合a的基数 in : 路p的长 a , b 3 : 整数集合 x i a v ) j 定 义1 . 1 .2 e 1 图g 的k 一 宽直 径d k ( g ) 是指当 点“ ， ; 取遍点 集 v ( g ) 时 最 大的宽距离d k ( u , v ) . 即 d , ( g ) 一 m a x ld k ( u , v ) d u , v e v ( g ) j . 定义1 . 1 . 3 1 图g 的 ( k - 1 ) 一 容错 直径d , ( g ) 是指当图 有k - 1 个点出错 或 失效时图的直径.即 d w ( g ) = m a x d ( g 一 s ) : i s 1_ w 一 1 . 定 义1 . 1 .4 i4 1 图g 的w - r a b i n 数r , ( g ) 即 为 最小的l 使 得 任意、 + 1 个 不 同的顶点x , y l i y 2 , . . ., y w ， 存在w条x 到y y 2 ， 二 ， y ， 的内部点不交的长至多 为 1 的路. 对宽直径，容错直径和 r a b i n数有下面的基本性质 性质1 . 1 . 1 4 1 g为连通图 ， 则 ( 1 ) d , ( g ) d 2 ( g ) d k ( g ) ( 2 ) d , ( g ) d 2 ( g ) 一 d , ( g ) ( 3 ) r , ( g ) _ r 2 ( g ) 二 r , ( g ) ( 4 ) d . , ( g ) d ( g ) ， d w ( g ) _ r . , ( g ) 1 . 2几类常用网络的宽直径 宽直径是在研究并行技术，分布式计算机网络的路由，可靠性，容错 和其它通信协议中提出来的， 是结合度量通信延迟和容错的两个重要参数 直径和连通度的新参数自1 9 9 4 年d . f . h s u 提出宽直径以来引起了国内外 数学工作者与计算机工作者的关注，特别是对特殊网络的研究进展较快. 而互连网络通常采用特殊的网络，即网络拓扑有一定的规范性，根据不同 的需求建立不同的连接方式， 这样便于对源结点和目的结点进行分析，寻 找信息传输路径，控制传输时延，提高一定的容错性能， 本节介绍几类常用的互连网络及近几年这些网络的参数研究结果 第 3页 共 4 6页 电子科技大学硕士学位论文 ( 1 ) 蝶形网络b ( b u t t e r fl y n e t w o r k ) b 。 的顶点集v ( b n ) = x = ( x o , x . . . . . . x 。 )10-x, _ n , x , e 0 ,1 ,o s i _ n ， 弧集 e ( b j = ( x , y ) i y o = x o + i 且 x , = y1 5 i 2 滚 ( b) = 2 , d ( b) = 2 n , d 2 ( b) = 2 n + 2 2 n + 2 d 2 ( 氏) x 2 ， 一， x , ) i x , e 0 , d - 1 ; 点( x 1 ， x 2 ， . i x , ) 与( x i ， x 3 , * , x, a ) 邻接，其中。 e 0 , d - 1 . b ( d , n ) 有d ” 个顶点. i m a s e , s o n e o k a 和c k a d a 9 证 明了b ( d , n ) 的 参数d d _ 1 ( b ( d , n ) ) = d , _ , ( b ( d , n ) ) = n + 1 = d ( b ( d , n ) ) + 1 . 图 1 . 2 . 2 : b ( 2 , 3 ) 无向 d e b r u i j n网u b ( d , n ) 的顶点v = ( x i , x 2 , 二 ， x) i x , e o , d - ; 点 ( x i , x 2 ， 一 ， x ) 与( x 2 ， x 3 ， . . , x , a ) , o, x i . x 2 ， 一 ， x _ , ) 邻接， 其中a 渭e o , d - 1 . e s f a h a n i a n和 h a k i m i 1 0 得到k ( u b ( d , n ) = 2 d - 2 = s ( u b ( d , n ) ) . p r a d h a n和 r a d d y 得d d ( u b ( d , t ) ) 2 n 广 义d e b r u ij n 网 g b ( d , n ) 是 指 顶 点 集为v ( g ) = ( 0 ,1 ,2 , . . . , n - 1 ) ， 弧 集 为 e ( g g ) = i - a i n + a m o d ( n ) , a 。 o , d 一 1 1 的图 第 4页 共 4 6页 电子科技大学硕士学位论文 广义无向d e b r u ij n网u g r ( d , n ) 是有向广义d e b r u i j n 网g , ( d , n ) 中的 弧用无向边代替 ，取消 自环和重边所得的图. h e n r y e e s c u a d r o和f e l i x p m u g u 1 1 证明 广义d e b r u ij n u b ( n , n 2 ) 的 相关参数: 当。 2 时，u b ( n , n 2 ) 是2 ( n - 1 ) 一 正则且k ( u b ( n , n 2 ) ) - 3 时d ( u b ( n , n ) ) = 2 . 当n - 4 时k ( u b ( n , n 2 ) ) = 2 ( n - 1 ) , d . ( u b ( n , n 2 ) ) = 4 其中w = 2 ( n - 1 ) . c a r o 等 1 2 证明了 当n - 2 时d 2 ( - , ( u b ( n , n ( n + 1 ) ) ) = 5 . ( 3 ) k a u t z 图k ( d , t ) 顶 点 集 v ( k ( d , t ) ) 一 (x , , x 2 ， 一 ， x , 二 。 0 , d l x , # x ，十 ， ， 点 ( x x z , . . ， : ，) 与 d 个顶点( x z , x 3 , . . . ， x ， ， a ) 相邻，其中。 c m 0 , d x , . k ( d , t ) 是有d 十 d - ， 个顶点的直径为t 的d - 正则图d - 连通图 d u d . z , h s u d .f . 和场u u y . d在 6 中证明了 d d (k (d ,t，一 d d(k (d ,t)一 + 子 r+ 1 t 3 1二 2 5 中进一步得到 k ( d ,l ) 是d + 1 个顶点的完全对称有向图， 并且k ( d , t ) 是k ( d , t - 1 ) 的线图. 如果x , y 是k ( d , t ) 任意的两点，则x 到y 的d 条点不交路中一条长至 多为t ; d 一 2 条路长至多为1 + 1 ; 一条长至多为t + 2 无向k a u t z 图u k 似, t ) 是顶点集为v ( k ( d , t ) ) ，点( x x-, x ) 与2 d 个 第 5页 共 4 6页 电子科技大学硕士学位论文 顶点( x2， x 3 ， . . . , xa ) , ( p , x z , x 3 ， 一 ， x ) 相邻，其中a e o , d x , q # x z . 李乔 5 4 证明了无向 k a u t z图u k ( 2 , t ) 的限制性连通度k ( u k ( d , t ) = 4 k 和p r 制性容错直径d , ( u k ( d , t ) ) s t + 1 4 ( t _ 3 ) . k ( d , t ) 图的可变直径 ( 5 1 3 ) ) t 1 t +1 t +l t +2 以 s=0 d ( s ; k( d , t ) ) 0 _s 5d一1 且t 二1 1 3 1!一 - ( 4 ) n 一 维超立方体( h y p e r c u b e ) 么 n 一 维超立方体么是一 个具有2 ” 个结点的图， 各结点用一个二进制数 字来表示 两结点相邻接当且仅当只有一个地址数字不同. q n 相 关参数 i d ( q j = k ( q n ) 一 n , d ( q) = n + 1 , d_ , ( q) = n + 1 ( n _ 3 ) + ;, ( 忿) = n + l . 1 9 9 3 年s h a h r a m l a t i f i 和s e n i o r me m b e r 1 6 得到n 一 维超立方体么中 的任意两点间的路由问题， ( 1 ) q 。 中的任意两点 u , ，之间的n条点不交路中d h ( u , v ) 条长为 d h ( u , v ) , n - d h ( u , v ) 条长为d ( u , v ) + 2 ， 其中d ( u , v ) 是u , v 汉明 距离; ( 2 ) 限制性容错集 q 。 有2 n -3 个失效点，则 a ) 任一 对汉距离为n 的两点u , v 有d p ( u , v ) = d h ( u , v ) = n( 注: d p ( u , v ) 是u , v 之间的最短有效路长) ; b ) 任一 对汉明 距离为n - 1 的 两点u , ， 有d p ( u , v ) _ n + 1 ; c ) 任一 对汉明 距离为n - 2 的 两点u , ， 有d p ( u , v ) _ n + 2 ; d ) 任何点 对u , ?有d p ( u , v ) _ d u ( u , v ) + 4 ; d 2 - , ( q , ) = n + 2 . ( 5 ) d 维立方体( d - a r y n - c u b e ) 第 6页 共 4 6页 电子科技大学硕士学位论文 c ( d , n ) 是具有 d 个顶点的图， 其结点为 ( x n - i , x - 2 1 . . . , x o ) . 其中 0 5 x ; 5 d - 1 , o s i 5 n - 1 . ( x _ x _ 2 , . . , x o ) 与( x n _ . . , x ， 一 ， x ! + 1 , x j ， 一 ， x o ) 相连 ( 0 - j - n - 1 ) ， 其中加法为模d 的加法， l i a w和c h a n g 1 4 如果d ? 2 且1 - w - n ， 则 d w(c (d ,n) = d(c (d,n)，一 rw(c (d ,n)= ,(d 1)in(d - 1) + ， 1 5w_ 2 0 _ i _ n 一 1 ，则 d w ( g h) = d ( g h ) = r , ( g h ) n n 儿+i n+l i _ 3 n + 1 、 艺 二 ( m ， 一 1) r，.口eslleslzi -一 ( 7 ) 折叠式超立方体( f o l d e d h y p e r c u b e s ) 在超立方体的基础得到的折叠式超立方体 f h ( n ) 是连通度为 。 + 1的 ( n + 1 ) 一 正则图. 第 7页 共 4 6页 电子科技大学硕士学位论文 e i - a m a w y 和l a t i f i 3 9 证明了 d ( f h ( n ) ) = r n / 2 1 ; 1 9 9 5 年d u l 和f a n g 1 9 证明了d d . i ( f h ( n ) ) 一 卜 / 2 飞 + 1 ; l i a w和c h a n g 在 1 4 证明了 r w ( f h ( n ) ) _ d ( f 万( 。 ) ) = d w ( f h ( n ) ) = f n / 2 当 1 、 w 、 r n / 2 一 1 时 r n / 2 1 + 1当 f n / 2 1 _ w : 。 + i 时 而网络h f n ( n , n ) 是以超立方体为基本模型 图 1 . 2 . 4 d . r . d u l 等在 1 9 得到h f n ( n , n ) 的一系列参数 d ( h f n ( n , n ) ) 一 2 r n / 2 1 + i k ( h f n ( n , n ) ) 一 n + 1 d , , ( h f n ( n , n ) ) 一 几 十 ; ( h f n ( n , n ) 二 2 r n / 2 1 + 3 . h u a n g l i e 讨论了 另 一种超网 络( t w o - l e v e l h y p e r n e t n e t w o r k ) h n ( d ,2 ) . 点 集v = l( b 2 d - 2 ad - 3 , ， 二 ， b o ) i b 。 0 ,1 ) , i 0 ,2 d 一 2 , d 2 . 点( b e d - 2 , b 2,1- 3 , . . . , b o ) 与 ( b e d - 2 , b 2 d - 3 , . . . ， b . i , b . ， b ,- : ， . . . ， b o ) 或( b d - ， . . . ， b i , b 2 d - 2 , - . , b d b o ) 相邻接. 当d ? 3 时d= 2 d + 1 = d ( h n ( d ,2 ) ) ， d , _ , ( h n ( d ,2 ) ) = d d - z ( h n ( d , 2 ) ) = d+ l ; jij11、 -一 d d ( h n( d , 2 ) ) = 马- , ( h n ( d , 2 ) )_ 1 0 u 十2 d=3 d ) 3 ( 8 ) wk 一 递归网络wk ( d , t ) c h e n 和d u l 在 1 9 9 4 年 4 0 证明了 d ( w k ( d , t ) ) = 2 一 1 ，k ( w k ( d , t ) ) = d 一 1 , d ,_ , ( w k ( d , t ) ) = 3 x 2 一 ， 一 1 ; l i a w和c h a n g 1 9 9 9 年 1 4 进一步证明 第 8页 共 4 6页 电子科技大学硕士学位论文 d ( w k ( d , t ) ) = d w , ( w k ( d , t ) ) = r w ( w k ( d , t ) ) = 2 ， 一1 3 . 2 ， 一1 w =1 2w d一1 ( 9 ) 循环网 络 ( c i r c u l a n t n e t w o r k ) g ( n ;a ) 循环网络可以 看成为加群z 。 关于 其子集a的有向c a l e y 图 当n= d , a 二 1 , d , d z , . . . , d - 时g ( n ;a ) 记为g ( d 汹 ) . 如图1 .2 . 5 . 图 1 . 2 . 5 : g ( 1 6 ; 1 , 4 ) 1 9 9 4 年h s u 和l y u u 1 证明了 d ( g ( d ; a ) ) = n ( g ( d ; a ) ) = n ( d 一 1 ) + 1 l i a w , c a o 和c h a n g 1 9 9 8 年 4 2 证明了 d , (g (d ; a )= d w(g (“ 一 “ ，= n ( d 一 1 ) n ( d 一 1 ) + 1 1 5w n一1 w 二 二 n l i a w和c h a n g 在 1 9 9 9 年 1 4 得到其r a b i n 数: 二 (g (d 一 ， )一 n ( d 一 1 ) n ( d 一 1 ) + 1 1 互w _n一i w二 二 月 = 1 ,2 , . ., n )两个点相邻接当且仅当第 1 个符号与第 i 个符号对换，即 ( p i , p 2 , . ., p i 二 p . ) 与: ()= ( p , , p 2 ， 二 ， p ,- ,.p , , p i. i ， 二 ， p) 相邻 第 9页 共 4 6页 电子科技大学硕士学位论文 !il，:， 图 1 . 2 . 6 b 3 g 。 有n ! 个顶点，n !( n - 1 ) / 2 条边. g u q i a n p i n g 1 5 7 1 d . - i ( g . ) = d ( g) + 1 , r n - , ( g ) 、 d ( g ) + 4 , d ( g n ) = l 3 ( 、 一 1 ) / 2 n 维不完全星图g , , ( i n c o m p l e t e s t a r g r a p h ) ( 1 _ m 5 n ) 有m x ( n - 1 ) ! 个 ( n 一 2 ) m 2 x ( n 一 1 ) i + m ( m一 1 ) 2 x ( n 一 2 ) ! 条 边g。 一 ( s n m , 瓦 .m ) s , 。 一 ( p . p 2 , ., p n ) i ， 。 。 ， 、 。 - p , i ， n , p ， ， ， ， ， ， ， e ,。 一( ( p l , p 2 ,. ., p ) , ( p , , p 2 ,., p ,- i , p i , p ,. , . , p a i ( p p 2 , .二 ， p ) 。 s ,n ( p p 2 , , p ，一 ， , p , p ,. i ， 二 ， p ) e s , ，2 i n 由图的构成知:g. = 民- i i g _ = g , . d (g 】一 一 “ (g ， 一 3(n - 1)j2 2-m s 一 s i , s 2 ， 二 。 s x k v ( h )和 沪: e ( g ) - 4 e ( h )， 使 得 v g ( e ) = u v当 且 仅 当 b ( u ) b ( v ) . 2 . 1 . 3环网络g ( n ; s s . . . . . . s , ) 是一种循环正则图，其结点集合用 v = z = 0 ,1 , 2 ， 一 ， n - 1 表示， n是自 然数， 下面的加法为模n的加法，弧集 第 1 2页 共 4 6页 电子科技大学硕士学位论文 e ( g ) = ， 一i 斗 si + s 2 ， 二 ， i + s k : i = 0 ,1 ， 二 ， 刀 一 1 , 0 s , s 2 一 6 , g c d ( n , s s 2 ) = 1 且s , s 2 i + 1 , i + s : i = 0 ,1 , . . . , n- 1 ) ,其中加法为模 n 的加法 如1 a 便g ( n; l , s ) n 直径达到最小而n尽可能大， 1 9 7 4 年w a n g和c o p p e r s m i t h 4 4 采用l 型网格的方法得到g ( n ; l , s ) 的 直径d = m a x ( dd 2 ) , d , = m + p + q - 2 , d 2 = m + n + q - 2 ，其中。= n - z , : = h 一 z , p= y + z 一 n，q = : ，r ( x ) = x ( m o d n ) , h = m i n ( i r ( i s ) i + 1 ) ， z= m a x r ( z s ) 0 z h ) ，y=m i n r ( i s ) 】 0 - l , u = v = - l ; w ( 9 u 2 + 7 ) / 2 4 , u为奇数 且， = ( u + 1 ) / 2 ; w 3 u 2 / 4 + v , “ 为偶数且u / 2 - v _ u / 2 + 1 则: = 3 w ( 3 ) n= 3 w 2 + 3 w ， = 3 w + 2 . ( 4 ) n= 3 w 2 ，d ( n ; 1 , 3 w 一 1 ) = 3 w 一 i . b e r m o n d 2 0 1 得到部分双环网络的直径和平均距离 d ( n ;1 ,- 2 ) = n 1 3 + l ， d ( n ;1 ,- 2 ) = n / 6 , d ( t 2 ;l , t ) = 2 t - 2 ， d ( t 2 ;i , t ) 一 t - 1 对于一般的双环网g ( n ; s , , s 2 ) 给定顶点数如何确定步长s s : 使 g ( n ; ss 2 ) 为最优网络. f . a g u i 1 6 , m . a . f i o l e3 4 1 和 刘焕平等 i s 7 分 别从 几何和 代数的 角度给出 第 1 4页 共 4 6页 电子科技大学硕十学位论文 构造最优网络的有效算法. 由于环网络的点传递性和对称性. 不妨设 s , 0 , s 2 0 . 因为若s , 0 , s 2 0 ，则g ( n ; ss 2 ) = g ( n ; sn - s 2 ) . 其他情 形完全类似. f . a g u i 1 6 , m . a . f i o l 13 4 1用几 何l 型 直 得到g ( n ; ss 2 ) 的 直 径 d ( n ; ss 2 ) = d , = m a x ( 1 + h 一 w , l + h 一 y 一 2 ( l 型的构造如图2 . 2 . 2 ， 不妨记向右步长为s 2 ， 向上步长为s , ) 顶点数n ( l , h , w , y ) = 1 h - w y ，不妨设0 _ w - y 5 h , 0 - w- 1 . 则当给定 直径d= d ,. = 1 + h - w - 2 时，n ( l , h , w , y ) = 1 h - w y 在条件d= l + h - w - 2 和 0 - w - y - h , 0 - w s 2 ) 是2 一 连通图 . u , v 为图中 任意两点一定存在点 x 使d 2 ( u , v ) = d 2 ( 0 , x ) . l 型网格内的点x - is . 十 j s 2 ( m o d n ) = r ( i s , + a) ， 记 a = r ( is , ) ! 0 is , - i s , 十 s 2 -4 is , + 2 s 2 - - - i s , + j s 2 ; 0 - - s 2 - -二 - j s 2 - - s , 十 j s , - 2 s , + j s , 分峥i s , + i s , ， 故有d 2 ( o , x ) s i + j ( 2 ) 若a e a , a = r ( is , ) , 0 2 s , - - - is , ;o -s 2 - - u 一a t。 - s , - 今” -b 故有d 2 ( 0 , b ) m a x 仃 ， d ( o , v ) + 1 ) 当a , b , x 分别取遍a , b , x ，则由宽直径的定义得 d , ( g ( n ; s , , s 2 ) ) = d l + 1 2 . 2 . 3 环网g ( n ; s s , ) 的r a b i n 数 定理2 . 2 . 2 环网g ( n ; ss 2 ) 的r a b i n 数r 2 ( g ( n ; ss 2 ) ) = d c + 1 证明 考查点。 到g中任意点集t = u , v 的内部点不交路 ( 1 ) 若u , v 不同时在点 集a或b 中， 设u = r ( i, s , + a s 2 ) , v = r ( i 2 s , + j , s 2 ) 路径如图2 . 2 . 3 。 i. 2 .1 .4 困 121 p ( 0 , u ) : 0 a s , - - -i , s l - - 7 i s l + s 2 -i , s , + 2 s 2 - 二 - - i , s , + a s 2 = “ 第 1 6页 共 4 6页 电 子科技大学硕士学位论文 p ( o , v ) : 0 - s 2 - 一- j 2 s 2 - - s , + j 2 s 2 - 2 s , + j 2 s 2 - - 2s, + j 2 s 2 = v ; d 2 ( 0 , t ) = m a x i, + ji 2 + j 2 卜d , ( 2 ) 若u , v 同 在a 或b中，不妨设u , v 同 在a中 且u = r ( is , ) , v = r ( j s , ) 其中0 i ( i 一 1 ) s , - i s , = 、 ; p ( o , v ) : 0 - s 2 - - ， ， - z - v d 2 ( 0 , t ) 二 m a xi , d ( 0 , z ) + 1 1 人+ 1 若u , v同在 b中类似于同在a中的讨论. 综上所述可知d 2 ( o , t ) s d l + 1 . 故r 2 ( g ) = d l + 1 2 . 3 双环网络c ( n ; ss 2 ) 2 . 3 . 1 双环网络c ( 从s s 2 ) 的结构 双环网c ( n ; s s 2 ) 是无向环网络. 具有顶点v = z n = 0 ,1 , 2 , . . . , n- 1 ， 点 i 与i 士 s i 土 s 2 相邻接. 为简单起见，不妨记步长s l i s 2 分别为 a和 b . 则 c ( n ; s , , s 2 ) 记为c ( n ; a , b ) . d c ( n ; a , b ) = d ( c ( n ; a , b ) ) , l d c ( n ) = m i n d c ( n ; a , b ) . b o e s c h和wa n g 1 9 9 8 年改进了w a n g 和 c o p p p e r s m i t h 1 9 7 4 年的结论 ，。 (、 ) 打 拒 万 万 1 2 1得 到 (、 ) 的 下 限 ib , (n ) 一 (,2-n - 1 一 1) 1 2 1 当n 6 时，d ( n ; i b c ( n ) , i b c ( n ) + 1 ) = i b c ( n ) ( m u k h o p a d h y a y a k 2 1 ,2 2 ) 当n 6 时， 如果g c d ( n , i b , ( n ) ) = 1 或g c d ( n , l b c ( n ) + 1 ) = 1 则d o ( n ) = 1 b , ( n ) . f a b r e g a j 和z a r a g o z a m 采 用 棋 盘 方 法( 如 图2 .3 .1 ) 讨 论 双 环 网 的 优 化与容错问题. 如果固定步长为a , 瓦则与点0的距离为 1 的点有 4个: 士 a ， 士 b m o d ( 扔; 与点0 距离为2 的点有8 个:士 2 a , 1 2 b ， 士 ( a + b ) , 1 ( a - b ) m o d ( n ) ; 如此下去， 与点。 距离为k 的点有4 k 个. 当给定直径d则顶点数 第 1 7页 共 4 6页 电子科技大学硕士学位论文 最 多可达 n d = n d - 1 n n d 时， 2 d 2 + 2 d+ 1 ， 此 时 a = l , b = 2 d + 1 或 a = d , b = d + 1 、当 均有d ( c ( n ; d , d+ 1 ) ) = d 目1 1 .1 定理2 .3 . 1 若4 度循环图c ( n ; a , b ) 连通， 则有且仅有两类不同构的图: ( 1 ) c ( n ;l , a ) ( 1 a n l 2 ) ; ( 2 ) c ( n ; a , b ) ( a , b 为n 的互素因子) . 证明 对任意的4 度连通循环图c ( n ; a , b ) 满足g c d ( a , b , n ) = 1 . ( 1 ) 当。 = 1 , 1 b n / 2 , b e 2 ,3 , . . . , r n / 2 1 - 1 . 此时 有r n l 2 1 - 2 个不同 构 的图. ( 2 ) 当。 # i ， i a b n l 2 ， 因 g c d ( a , b , n ) = 1 ，故可分两种情况 i ) a , b 至少有一个与n 互素，不妨设g c d ( a , n ) = 1 ，作同构映射 o : i - + is m o d ( n ) , i = 0 ,1 , ， 二 ， n - 1 . 则必存在k e 2 ,3 , - - .,卜 / 2 1 - 1 ， 使得 c ( n ; a , b ) 二 c ( n