(应用数学专业论文)网络泛圈性与泛连通性的研究.pdf_第1页
(应用数学专业论文)网络泛圈性与泛连通性的研究.pdf_第2页
(应用数学专业论文)网络泛圈性与泛连通性的研究.pdf_第3页
(应用数学专业论文)网络泛圈性与泛连通性的研究.pdf_第4页
(应用数学专业论文)网络泛圈性与泛连通性的研究.pdf_第5页
已阅读5页,还剩81页未读, 继续免费阅读

(应用数学专业论文)网络泛圈性与泛连通性的研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 我们通常用一个连通的无向图g = ( u e ) 作为互连网络的拓扑结构,这时 图g 的顶点代表网络中的组件,组件之间的通信联系用相应i 员点之间的连线米表 示网络的拓扑结构决定着该网络的性能可嵌入性是度量网络优劣的一个重要 性能一个网络是否具有泛嘲性可以度量该网络是否可以嵌入任意长度的幽,泛 连通性是泛圈性的深化,如果一个网络是泛连通的! j 5 l j 一定足泛斟的 一个大型网 络在投入使用的过程中,它的某些组件和连线难免会发生故障我们所说的网络 容错性是指该网络能容忍多少组件和( 或) 连线同时发生故障,剩余的子网络中仍 然含有某些特殊结构故考虑网络的容错性其有实际意义 本文主要研究几个著名网络的泛刚性、泛连通性和边容错泛阱性、泛连通性 全文共分五章 第一章介绍了本文用到的一些图和网络的基本概念泛眭和泛连通性的定 义,儿个著名的网络的定义以及目前已经取得的一些结果 第二章研究了几个著名网络的泛矧性首先,研究了折叠立方体网络f o ( n2 2 ) 的边泛斟性根据它的维数n 的不同的奇偶性,证明了它的每条边位丁不同长 度的奇陶或偶罔上;然后,证明了交义立方体嘲络c 0 。( n 2 ) a 部纽立方体网 络l t 0 。( n 2 ) 的每条边位丁一个长为的斟上,其中4 f 茎2 “:通过证明类立 方体网络的点泛圈性用统一的方式证明了交义立方体网络,m s b i u s 立方体网络, 纽立方体网络以及局部纽立方体网络等具有小的直径的超立方体网络的一些变型 的点泛圈性统一了前人的证明 第三章研究几个著名网络的泛连通性对于折叠立方体网络f q 。中的距离 为d 的两点x 和,它们之间存在长为的z 路,其中h 曼f 2 “一1 h ( d ,n + 1 一d ) 且e 与h 具有相同的奇偶性对交义立方体网络c q n ( n 3 ) m s b i u s 立方体 网络m q 。( n 3 ) ,局部纽立方体网络l t q 。( n 3 ) 中的任意两点n 和 ,存在长 为的 t t t ) 路,其中d ( u , ) + 2 l s2 n 一1 目录 第四章研究了超立方体网络的边容错泛连通性,折叠立方体网络的边容错边 泛吲性以及限制边容错哈密顿性,得到了以下儿个结果: l 如果超立方体网络q n ( n 2 ) 的故障边集为f 且l f l n 一2 ,则对q n 中 任意两点“和 存在长为f 的不龠故障边的路,其中d q ,。( “_ r ) + i - 2 s2 “一 l 且2 l ( 一如。( 。) ) 如果如。( u 口) n l ,则还存在长为d q , 小,t 1 ) 的不肯故障边 的一路 2 当n 3 时,如采n 是奇数、! j l i 】f 足m 1 ) 边容错边偶泛罔的如采n 是 偶数,f “的故障边集为f 且i f i5n 一1 ,则f q 。一f 中任意一条边e 位1 :长为的 偶矧上,还位于长为的奇酬上,其中4 墨f 茎2 “,n + 1 茎7 2 “一1 , 3 在n ( 3 ) 维折叠立方体网络f q n 中,如果故障边集f 满足5 孙一3 且f 0 。一f 中的每个顶点至少与两条边相邻,则f q 。 f 龠有哈密顿斟 在第五章中,我们对本文的t 作进行了总结,并且提出了儿个有待进一步研究 的问题 a b s t r a c t i t i sw e l l - k n o w nt h a tat o p o l o g i c a ls t r u c t u r ef o ra nh l t e r c o n n e c t i o nn e t w o r k c a nb em o d e n e db yac o n n e c t e dg r a p hg = ( v e ) ,w h e r ev i st i l es e to fp r o c e s s o r s a n dei st h es e to fc o n l m u n i c a t i o nl i n k si nt h en e t w o r k t h en e t w o r kt o p o l o g y d e t e r m i n e sh o ww e l lt h ep r o c e s s o r sc a nw o r kc o o p e r a t i v e l yo n eo ft h ec e n t r a l i s s u e si ne v a l u a t i n ga ni n t e r c o n n e c t i o nn e t w o r ki st os t u d yh o ww e l lo t h e re x i s t i n g n e t w o r k sc a l lb ee m b e d d e di n t ot h i sn e t w o r k t h ep a n c y c l ep r o b l e ma s k si fa c y c l eo fl e n g t h i sas u b g r a p ho ft h en e t w o r kw i t ha n yp o s i t i v ei n t e g e r t h e c o n c e p to fp a n c o n n e c t i v i t yg e n e r a l i z et h ec o n c e p to fp a n c y c l i c i t y i fan e t w o r ki s p a n c o n n e c t e d ,i ti sa l s op a n c y c l e s i n c ev e r t e xf a u l t sa n de d g ef a u l t sm a yh a p p e n w h e nan e t w o r ki su s e d ,i ti sp r a c t i c a l l ym e a n i n g f u lt oc o n s i d e rf a u l t yn e t w o r k s i nt h i sd i s s e r t a t i o n ,w ed i s c u s st h ep a n c y c l i c i t y ,p a l l c o n n e c t i v i t y ,e d g e f a u l t t o l e r a n tp a n e y c l i c i t ya n dp a n c o n n e c t i v i t yo fs o m ei m t w o r k s i tc o n s i s t so ff i v e c h a p t e r s t nt h ef i r s tc h a p t e r ,w ei n t r o d u c eg r a p h t h e o r e t i c a lt e tm i n o l o g ya n dn o t a t i o n u s e di no u rd i s c u s s i o nw ea l s oi n t r o d u c et h ec o n c e p t so fp a n c y c l i c i t y ,p a n c o n n e e t i v i t ya n ds o n 2 ew e l l k n o w nn e t w o r k s t h e nw el i s ts o l n ek n o w nr e s u l t so n t h e m i nt h es e c o n dc h a p t e r w eb e g i nt os t u d yt i l ep a n c y c l i c i t 3 o fs o m en e t w o r k s w ef i r s ts t u d yt h ee d g e p a n c y c l i c i t yo ff q 。w ep r o v e dt h a te v e r ye d g eo ff q , ,。 l i e so nc y c l e so fd i f f e r e n tl e n g t h sa c c o r d i n gt ot h ep a r i t yo fn :w ea l s op r o v ee v e r y e d g eo fc q n ( o rl t q n ) l i e so nac y c l eo fe v e r yl e n g t hf r o m4t o2 ”i n c l u s i v ef o r n22 ;t h e nw ep r o v et h a tak i n do fh y p e r c u b e - l i k en e t w o r k si sv e r t e x p a n c y c l i c a sa na p p l i c a t i o nw ep r o v es o m ev a r i a t i o n so ft h eh y p e r c u b ew i t hl o w e rd i a m e t e r a r ea l lv e r t e x - p a n c y c l i ci nau n i f i e dm o d e l i nt h et h i r dc h a p t e r ,w ec o n s i d e rt h ep a n c o n n e e t i v i t yo fs o m en e t w o r k sf o r a n yt w od i s t i n c tv e r t i c e sza n dyi nf q n w i t hd i s t a n c ed ,f q nc o n t a i n sa nx y p a t h o fl e n g t h w i t hh 2 “一1s u c ht h a t a n dhh a v et h es a m ep a r i t y ,w h e r e h d ,n + i d ;f o ra n yt w od i f f e r e n tv e r t i c e s 乱a n d i nc q ( o rm q no r l t q 。) ( n 3 ) :t h e r ee x i s t sa “ - p a t ho f l e n g t h w i t hd ( u ,u ) + 2s s2 “一1 i nt h ef o r t hc h a p t e r ,w es t u d yt h ee d g e f a u l t t o l e r a n tp a n e o n n e e t i v i t yo ft h e 日录 h y p e r c u b e s ,t h ee d g e f a u l t t o l e r a n te d g e - p a n c y c l i t yo ft h ef o l d e dh y p e r c u b e sa n d l h er e s t r i c te d g e f a u l t t o l e r a n th a m i l t o n i c i t yo ft i l ef o l d e dh y p e r c u b e s t h er e s u l t s g e n e r a l i z es o m ek n o w n r e s u l t s 1 i fq 。( n 2 ) h a sa tm o s tn 一2f a u l t ye d g e s t h e nf o ra d yt w od i f f e r e n t v e r t i c e sua n dut h e r ee x i s t saf a u l t f l e ew p a t ho fl e n g t h w i t hd q ,( i t ,) + 2 2 “一1a n d2 l ( e d q 。扣,u ) ) m o r e o v e r t h e r em u s te x i s taf a u l t f l e e 。p a t h o f l e n g t hd q 。( ) i fd q 。( “, ) 一l 2 f o r 佗3 ,i fn i s o d d ,t h e nf q 。i s ( r z 1 ) 一e d g e - f a u l t t o l e r a n te d g e b i p a n c y c l i c ;i f ,z i se v e na n df q 。h a sa tm o s tn 一1f a u l t ye d g e s t h e ne v e r y n o a f a u l t ye d g eo ff q 。l i e s0 1 2 af a u l t f r e ec y c l eo fe v e r ye v e nl e n g t hf r o m4t o2 。 a n de v e r yo d dl e n g t hf r o mn + lt o2 ”l 3 i ff q n ( n 3 ) h a sa tm o s t2 n 一3f a u l t ye d g e s ,w h e r ee a c hv e r t e xi si n c i d e n t w i t ha tl e a s tt w of a u l t f r e ee d g e s ) t h e nt h e r ee x i s t saf a u l t f r e eh a m i l t o n i a nc y c l e c o n c t u s i o u sa n ds o m ep r o b l e m st ob es t u d i e df u r t h e ra r ei nt h ef i f t hc h a p t e r 第一章预备知识 我们所说的互连网绍- ( i n t e t c o n n e c t i o nn e t w o r k ) 是泛指一些组件通过通讯信道 包括有线的和无线的) 按照一定的点对点的方式相互连接而构成的系统这些组 牛可以足计算机子网络、计算机、计算机内部的处理器、存储器、通信设备、其他 元件或设备等这些组件之间的连接方式是决定网络性能和价格比的一个主要冈 煮,因此研究网络组件之间的连接方式显得尤为重要网路中组件和组件之间的连 暖方式称为该网络的拓扑结构( t o p o l o g i c a ls t r u c t u r e s ) 在分析网络拓扑结构时人 仃通常把网络中组件抽象成一个点,把通信信道抽象成两点之间的连线那么该网 络的拓扑结构就被抽象成一个图研究网络的拓扑结构问题就归结为研究图的结 陶问题换句话说图是网络结构的数学模型,我们可以通过图论方法来研究网络 的拓扑结构 瓦连网络可以用图来模拟,冈此互连网络与图论有着密切的关系事实证明, 图是互连网络设计和分析的最有用的数学t 具,并已被计算机科学家广泛接受和 采用本章将会在第一节简单介绍图的基本概念以及在以后讨论中要用到的记号 第二节介绍图的嵌入问题及麻用背景;第三节介绍本文主要研究的儿个著名的网 络:第四节介绍一些已有结果 1 1 图论术语的介绍 本节简单介绍图的基本概念和在以后的讨论中要用到的记号文中没有定义 的有关图的术语和记号可参见恤7 】 1 1 1 图的基本概念 所渭图( g r a p h ) 是指有序三元组( u e 妒) 其中v 非空称为顶点集( v e r t e x - s e t ) v 中元素称为顶点一e 矗e 列( 或点( p o i n t ) ) ;e 称为边集( e d g e 纠,e 中元素称为j z ( e d g e ) ; 而妒是e 到v v 的映射,称为关联函数n n c i d c 血n c t i o n ) 妒描述了边与顶点 l 2 中国科学技术大学博士学位论文 之间的关联关系若对每个( z ,口) ,( e ) 均有( g ,z ) 曲( e ) ( 这样的两条边称为 对称边扣m m e 打 ce d g e s ) ) ,则称图g 为无向图( u n d i r e c t e dg r u p m :否则就称为有向 图( d i ,u c t e dg r a p h e 或d i g r a p h ) 显然,无向图可以看成足特殊的有向图( 对称有向图) 。 我们把e 中的元素e 直接表示成v v 7 中的元素( t ,) ,记e = ( n9 ) 此时,边 与顶点之间的关联关系已明确、j j ! | ju 简记( 1 i e l7 ) = ( u e ) ,在本文中我们采用这 种简单记号 在无向图中的边用无序对( z ,y ) 来表示,两顶点z 与口称为边( t ) 的两个端 点r e n d v e r t i c e s ) 边与它的两端点称为关联的( i n c i d e n t ) ,与同一条边关联的两端 点或者与同一个顶点关联的两条边称为相邻的( a d j a c e n t ) 两端点相同的边称为 ( 1 0 0 p ) 具有相同的两个端点的两条边称为平行边佃u r 乜! f e fe d g e s ) 或重边r 7 n “l t i e d g e s ) 无环并且无平行边的阁称为简单图( s i m p l eg m p h ) 设( k e ) 是图,v 中元素的个数w 和e 中元素的个数e ,即”= i v i 和e :l e l 分 别称为该图的顶点数或阶r o m e rj 并1 1 边数r s i :e j 设g 是无向圈,z v ( c ) 的顶点度一 t e xd e g r e e ) 定义为g 中与、r 关联的边的 数日,i d 为d g ( z ) 设3 j 和g 是图g 中两顶点连接z 和长度为k 的x y j g ( p a t h ) 记为z 路是指 顶点观和边e ,交错出现的序列 p = x i o ( = t ) 龟i 孔l e i j 巳k x i ( = 9 ) 其中与边e i ,相邻的两顶点托。和她,恰好是岛,的两个端点且除点。和外,其 余的顶点互不相同,有时我们简记p = x x 。x i 。_ 1 9 z 和g 称为p 的端点( e n d v e r t i c e s ) ,其余的顶点称为内部点( i n t e r n a lv e r t i c e s j p 中边的数 = ia 称为p 的长度 两个端点相同的路称为圈( c y c l e ) 包俞图中所有顶点的路称为哈密顿路m 。m i l t 。i n n p a t h j 包含图中所有顶点的陶称为哈密顿圈r h a m i l t o r d a nc c l ej 图g 中最短斟的 长度称为g 的围长( g i r t h ) ,记为9 ( g ) 图g 中两顶点z 和之间的最短路的长度称 为两点间的距离( d i s t a n c e ) ,记为d g ( 。,) ,当图g 明确时,简记为d ( z ,9 ) 图g 中任 l1 图论术语的介绍 3 意两顶点z 和之间的距离的最大值,称为图g 的直径( d i a m e t e ;j - 记为d ( g ) 两个图g 和h 称为是同构的( i s o m o 1 时,主图日模拟客图g 的有效率将降低 如果g 同构 i 日的某一个子图t ,j i i l j g 到t 的任何一个同构映射0 可以扩充 为g 到h 的一个嵌入妒这种嵌入称为同构嵌 k ( i s o m o r p h i ce m b e d d i n g ) 同构嵌入 是最理想的,冈为它是点对点的,而且当窖图被用来表示一个算法的通信模式时, 在主图运行该算法与客图上运行该算法有相同的速度在这种情况下,主图能以同 样的速度有效的模拟客图 负载( 1 0 a d ) 是指当客图g 被嵌入土图h 后,g 用到h 的某一个顶点的最大次 数 毋容置疑,最好的嵌入应是这两个参数都很小冈此最理想的嵌入是同构嵌 入,即客图同构丁- 主图的某个子图冈为此时膨胀数和负载都是l 路是总线网络( b u sn e t w o r k ) 或线形阵列网络( 1 i n e a ra r a yi m t w o z k ) 的托扑结构 斟是环网f l o o pn e t w o r k ) 的拓扑结构环网是最通用的,最简单的且足最有用的互 联网络之一本文主要研究路和l 割在网络中的同构嵌入问题 如果图g 含有长为的躺,其中9 ( g ) ”( g ) ,g ( g ) 是图g 的例长,v ( g ) 是 图g 的阶,称图g 是泛圈的( p a n c y c l i c ) 如果图g 足泛崩的,则一定是哈密顿的网 络是否具有泛吲性可以度量该网络是否可以嵌入任意长度的矧 泛时陛的概念被推广到点泛陟| | 洼【2 l j 和边泛列性阱如果图g 的每个顶点位 丁长从g ( g ) 到v ( g ) 的幽上,则称g 是点泛圈的( v e r t e x p a n c y c l i c ) 如果图g 的每条 边位于长从g ( a ) 到v ( a ) 的削上,则称g 是边泛圈的f e 曲e p a n c y c l i c ) 显然边泛吲 的图一定是点泛蚓的 如果图g 中的任意两个顶点之间存在一条哈密顿路,则称g 足哈密顿连通的 ( h a m i l t o n i a nc o n n e c t e d ) 如果图g 中的任意两个顶点z 与g 之间有长为的路其 驵2 图的畎入年i i 它的州络意义 7 哈傅顿性 吣膏钡琏通儿 泛i 铡住 点泛嘲r l : 边泛瞄他 泛连通什 图12 :炎哈崭顿悱的也禽关系 中d g ( 。,9 ) s ”( g ) 一1 ,“g ( z ,口) 足图g 中z 与y 之间的距离! l l i j 称g 足泛连通 的船n c o n n e c t e d ) f 3 1 | 显然,泛连通的图一定足喻密顿连通的 哈密顿性、哈密顿连通性、泛矧性、点泛吲性、边泛吲性、泛连通性统称为类 哈密顿性,它们之间的包龠关系见图1 2 冈为二部图不含奇嘲,故对二部图提出了偶泛尚的概念如果图g 含有长 为e 的偶吲,其中9 ( c ) s ”( g ) 称图g 是偶泛圈的一一一p a n c y c l i c j 【3 讣如 果图g 中的任意两个顶点z 与y 之间有长为的路,其中如( r ,) f ”( g ) 一 1 且2 1 ( e d c ( x ,) ) ,则称g 是偶泛连通的一”一p a n c o n n e c t e d j 【32 1 一个大型网络在使用过程中,它的某些结点或连线难免发生故障:故考虑存 在故障的网络具有实际意义在文献【2 5 】中,t t s i e h 等人提出了点容错哈密顿性和 边容错哈密顿性,用来度量网络的容错哈密顿性文献 2 9 】 f 5 4 】将此概念推广为 点( 边) 容错哈密顿连通性,容错哈密顿性,容错哈密顿连通性及容错泛阁性等概念 如果对图g 的任意故障点( 边) 集f v ( a ) ( e ( g ) ) 且f f is ,图g f 仍是哈 密顿的( 哈密顿连通的,泛圈的,泛连通的) ,称图g 为k 点r 迫,容错哈密顿的伶密顿 连通的,泛圈的,泛连通的j 如果对图g 的任意故障集f v ( a ) u e ( g ) 且1 f 【墨k 图g f 仍是哈密顿的( 哈密顿连通的,泛嘲的,泛连通的) ,称图g 为容错哈密顿 的伶密顿连通的,泛圈的,泛连通的,文献【6 1 , 3 2 1 ,【2 3 1 ,【2 6 , 1 2 】研究了不同网络 8 中国科学技术大学博士学位论文 的上述容错性能 1 _ 3 几个著名的网络 本节将介绍几个著名的网络,它们一般都具有简单的递归结构和高对称性、高 容错性、简单结构的可嵌入性、简单路由选择算法和易扩充性等许多好的性质 1 3 1 起立方体网络 0 0 0 0 圈13 超:方体刚络q 1 ,q 2 和q 3 超立方体网络的拓扑结构是指n 维立方体,通常记为q 。它的图论模型是一 个简单无向图q 。= ( ke ) h a r a r y 【2 0 】己列出它的许多等价定义最常见的是如下 定义 q 。的顶点集由所有长为n 的二元字符串组成,即 v = z x 一1 x l :z t o ,1 ) ,i = 1 2 ,n ) ; 两顶点茁= 茁。z 1 z l 和y = y 一】y l 在q 。中相邻甘:l 旧一y d = 1 即有且仅有一个坐标不同 图1 3 所示的是超立方体网络0 i ,q 2 和q 3 n 维超立方体网络有下面一些性质 0llllliq 8中国科学技术大学博士学位论文 的上述窖错性能 1 ,3 几个著名的网络 本节将介绍儿个著名的网络它们一般都具白简单的递归结构和高列称性、高 容错性、简单结构的可| 撮入性、简单路由选择算法和易扩充性等许多好的陆质 1 3 1 超立方体网络 图l3 一超i 冉 奉州詈抖0 i ,q t u 0 3 超立方体网络的拓扑结构是指“维立方体,通常记为臼。它的图论模型是一 个简单无向图q ,。= ( ue ) h a r a r y 【2 0 】已列出它的许多等价定义最常见的足如下 定义 q 。的顶点集由所有长为n 的二元字符串组成即 y ;f z ,z 。一1 z 1 :乩 0 1 ) ,i = 1 2 ,n ) 两顶点z :t 。t 。z i 和9 = 轴鼽1 目1 在0 。中相邻* 羔i 旧一机 一1 即有且仅有一个坐标不同 图1 3 所示的是超立方体网络q hq 2 和q 3 t t 维超立方体网络有f 面一些性质 ,。维超立方体网络有f 面一些性质 8 中国科学技术大学博士学位论文 的上述容错性能 1 _ 3 几个著名的网络 本节将介绍几个著名的网络,它们一般都具有简单的递归结构和高对称性、高 容错性、简单结构的可嵌入性、简单路由选择算法和易扩充性等许多好的性质 1 3 1 起立方体网络 0 0 0 0 圈13 超:方体刚络q 1 ,q 2 和q 3 超立方体网络的拓扑结构是指n 维立方体,通常记为q 。它的图论模型是一 个简单无向图q 。= ( ke ) h a r a r y 【2 0 】己列出它的许多等价定义最常见的是如下 定义 q 。的顶点集由所有长为n 的二元字符串组成,即 v = z x 一1 x l :z t o ,1 ) ,i = 1 2 ,n ) ; 两顶点茁= 茁。z 1 z l 和y = y 一】y l 在q 。中相邻甘:l 旧一y d = 1 即有且仅有一个坐标不同 图1 3 所示的是超立方体网络0 i ,q 2 和q 3 n 维超立方体网络有下面一些性质 0llllliq 1 3 几个著名的嘲络 9 性质1q n 有2 “并顶点,是n 正则的,有n 2 n 一1 条边 性质2q ,。的直径是n 性质3q 。是二部分图 性质4q 。是c a y l e y 图 性质5q ,。足点和边可迁的 1 3 2 折叠立方体网络 在文献【1 6 中,e 1 a m a w y 和l a t i f i 提出n 维折叠立方体网络f q ,。的概念,它 是通过在n 维超立方体网络q 。中添加2 1 条边i 叮得到的新网络即v ( f q 。) = 七。z 一1 ,z 1 :$ i o ,1 ,i = 1 ,2 ,n ) ,顶点z = x n x 。一1 t 1 干n y = 掣。一1 y l 相邻甘掣= 可。一l y l = z n z ,h 砧。1 孟。锄一l z l ,其中1 i 墨n ( 此时称( z ,) 为 正常边) ;或y = 鼽珈一1 y 1 = x n x l i 1 = i ,其中6 = 1 i = 0 ( 此时称( z ,y ) 为 补边j ,顶点= x n x 。一1 i 1 = j 称为z 的补点 图14 所示的足折叠立方体网络f q 3 和f q d f 口3 f 0 4 圈l4f q 3 与f 仉( n 边表示补边) 在文献【1 6 】中,e l a m a w y 和sl a f i f i 等人研究了折叠立方体网络的性质n 维 折叠立方体网络显然和n 维超立方体网络具有相同的顶点数目边数比n 维超立 方体网络多2 ”1 条n 维折叠立方体网络的连通度是n + 1 ,直径是! 学1 它具有 l o中国科学技术大学博士学位论文 和超立方体铡络类似的高对称性结构、简单的路由算法撕它的直径儿乎是同样规 模的超立方体网络的一半,因此折叠立方体网络被看作超立方体网络的一个很好 的替代者 1 3 3 交叉立方体网络 a ) c 0 3 图l5 变叉t 打体叫络c o , 3 和g 0 4 e f e 在文献【1 4 ,1 5 】中提出了交义立方体网络 具体定义如下:记r = ( ( o o ,o o ) ,( 1 0 ,1 0 ) ,( o l ,1 1 ) ,( 1 1 0 1 ) 若( z ,) r ,则 记。一y n 维交义立方体网络,记为c q 。,是指这样的一个圈它有顶点集 v = z :x = x n - 1 x n 一2 x l t 0 ,x i 0 ,1 ) ,0si 曼n l 两顶点z = x z 。- - i 一2 x l z o 和= 一m y h y l y o 之间有边相连当且仅当存在 个j ( 0 j 兰7 l 一1 ) 使得 ( 1 ) 9 2 n i 奶+ l 一一1 协+ h ( 2 ) x j y j , ( 3 ) 如果j 是奇数,那么有鲫一l = 巧一1 ,并且 驵3 几个著名的列络 ( 4 ) 对每个0si f ;1 ,则f 中的最短“”路恰含一条补边 证明设d h ( u ,”) = h 墨l ;j 冈为d h ( u ,i ) = 7 l ,故”5 如果t :0 。中有一条 最短t c ”路龠有补边,由定理2 24 ,路p 恰含有一条补边e = ( z ,i ) 设妇( u z ) = i 妇( 苗 ) = r m 则有d f q 。( u ,z ) = d h ( u ,z ) = i ; ,冈为d f q ,。( n ,口) s ,所以f q 。中的最短n 路一定龠补 边,又由定理2 2 4 知,该最短路恰含一条补边定理得证 口 注如果n 是奇数,且d h ( u ,”) = i n ,则在f q ,。中既有不含补边的最短u u 路 也有恰龠一条补边的最短u ”路 定理2 2 6 如果n 维折叠立方体网络f 0 ,含有奇矧,! i ! | j 最短奇h 恰龠一条补 边,且矧长是n + 1 证明如果f q 。含有奇圈,则由定理2 2 1 知,n 足偶数且它的任一奇陶一定 含有补边义困为f q 。中的任意两条补边不相邻,所以它的任一奇蚓一定龠有非补 边设c = ( v o ,u 1 ,”2 f ,如) 是f q 。中长为2 + 1 的最短奇剐,且8 f = ( 毗,”“1 ) 不 是补边下面考虑斟c 中的两条路p l = ( o ,v h 一,) 与p 2 = ( ”, 0 2 t ,v o ) 如 果p l 不是f q 。中的最短v o y 路,而p 是一条最短y o 路,! j ! l jp 1 u p 7 中任意削c 的 长度都小于2 9 + l ,故e 是一个偶吲,所以两条路p l 与p7 的长度具有相同的奇偶性 类似可得两条路p ,与p 2 + e 的长度具有相同的奇偶性所以两条路p 1 与p 2 + e f 的 长度具有相同的奇偶性,口p c 是偶圈,矛盾故p l 是最短路同理可证,p 2 也是最 短路由定理2 24 知,嘲c 至多含有两条补边义l 天| 为c 是奇鼯| 1 由定理2 2 2 , 阁g 恰含有一条补边 由定理2 2 3 知,皓l c 的长度至少为n + 1 义由定理2 23 知f 0 。中任一补边 位于一个长为n + 1 的尚中由此可得,最短奇湖的长度是n + 1 定理得证 e l i 2 2 2 折叠立方体网络的边泛圈性 在超立方体网络q 。中,由最左端分量分别是0 和1 的所有点导出的n 一1 维子 立方体记为q o 一1 和q :- 1 j 则f q 。的2 ”一1 条补边连结顶点o u 和1 a ,其中o u q ! _ 1 2 0 中国科学技术大学博士学位论文 l u q :l 且v ( q 。一i ) 引理2 2 1 ( l i 等人【3 2 1 ) 在q 。中,如果n 2 ,则育如下结论: ( a ) 对q 。中任意两点z 和y ,有长为f 的z g 路,其中d q ,i ( z 目) 2 n 一1 , 且与叱,。( z ,y ) 具有相同的奇偶性: ( b ) e 。中的每一条边位丁长为的陶上、其中4 2 ” 定理2 2 7 折叠立方体网络f ? ,。( n22 ) 的每一条补边位丁一长为f 的偶上 其中4s s2 n 证明设e 是f q n 中的一条补边4 i 妨设e = ( o “,l 。) ,其中。目y ( q :一1 ) , 1 y ( 娥一1 ) 取职一1 中的一条边( o u o w ) 以及娥一1 中的一条对应边( 1 u ,1 5 ) 下 证边e = ( 0 u ,1 i ) 位丁长为l 的偶矧上,其中4 曼f 2 n 将记为f = f 7 + 7 7 + 2 、其中1 7s2 1 1 1 f 7s2 - 1 1 且f ,和c ,者$ 为 奇数由引理2 21 ( a ) 知,在q o l 中存在氏为7 的连接o u 和o “的路p 在q :一1 中 存在长为的连接l i 和1 5 的路p ”【天| 此p 7 + ( o u ,1 i ) + p ,+ ( 1 i ,0 n ) 是f q ,。中含 有边e 长为的嘲( 见图2 1 ( a ) ) 定理得证 口 q ! 一,0 :卜。q ! 一。 ( b ) 图2 1 连用2 27 与定坪2 28 嘲的幽示 ( c ) 定理2 2 8 在折叠立方体网络f q 。( n 2 ) 中,如果,;足奇数则它的每一条 边位丁长为的偶圈上,其中4 曼p 2 n ;如果n 是偶数,则它的每一条边位t f 22 折叠立方体州络的泛| 卷| 性 2 l 为的偶刚上其中4 2 ”,且还位丁长为f 的奇蚓上,其中n + 1sps2 “一l 证明如果n 是奇数则由定理2 , 2 1 知f c 2 。是一个二部图由引理2 2 1 ( b ) 及定理2 2 7 知结论成立 如果n 是偶数,则由定理2 2 1 知,f q 。不是一个二部图r h 引理2 2l ( b ) 及定 理2 2 7 知,f q 。的每一条边位丁长为的偶吲上,其中4s s2 “ 下证当t t 是偶数时,f 仉的每条边位丁长为的奇削上,其q = | n + 1s 曼 2 n 一1 分两种情形来讨论 情形j 边e 是一条补边记e = ( 玑a ) 冈为,t 是偶数,故u 和i 属丁q ,。的二部 划分的同一部分,且“仉( u ,日) = n , ( 0 一1 ) 一n ) = ( ( 一1 ) - d 。,。( “1i ) ) 是整数由引 理2 2 1 ( a ) 知,在q 。中存在长为一l 的连接t l 和n 的路p ,其中,。( p 一1 ) 2 “一2 冈此,圈p + e 是f q 。中肯有边e 的长为的奇陆| 情形2 边e 不是一条补边记e = ( m t ,) 此时u 和t ,属丁q 。的二部划分的 不同部分不妨设e = ( 0 “,1 u ) ,则( 1 u ,o i ) 是f q 。中的一条补边,且有d ;t ( oc 6 - o z 2 ) = 几一1 因为与( n 一1 ) 都是奇数,且 ( 即一2 ) 一( n 一1 ) ) = ( ( 一2 ) 一d q ,。( o n ,0 i ) ) 是整 数,由引理2 2 1 ( a ) 知,在q n l 中存在长为奇数( 一2 ) 的连接o u 和0 u 的路p 其 中n 一1 ( 一2 ) 墨2 n 一1 记0 :一l 中氏为2 “一1 的连接o 和o i 的路为p 0 如果n + 1s 2 n 一1 + 1 ,则p + ( o 虬l u ,腑) 足f q 。中龠有边e 的长为的奇 斟,其中n + 1 茎2 7 1 + 1 ( 见图2 1 ( b ) ) 如果2 n 一1 + 3 兰p 兰2 n 一1 ,令7 = g - 2 n 一1 ,则有2s 7 2 “一2 不妨设p o = ( o u ,0 u 1 ,0 “2 ,0 u 2 。- t _ 2 , o i ) 冈为q 0 1 中的每条边( o u 。,o u 。+ 1 ) 在q i l 中有对应 边( 1 u 。,l u h l ) ,所以矧c = ( 0 u ,o u t ,i u l ,l l 2 ,0 u 2 ,0 u 3 ,l u 3 ,o u e ,一1 ,1 , t e ,一1 ,1 u n o u e , 0 u l ,0 札,+ 2 ,0 u 2 。- 2 o 百,l “,0 u ) 是f q 。中含有边e 的长为2 1 + 1 + = 的 奇圈( 见图21 ( c ) ) 定理得证 口 2 2 中国科学技术大学博士学位论文 一一 2 3 交叉立方体网络的边泛圈性 由第一章中的定义易知,交义立方体网络c q 。可以递归定义如下: e q i 是具有两个顶点的完全图分别用。和1 来记它的两个顶点当n 2 时, g q 。可以由两个e q 。1 添加一些边得到记其中的一+ c q n 一- 为e 哦它的顶 点集为: v ( e q :_ ) = ( o x ,2 z l x o :“= 0 o rl 记另一个c q 。为g q :一。,它的顶点集为: v ( g q :一1 ) = l y 2 ”l o :玑= 0o r l ) 一 两个顶点0 z 。一2 z l 。v ( c q o 一1 ) 和l y ,2 y t y o y ( g q :一1 ) 有边相连当且仅 当 ( 1 ) z 一2 = 一2 当n 是偶数,且 ( 2 ) z 2 件l 。2 。如。上l 抛。,其中0si 2 “由引理2 3 2 知,吲c 是2 临界的故 在c 上存在一条临界边( u l ,。l ) 且托l ,u l ) e 由引理2 3 1 知,乜与v l 在r 中的 邻点“r 与口r 相邻、即似r ,口n ) e ( r ) 由归纳假设知,在r 中存在长为4 墨 6 的吲1 夭i 此p ,= c 一( u r , r 1 是r 中连接“咒与u r 的路令p = c 一( l l , l ,。l ) , 则p 龠有边e 且p 十( 1 - l ,” ) + p + ( “ ,l ) 为c q 。中俞有边e 的长为的吲 当2 n 一1 + 4 e 2 n 时,令= 一2 n ,则有4 2 ”1 由归纳假设及 引理2 3 2 知,在三中存在长为2 佗_ i 的龠有边e 的2 临界圈c 故在c 上存在一条临 界边( t l ,。l ) 且( “t l ) e 设n 和 分别是“l 和 u l 在r 中的邻点则( t ”r ) e f 剐由归纳假设知在r 中存在长为7 的陶c 7 龠有边( l r ,”n ) 令p = c - - ( “l ,t l ) 且p 7 = c ,一( p r ,札r ) 则p + ( u l , 凡) + p + ( 札疗t t l ) 足c q 。中长为的含有边e 的 阁( 见图2 3 ( a ) ) 情形2 边e 是工与r 之间的交义边记e = ( t t l ,u m 根据。的不同奇偶性,分别构造长为4 和5 的含有边e 的蚓如下 易验证当z l z o 一l 口。时,有x l x o 一9 * y o 与2 i i o 一9 l 面 当n 是偶数时,不妨设t 也= ( 0 z r 。- 2 x n

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论