（应用数学专业论文）网络拓扑结构设计中几个问题的研究.pdf

摘要 本文讨论互连网络垣b 箜掏分析中的几个问题全夹共分三部分 第一部分讨论图的限制边连通度喔剑塑连通鏖是衡量圈鳖查鳢壁的重要参 数本部分研究它与最小边度的关系，首先给出了图的限制边连通度小于最小边 度的必要条件，然后利用这个结论找出了一些优图的类，如除星以外的连通边可 迁图，奇阶的或不含三角形的连通点可迁图，它们的限制边连通度都与最小边度 相等 f 第二部分讨论k a u t z 和d eb r u 的n 有向图中的路长问题fd u e ta j 证明了， 对于k a u t z 有向图k ( d ，k ) 中的任意一对不同的顶点z 和y ，存在d 条内点不 交的( x ，y ) 一路，其中一条长k ，d 一2 条长k + 1 ，一条长墨k + 2 i m a s ee t a j 证明了，对于d eb r u i j n 有向图b ( d ，k ) 中的任意一对不同的顶点x 和y ，存 在d 一1 条内点不交的( o ，y ) 一路，长度都不大于k + 1 但是，原始的证明非常 复杂，尤其是后者，含有繁琐的验证我们这里给出这两个定理的简单证明，彳 第三部分讨论c a y l e y 图的笛卡尔乘积问题c 型l 。匕图是由有限群导出的 一类重要的点可迁图，被认为是非常合适的互连网络拓扑结构而笛卡尔乘积则 是从小规模的指定网络构造大规模网络的重要构造方法本部分证明了c a y l e y 图的笛卡尔乘积仍是c a y l e y 图作为实例，指明循环网络、超立方体、广义超 立方体、超环面和立方连通圈等都是c a y l e y 图这样可以借助于代数方法来分 析和研究这些网络的性质 2 2 0 0 2 年中国科学技术大学硕士学位论文3 a b s t r a c t t h ed i s s e r t a t i o ns h o w ss o m es t u d yo nt h et o p o l o g i c a ls t r u c t u r eo fn e t w o r k s i tc o n t a i n st h r e ep a r t sa sf o l l o w s ： t h ef i r s tp a r td i s c u s s e sa b o u tt h er e s t r i c t e de d g e c o n n e c t i v i t y ，w h i c hp r o v i d e sam o r ea c c u r a t em e a s u r eo ff a u l t t o l e r a n c eo fn e t w o r k st h a nt h ec l a s s i c a l e d g e c o n n e c t i v i t y i tr e l a t e st h er e s t r i c t e de d g e c o n n e c t i v i t yt ot h ee d g e d e g r e e o fac o n n e c t e dg r a p h w eg i v e ss o m en e c e s s a r yc o n d i t i o n sf o rag r a p hw h o s e r e s t r i c t e de d g e c o n n e c t i v i t yi ss m a l l e rt h a ni t sm i n i m u m e d g e d e g r e e ，t h e n u s e t h e s ec o n d i t i o n st os h o ws o m e l a r g ec l a s s e so fg r a p h s ，s u c ha sa l lc o n n e c t e de d g e t r a n s i t i v eg r a p h se x c e p tas t a r ，a n da l lc o n n e c t e dv e r t e x - t r a n s i t i v eg r a p h sw i t h o d do r d e ro rw i t h o u tt r i a n g l e ，h a v ee q u a l i t yo ft h er e s t r i c t e de d g e c o n n e c t i v i t y a n dt h em i n i m u m e d g e d e g r e e t h es e c o n dp a r ti sa b o u tt h ep a t h l e n g t hp r o b l e mi nk a u t z d i g r a p ha n dd e b r u i j nd i g r a p h d ue ta ls h o w e dt h a tf o ra n yt w o d i s t i n c tv e r t i c e sza n dyi nt h e k a u t zd i g r a p hk ( d ，) ，t h e r ea r edi n t e r n a l l yd i s j o i n t ( x ，g ) 一p a t h s ，o n eo fl e n g t h a tm o s tk ，d 一2 o f l e n g t ha tm o s tk + 1 ，a n d o n eo f l e n g t ha tm o s t + 2 i m a s e e a ls h o w e dt h a tf o ra n yt w od i s t i n c tv e r t i c e sxa n dyo ft h ed eb r u i j nd i g r a p h b ( d ，) ，t h e r ea r ed 一1i n t e r n a l l yd i s j o i n t ( z ，) 一p a t h so fl e n g t ha tm o s tk + 1 h o w e v e r ，t h e i ro r i g i n a lp r o o f s ，e s p e c i a l l yt h el a t t e r ，c o n t a i nb o r i n ge x a m i n a t i o n s f o rs e r v a lc a s e s t h ec o n c i s ep r o o f sa r eg i v e ni nt h i sp a r t t h et h i r dp a r ti so ns o m er e s u l t so f c a y l e yg r a p h s ，w h i c hr e p r e s e n t a c a t e g o r y o fs y m m e t r i ca n dr e g u l a rg r a p h sd e r i v a b l ef r o mf i n i t eg r o u p s ，h a v eb e e ns h o w nt o b ev e r ys u i t a b l et os e r v ea si n t e r c o n n e c t i o nn e t w o r kt o p o l o g i e s a sa no p e r a t i o n o fg r a p h s ，t h ec a r t e s i a np r o d u c ti sa ni m p o r t a n tm e t h o di nc o n s t r u c t i n gl a r g e r n e t w o r k sf r o ms o m es m a l la n ds p e c i f i e do n e s i nt h ef o u r t hs u b s e c t i o n ，i ti s s h o w nt h a tt h ec a r t e s i a np r o d u c to fc a y l e yg r a p h si ss t i l lac a y l e yg r a p h i n i l l u s t r a t i o no ft h i sr e s u l t ，c i r c u l a n t s ，h y p e r c u b e s ，g e n e r a l i z e dh y p e r c u b e s ，t o r o i d a l m e s h e s ，c u b e c o n n e c t e dc y c l e sa n ds oo n ，a l la r ec a y l e yg r a p h s 第一章图的限制边连通度 1 1 引言 在计算机互联网络的拓扑结构设计与分析中，连通度是度量网络可靠性的重 要参数但在分析和应用这些参数时，人们不言而喻地假定某些组件的任何子集 都会同时失灵，或者说对这些参数未加任何限制然而，在带有某种类型故障可 诊断算法的计算机互联网络中，人们可以安全地假定网络组件的某些子集不会同 时失灵，或者说对这个参数加以某些限制对于这样的网络，经典的连通度不能 精确地度量其可靠性h a r a r y ( 1 9 8 3 ) 首先提出限制连通度的概念它能够更精 确地分析各种网络的可靠性近几年来，已引起许多理论计算机科学工作者和数 学工作者的研究兴趣( 比如， 1 3 ， 1 4 ， 2 4 ， 2 5 】， 2 6 ， 2 7 ， 3 3 ， 3 6 ， 3 7 j ， 3 s 】) 这里主要研究边情形的限制连通度，即限制边连通度这个崭新的概念最先 是由e s f a h a n i a n 和h a k i m i 1 3 】提出的 本章的主要结果给出一般图的1 一限制边连通度的上界，以及在点可迁图的 条件下，何时达到上述上界 在这个部分里，我们称不连通图、三角形和星图为平凡图，其它的图称为非 平凡图s e ( g ) ，若g s 不连通，则称s 是g 的边割若g s 不连通 且它的每个连通分支都不含孤立点，则称s 是g 的1 一限制边割x y ( g ) ， 用a ( x ) 表示e ( x ，叉) d ( x ) = i a ( x ) 1 图g 的1 一限制边连通度记为a ( g ) ， 定义为 a ( g ) = m i n d ( x ) ：x 是g 的1 一限制边割) 对于e = x y e ( g ) ，令 如( e ) = d a ( x ) + d v ( y ) 一2 ，f ( g ) = r a i n 如( e ) ：e e ( g ) ) ( g ) 称为是g 的最小边度在文献 4 】中已证明，对于任意的非平凡图g ，a ( g ) 存在，并且满足下面不等式： a ( g ) f ( g )( 11 1 ) 设g 是非平凡图，如果川( g ) = f ( g ) ，则称g 是优的，否则称g 为非优的我 们的目的是要找出一些优图的图类在文献 1 4 ，【2 4 ， 2 5 ， 2 6 ， 2 7 ， 3 3 】， 3 7 】， 3 8 4 中国科学技术大学硕士学位论文5 中，已指出了一些优图的图类在这里，我们首先给出一些非优图的必要条件， 然后由此获得一些优图的图类，它们包括非平凡的边可迁图，不含三角形的奇阶 连通点可迁图另外，在 1 4 ， 2 5 ， 2 7 ， 3 7 中所得到的某些优图图类可有我们这 里的结果导出 1 2 一些记号和预备结果 设g = ( k e ) 是图，x ，y 是v ( a ) 的非空子集，则有( 见 2 8 】，p r o b l e m 64 8 1 ： d ( x n y ) + d ( x u y ) d ( x ) + d ( y )( 1 2 1 ) 若x n y = o ，记( x ，y ) = e = x y e ：z x 且y y ) s 是g 的1 一限制边割，如果 s i = a ( g ) ，则称s 为a ，- 割易知，对于 任意的a 一割s ，g s 恰有两个连通分支设x 是v ( v ) 的真子集，若o ( x ) 是g 的a 一割，就称x 是g 的分片如果x 是g 的一个分片，则又也是g 的分片令 r ( a ) = t i n i x l ：x 是g 的分片) 显然，2 r ( g ) 茎 1 v f 分片x 如果满足i x l = r ( g ) 就称x 是g 的原子 定理1 1 非平凡图g 是优的当且仅当r ( e ) = 2 证明：设r ( a ) = 2 则存在x = z ，g 满足d ( x ) = ( g ) = 话( e ) ，这里 e = x y e ( g ) 由( 1 1 1 ) 及f ( g ) 的定义得， ( g ) f g ( e ) = d ( x ) = 入( g ) f ( g ) ， 所以g 是优的 反之，假设g 是优的，则存在g 的一条边e = x y 满足 ( g ) = f ( g ) = 如( e ) = d e ( x ) + d a ( y ) 一2 现令x = f x ，g ) 若g o ( x ) 无孤立点，则r ( g ) = 2 下设g o ( x ) 有一个 孤立点u 显然1 d c ( u ) s 2 如果如( u ) = l ，不失一般性，我们设u 与y 相邻，那么 d g ( z ) + d a ( y ) 一2 = f ( g ) d a ( y ) + d a ( u ) 一2 = d a ( y ) 一1 中国科学技术大学硕士学位论文 6 这说明d a ( x ) = 1 于是 矛盾 a ( g ) f y z ：d a ( z ) 2 i d a ( x ) 2 = ( d a ( x ) + d v ( y ) 一2 ) 一1 = f ( g ) 如果d g ( “) = 2 ，u 与z ，y 都相邻则 d g ( x ) + d a ( y ) 一2 = ( g ) d a ( y ) + d e ( u ) 一2 = d a , ( y ) 从而得d a ( x ) = 2 ，类似地，又可得d a ( y ) = 2g 就是一个三角形，矛盾于假设 1 3 非优图原子的性质 引理1 2g 是非优图，f 是g 的一个分片，u 是f 的真子集，是图 g o ( u ) 中孤立点的集合如果j u 且i ( j - ，_ ) i l ( ，f u ) l ，则f i 是g 的 一个分片 证明：不妨假设，0 令y = r i ，f = f u 那么y o ，f 0 ，因 为，u 且u 是f 的真子集记z 是g o ( y ) 的全体孤立点的集合如果 z = d ，则y 是g 的1 一限制边割由假设i ( ，f ) i l ( ，f 引，我们有 a ( g ) 茎d ( y ) = d ( f ) 一i ( ，f ) i + i ( ，f 引sd ( f ) = a ( g ) 这说明y 是g 的分片故当z = o 时引理结论成立 以下证明z = o 假设z 0 ，我们导出矛盾 首先，说明对于任意x i ，( z ，f ) 0 令i = x i ：( x ，f ) = 0 ) 如果 1 7 0 ，则g ( ，) f ，因为由假设知( i ，u i ) = o 令 z = ( z n f ，) g ( ，) ，w = ( y u ，) 砂 易知，g o ( w ) 不含孤立点，o ( w ) 是g 的一个1 一限制边割注意到 l ( ，f ) l = i ( ，_ ) l l ( j ，f 引l ( ，f 引i ，7 i 0 ， 2 0 0 2 年中国科学技术大学硕士学位论文7 得i 1 0 且 i ( 八，f ) f l ( ，f 引l ，f 7 z l + i ( ，f 7 z 引 i ( ，f z ) 于是我们有 d ( 仉7 ) = d ( f ) 一1 ( z ，f ) 1 d ( f ) 一i ( z ，f ) i 曼d ( r ) f ( j ，f ) 1 + i ( i 1 ，f z ) a ( g ) 矛盾导出，= 0 ，即对于任给x i ，( x ，f ) d 于是 ( y ，”) l = n a ( v ) n ，”l f ( n a ( y ) n ”，f ) i ，v y z ，”，( 1 3 1 ) 其次，我们断言z = n g ( y ) n f i = 0 说明z y 因为z 是g a ( f v ) 的孤立点的集合且g o ( e ) 不含孤立点，故z 舀( n 但g ( ，) nu = 0 ，因 为由假设j u 是g o ( u ) 的孤立点的集合于是z 舀( ，) nf ，另一方 面，如果( g ( ，) n f ，) z 0 ，那么v z 0 ，g o w z ) 不含孤立点，因为f 是g 的一个分片又由j o 和d z g ( j ) nf 知( j ，z ) o 根据假设 j ，f 2i i ，f 仉我们有 a ( g ) d ( y z ) = d ( f ) 一i ( ，- f ) i j ( z ，_ ) l + ，f z d ( r ) 一( i ( i ，_ ) l l ( ，f 引) d ( f ) = a ( g ) 显然是矛盾这说明( g ( j ) n f ) z = 0 于是z = v b ( j ) n f 再次，v z z 有( z ，f ) 0 否则z 是g o ( u ) 的一个孤立点，即z i ， 矛盾于是 j 恤，z ”) i = f n a ( x ) n z ”i 茎i ( g ( z ) n z ”，f ) i ，v x ，z ”z ( 1 3 2 ) 最后，令y z ，z f z ) n ，下式可导出矛盾： f ( g ) d c ( z ) + d g ( ) 一2 = l ( z ，- f ) l + l ( x ，z 可) ) i + i ( y ，f ) l + i ( ， z ) 墨i 忙，f ) i + l g ( ) n ( z ) ) ，f l + l ( ，司1 + i ( n c ( v ) n ( 八 z ) ) ，万) i = ( i x ，一f f + i ( g ( ) n ( ， z ) ) ，f ) i ) + ( i ( v ，f ) 1 + l ( g ( 。) nz ，f ) 1 ) = l ( v 0 ) n j ，f l + l ( g 扛) nz ，f ) l l ( ，f ) i + l ( z ，f ) i lf ) f i = d ( v ) = a ( g ) ( g ) ， 中国科学技术大学硕士学位论文8 第一个不等式成立是由于z = n c ( 1 ) nf 和( z ，y z ) d ；第二个不等式成立 是由于( 1 3 1 ) 式和( 1 3 2 ) 式证毕 定理1 3 设g 是非优图，则g 的两个不同的原子无交 证明设x 和x 是g 的两个不同的原子，那么d ( x ) = d ( x 7 ) = a 7 ( g ) a ( g ) 由( 1 2 ) ， d ( d ) = d ( xu x 7 ) d ( x ) + d ( x 7 ) 一d ( x n x ) a ( g ) ( 1 33 ) 这说明g o ( d ) 必含孤立点，设，是这些孤立点的集合，显然，冬d 如果d ，= d i 0 ，则o ( d 7 ) 是g 的1 一限制边割，因为g a ( d ) 不含孤立点，由( 1 5 ) 得 a ( g ) d ( d ) = d ( d ) 一d a ( “) d ( d ) a ( g ) 矛盾导出i = d 不失一般性，假设l ( d ，b ) i i ( d ，c ) 令f = 又，i = u = dc f ，由引理1 2 ，c ( = x d = f i ) 是g 的一个分片且真包含于x 这与 x 7 是g 的原子矛盾证毕 注长度大于3 的圈说明定理1 3 对优图不真 定理1 4 设g 是非优图，如果g 是正则的，则r ( a ) 3 证明由定理11 ，r ( a ) 3 ，显然k 之3 设x 是g 的一个原子，则 r = r ( g ) = i x l 且d ( x ) = a ( g ) ( g ) = 2 k 一2 考虑对x 中所有顶点度求 中国科学技术大学硕士学位论文9 和，得 k r = d a ( x ) 2r ( r 一1 ) + d ( x ) 笙二；! ! ：一1 一攀 疗k 而t 是整数，故t k l ，于是t = 一1 ，a x 的度为( k 一1 ) 注意到a x 必 含圈，因为3 ，若它不含三角形，则至少有2 女一2 个顶点( 见f 2 1 的e x e r c i s e l74 ( a ) ) 但这时，2 2 i x f = a 7 ( g ) s2 h 一3 ，矛盾故a x 1 含有三角 形 ( i i ) 任取y x ，由于g 是点可迁的，对于固定的。x ，存在盯a u c ( g ) ， 盯( z ) = y o ( x ) 也是g 的一个原子，令x y = 盯瞵) 因为y x y x ，故x x 。， 由定理1 3 ，xn 玛= o ，且g x 竺g 【x v 于是对于g 中的每个顶点y ，存 在一个包含的原子，且g 】= g 冈对于y ，z y ( g ) ，y 乙要么 蜀= 兄，要么j 0n x z = d 这些原子x l ，x 2 ，蜀。构成了v ( a ) 的一个划 分，且g x i 兰g 吲，i = l ，2 ，m ，m 2 所以 j vj = mj x j = f y 七一z l x l ( k 一1 ) = 2 1 e ( a ) 一2 m l e ( a l x ) 1 即g 是偶阶的，证毕 中国科学技术大学硕士学位论文 1 0 1 4 优图的图类 定理1 6 ( x u ， a r ) g 是连通的点可迁图，若g 不含三角形或是奇阶的 则g 是优的 这是定理1 5 的直接推论 众所周知的k 维立方体q k ( k 2 ) 是一类点可迁图，它经常被应用在分布 式存贮计算系统的构造上q k 是k 一正则二部分图，所以它不含三角形于是 从定理1 6 易得下面的结果 推论1 7 ( e s f a h a n i a n ， 1 4 ) 维立方体是优的 设。是长为d 的圈，k 维环面网孔( 见i s h i g a m i 2 2 ) 定义为笛卡儿乘积 c d 。c a 。c d 。它是点可迁的，当d i 4 时( 比如，参见 3 5 ) ，它不含三 角形由定理1 6 可得以下结果 的 推论1 8当d 。4 时，i = 1 ，2 ，k ，k 维环面网孔c ( d l ，d 2 ，d k ) 是优 另外一类在网络设计中很重要的图类是循环图，它也是点可迁的循环图， 用g ( n ；a 1 ，a 2 ，a k ) 表示，这里0 a l ，i 与j 有边相连当且仅当对于某个t ，1 t k ，有i j i i ! a i ( m o d n ) ( 见 1 ) 若a k ；，它是2 k 正则的，否则，是( 2 k 一1 ) 正则的 推论1 9 ( l ia n dl i ，【2 5 】) 连通循环图g ( 礼；a l ，a 2 ，a k ) ，n 4 ，是优的 如果它不含三角形或a k ； 证明：设g = g ( 礼；a l ，0 2 ，o k ) 由定理1 6 ，我们只需证当a k ；时， g 是优的即可假设g 不是优的，由定理1 5 ，对于g 的任意一个原子x ，存在 整数m 2 ，使得n = m i x l 且o x 】是( 2 一1 ) 正则的存在 1 ，a 2 ，a k ) 的子 集 6 。，b 2 ，巩) ，满足9 _ c d ( n ，b 1 ，b z ，b f ) = m 且g x 型g ( 蔫；，祭，籍) ， 、 中国科学技术大学硕士学位论文 l l 这里b t b 2 1 ，则l ”( d ) 的直径为k + n 注意到l ( d ) 的顶点集y ( l ( d ) ) 是d 的边集e ( d ) 由于( z ，y ) e ( d ) 可 以认为是d 中长为1 的有向链，所以( x ，y ) 可以用v ( d ) 中元素的二元序列x y 来表示于是，l ( d ) 的顶点集y ( l ( d ) ) 是v ( d ) 中元素的二元序列集的子集 同样地，由n 重线图p ( d ) 的定义，我们不难看出，l “( d ) 的顶点集是 _ d 中长为n 的有向路集 扩( d ) 的顶点可以看成是v ( d ) 中元素的n + 1 元 序列x o x l z n ，其中( 翰，x i + 1 ) e ( 口) ，i = 0 ，1 ，n 一1 设x = x o x l z 。 是( d ) 的一个顶点，对所有x n + 1 吉( z 。) ，l “( d ) 中有从顶点x 连到顶点 y = z z 。x n x 。+ 的有向边于是p ( d ) 中长为h 的有向路可以表示成v ( d ) 中元素的n + 1 + h 元序列x l x 2 z 。z 。+ l 一x 。+ 1 十h ，其中( ，z h l e ( d ) ) ， i = 0 ，1 ，一，n + h 2 0 0 2 年中国科学技术大学硕士学位论文1 6 2 3 d eb r u i j n 有向图的定义与性质 对于给定的整数d 芝2 和1 ，d eb r u i j n 有向图记为b ( d ，k ) ，通常有下列 三个等价定义 1 d 元集上的有序k 元组( d - a r yk - t u p l e s ) b ( d ，k ) 的顶点集v ( b ( d ，) ) = x l x 2 x k ：x i o ，1 ，d 1 ) ) ；b ( d ，k ) 中以顶点x l z 2 x 为起点的d 条有向边的终点为x 2 x 3 z n ，其中o o ，l ，d 一1 ) 2 线图 对于固定的d ，用砑表示在d 阶完全有向图的每个顶点上添加一个环后得 到有向图，则b ( d ，k ) 递归地定义为： b ( d ，1 ) = 砑；b ( d ，2 ) = 上( 埘) ；b ( d ，k ) = l k - 1 ( 硪) ，k2 2 3 代数 b ( d ，k ) 的顶点集v ( b ( d ，k ) ) 和有向边集e ( b ( d ，) ) 分别定义为： v ( b ( d ，女) ) = 0 ，1 ，d 一1 ) ； e ( b ( d ，) ) = ( z ，y ) ：y 三x d + a ( m o d d k ) ，o = 0 ，1 ，d 一1 ) 由b ( d ，k ) 的第一个定义容易获得 性质2 7d eb r u i j n 有向图b ( d ，k ) 有d 。个顶点，d 2 + 1 条有向边，d 正则 的，无平行边但有d 个环 由b ( d ，k ) 的线图定义容易获得 性质2 8b ( d ，k ) 的强连通度为d 一1 ，直径为k 2 0 0 2 年 中国科学技术大学硕士学位论文1 7 2 4k a u t z 有向图的定义与性质 对于给定的整数d 2 和k 1 ，k a u t z 有向图记为k ( d ，动，通常有下列三 个等价定义 1 d + l 元集上相继两元素不同的有序k 元数组( d + 1 - a r yk - t u p l e s ) k ( d ，) 的顶点集 v ( k ( d ，) ) = x l x 2 - - x k ：x i o ，1 ，一，d l ，z i z 。+ l ，i = 1 ，2 ，k 一1 ； k ( d ，) 中以顶点z l z 2 x k 为起点的d 条有向边的终点为x 2 x 3 x k o ，其中 n o ，1 ，一，d t ，n x 2 线图 对于固定的d ，用k d + 1 表示d + 1 阶完全有向图，则( d ，) 递归地定义为： k ( d ，1 ) = 肠扎k ( d ，2 ) = l ( 肠+ 1 ) ，k ( d ，k ) = l 1 ( + 1 ) 3 代数定义 k ( d ，k ) 的顶点集v ( k ( d ，) ) 和有向边集e ( k ( d ，) ) 分别定义为： v ( k ( d ，) ) = ( 0 ，1 ，d + d 一1 ) e ( k ( d ，) ) = ( z ，y ) ：y 三一( x d + a ) ( m o d d 。+ d 。+ 1 ) ，。= 1 ，2 ，d ) k a u t z 有向图的线图定义是由f o i l ，y e b r a ，a l e g r e ( 1 9 8 4 ) i 1 5 ) 和r e d d y , k u h l ， h o s s e i n i ，l e e ( 1 9 8 2 ) 独立发现的我们在部分中将主要用k a u t z 图的线图定 义由线图的定义知k ( d ，k ) = l ( k ( d ，k 一1 ) ) k a u t z 有向图这样一个简单的递 规结构是很有用的它不仅能使我们通过线图导出k a u t z 有向图的许多性质， 还表明若将k ( d ，) 作为计算机互联网络的拓扑结构，则日后对它进行扩容或升 级是方便的 性质2 9k ( d ，) 有d + d 一1 个顶点，d 。+ 1 + d 条有向边的d 正则简单 有向图 中国科学技术大学硕士学位论文1 8 利用线图的性质和k a u t z 图的线图定义，容易获得 性质2 1 0k ( d ，k ) 的连通度为d ，直径为k 2 5 主要定理和它的证明 定理2 1 【l l 】对于k a u t z 有向图k ( d ，) 中任意两个不同的顶点z 和， 存在d 条内点不交的( x ，) 一路，其中一条路长k ，d 一2 条路长k + 1 ，一 条路长k + 2 定理2 2 【2 1 对于d eb r u i j n 有向图b ( d ，) 中任意两个不同的顶点z 和口 存在d l 条内点不交的( x ，) 一路，它们的长度都不大于+ 1 原始的证明非常复杂，尤其是定理22 ，含有繁琐的验证我们这里运用线 图技术和d ue ta l l l l 的技巧简化两者的证明 定理2 1 的证明我们21 用归纳法 当k = 1 时，k ( d ，1 ) = t i d + 1 通过观察易得，在硒+ 1 中，对于任意两个不 同的顶点x 和y ，有d 条内点不交的( z ，) 一路，一条长为1 ，d 一1 条长为2 ， 故定理对k = 1 成立 假设当k 2 时，定理对k ( d ，k 一1 ) 中任意两顶点定理的结论成立 设z ，y 是k ( d ，k ) = l 卜1 ( k d + ) 中任意两个不同的顶点，则x ，y 对应于 k ( d ，k 一1 ) 中两条边，因为k ( d ，) = l ( k ( d ，一1 ) ) 记这两条边为x = ( w ，w ，) ) = 扣，u ，) 如果w u ，则由归纳假设，k ( d ，k 一1 ) 中存在d 条内点不交的( w ，”) 一 路，一条长k 一1 ，d 一2 条长k ，一条长s + 1 由线图的定义知， k ( d ，k ) 中存在d 条内点不交的( 。，) 一路，其路长满足定理中所述的条件 如果w = v ，则( x ，y ) e ( k ( d ，女) ) ，记z ，y 为如下的形式： z 2 x l x 2 一x k i x k ，y 2x 2 x 3 。x k x k + 1 2 0 0 2 年 中国科学技术大学硕士学位论文1 9 这里x l ，x 2 ，x k ，x k + l o ，1 ，d ) ，甄x j 当i = 1 ，2 ，k 这样 ( z l ，x 2 ，x k ，x k + 1 ) 是肠+ 中的一条长为k 的路我们以如下形式在k ( d ，) 中构建( z ，矿) 一路m ，件j ： w 1 = ( x l ，x 2 ，- ，x k 一1 ，x k ，x k + 1 ) = ( x l ，x 2 ，x k ，u j ，x 2 ，x 3 ，x k ，x k + 1 ) ，j = 2 ，3 ，d 一1 = ( x l ，x 2 ，x k ，x 2 ，札，x 2 ，x 3 ，x k ，x k + 1 ) ， 这里u ，u 2 ，d l o ，1 ，d z 1 ，x 2 ，+ l 且札2 ，“d 一1 互异显 然路m 的长为1 ，路的长为k + l ( j = 2 ，3 ，- - ，d 一1 ) ，路 的长为k + 2 为了说明这些( x ，) 一路是内点不交的，只需证，慨在k ( d ，k ) 中内点 不交即可 用反证法假设存在某个i 和j ( 2 i 0 - + k 。 笛卡尔乘积还保持了因子图的许多性质，例如 性质3 4 若d 1 ，d 2 ，d 。是点可迁的，则d 1 d 2 x d 。是点可迁的 中国科学技术大学硕士学位论文2 3 性质3 5 设d = d i d 2 d 。和d 7 = d i d ：x d ：都是n 个 有向图的笛卡尔乘积若对每个i = l ，2 ，n 有d i d ；，则d d 性质3 6 若无向图g l 含h a m i l t o n 圈，g 2 含h a m i l t o n 路则g 1 g 2 含 h a m i l t o n 圈 3 3c a y l e y 图 首先回顾一下c a y l e y 图的定义设是一个非平凡有限群，非空子集scr 并且s 不含r 的单位元e 定义一个有向图g 如下： v ( c ) = r ；( ，g ) e ( c ) jx - - i g s ，v 茁，可f 如此定义的有向图g 称为群r 关于子集s 的c a y l e y 图，记为c r ( s ) 容易证明侨( s ) 是强连通甘s 是r 的生成集若s _ 。= s - 1 ：s s ) = s ，则群r 关于子集s 的c a y l e y 图g ( s ) 是无向图显然，c a y | e y 无向图是 c a y l e y 有向图的特殊情形 例1g = c r ( s ) 是完全图甘s = f 一 e ) ，其中e 是r 的单位元 例2 循环图( c i r c u l a n t s ) g ( 礼；s ) 是一类最常见且应用最广泛的网络拓扑 结构 3 2 】，其中s l ，2 ，n 1 ) ，顶点集v = 磊，边集e = ( i ，j ) ：| s s 使得j i 三s ( m o dn ) ) 考虑群磊，0 是单位元，i 的逆元是n i 容易证明g ( n ；s ) 就是c a y l e y 图屹。( s ) 事实上，任取i ，j 磊= y ( g ( n ；s ) ) 由c a y l e y 图和循环图的定义 知， ( i ，j ) e ( c z 。( s ) ) = i 一1 + j s 车= ( n i ) + j = j i s ( m o dn ) 甘| 8 s 使得j i i s ( m o dn ) = = ( i ，j ) e ( g ( n ；s ) ) 显然，g ( 佗； 1 ) = c k ，g ( n ； l ，n 一1 ) ) = g 。；当s = l ，2 ，一，n 一1 ) 时， g ( n ；s ) = 因此，西，g 和k 。都是整数模n 剩余类加法群乙的c a y l e y 图 中国科学技术大学硕士学位论文2 4 3 4c a y l e y 图的笛卡尔乘积 定理3 - 1 c a y l e y 图的笛卡尔乘积仍是c a y l e y 图换句话说，设g 。( e n ( & ) ) 是有限群f i = ( x i ，o i ) 的c a y l e y 图，则笛卡尔乘积g = g 1 g 2 xg 。是 群f = f i r 2 r 的c a y l e y 图c r ( s ) ，其中 n s = u e 1 e l - 1 s i e l + l ) ， t = 1 e 。是r 。( i = 1 ，2 ，n ) 的单位元 证明：由第2 节的说明，我们只对凡= 2 来证明结论，此时r = f 1 r 2 = ( x l x 2 ，o ) ，s = ( e 1 ) 岛) u ( e 2 ) ) 任取x l x 2 ，y l y 2 x 1 x 2 ，其中 z 1 ，y l x 1 ，x 2 ，y 2 弼我们只需证明 ( x l x 2 ，y l y 2 ) e ( a ) 错( x l x 2 ) 。10 ( y l y 2 ) s 由图的笛卡尔乘积的定义知， ( x l x 2 , y l y 2 邶c g ，铮健 因为g 。= c r 。( & ) ，所以( 鼢，玑) e ( g ；) 甘。i 1o iy i s i ，i = 1 ，2 于是 x 】= y l ，( x 2 ，y 2 ) e ( g 2 ) 甘 ( x l z 2 ) 一1o ( y l y 2 ) = ( z i l z i l ) o ( y l y 2 ) = ( z i l0 1y 1 ) ( z i l 。2y 2 ) = ( z i l0 1x 1 ) ( 茹i 10 2y 2 ) = e l ( z i l0 2y 2 ) e 1 ) s 2 s 同样地 x 2 = y 2 ，( x l ，y i ) e ( g 1 ) 甘 ( x l z 2 ) 一1 。( y l y 2 ) = ( z i l z i l ) o ( y l y 2 ) = ( z f l0 1y 1 ) ( 茹i 10 2y 2 ) = ( z f l0 1y 1 ) ( z i l0 2z 2 ) = ( z i lo ly 1 ) e 2 s 1 e 2 ) s r0 0 d g g ，【，【 f g 、j 比玑 2 1 p 协 玑抛 中国科学技术大学硕士学位论文2 5 这说明g = g 1xg 2 是f = f 1 f 2 关于s c a y l e y 图c r f s ) 作为定理3 1 的应用 立即知q 。，q ( m 1 ，m 2 ， c a y l e y 图 s l e 2 ) u e l x 的 _ 并注意到k 。，g 和最都是群乙的c a y l e y 图， m 。) ，c ( m l ，m 2 ，- 一，m 。) 和d ( m l ，m 2 ，一，m 。) 都是 3 5 立方连通圈是c a y l e y 图 n 维立方连通圈( c u b e c o n n e c t e dc y c l e ) 3 0 ，记为c c c ( n ) ，是一个基于q 。 构造出来的无向图：用g 替代q 。的每一个顶点，并将q 。的第k 维边连到g 的第k 个顶点具体地说，c c c ( n ) 的顶点集为v = ( 。；k ) ：z v ( q 。) ，1s k n ，两顶点( 茁，k ) 和( ，k ) 有边相连 = 寺满足下列两条件之一： ( i ) x = x 且k k 三士l ( r o o dn ) ； ( i i ) k = 且x 和x 在q 。中有k 维边相连 c c c ( n ) 是由美国伊利诺伊大学的f p p r e p a r a t a 和法国巴黎南大学的j v u i l l e m i n 针对改进q 。的缺点而于1 9 8 1 年首先提出来的，它被广泛用于平行处 理系统的拓扑结构和v l s i 的布图与此同时，c c c ( n ) 还为解决大量问题( 如 快速f o u r i e r 变换、分类、矩阵乘法和置换等) 的有效并行算法提供可行的通信 模式c c c ( n ) 具