（应用数学专业论文）纽立方体网络的边泛圈性和hamilton性.pdf

摘要 我们通常用一个连通的无向图g = ( ve ) 作为互连网络的拓扑结构，这时 图g 的顶点代表网络中的组件，组件之间的通信联系用相应顶点之间的连线来表 示网络的拓扑结构决定着该网络的性能一个网络是否可以嵌入任意长度的圈， 是否是h a m i l t o n 连通的，是度量网络优劣的重要性能本文研究纽立方体网络， 主要得到了以下结果： 1 证明了当礼为任意大于2 的奇数时，n 维纽立方体网络中的每条边都在长 为4 到2 n 的圈上 2 证明了当竹为任意大于君的奇数时，n 维纽立方体网络是h a m i l t o n 连通 的 全文共分四章，其中第一章介绍本文用到的一些图和网络的基本概念；第二 章得到了纽立方体网络关于边泛圈性的结果；第三章得到了纽立方体网络关于 h a m i l t o n 连通性的结果；最后一章对本文的工作进行了总结，并且提出了几个有 待进一步研究的问题， l l l a b s t r a c t i ti 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 ni n t e r c o n n e c t i o nn e t w o r kc a nb em o d e l l e db yac o n n e c t e dg r a p hg = ( k e ) ， w h e r evi st h es e to fp r o c e s s o r sa n dei st h es e to fc o m m u n i c a t i o n l 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 yd e t e r m i n e sh o ww e l l t 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 y o n eo ft h ec e n t r a li $ s u e si n e 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 yi fi tc o n t a i n sc y - c l e so fa l lp o s s i b l el e n g t h sa n di fi t i sh a m i l t o n i a nc o n n e c t e d t h e t h e s i sc o n s i d e r st h et w i s t e dc u b en e t w o r k sa n do b t a i n st h ef o l l o w i n g r e s u l t s 1 f o ra n yo d d 仃23 ，e a c he d g eo f 佗- d i m e n s i o n a lt w i s t e dc u b e l i e so nac y c l eo fe v e r yl e n g t hf r o m4t o2 ” 2 f o ra n yo d d 礼3 ，t h et w i s t e dc u b ei sh a m i l t o n i a nc o n - n e c t e d t h i st h e s i sc o n s i s t so ff o u rc h a p t e r s i nt h ef i r s tc h a p t e r ，w e i n t r o d u c eg r a p h t h e o r e t i c a lt e r m i n o l o g ya n dn o t a t i o nu s e di no u r d i s c u s s i o n i nt h es e c o n dc h a p t e r ，w ed i s c u s st h ee d g e p a n c y c l i c i t y o ft w i s t e dc u b e s i nt h et h i r dc h a p t e r ，w ed i s c u s st h eh a m i l t o n i a n c o n n e c t i v i t yo ft w i s t e dc u b e s c o n c l u s i o n sa n d s o m ep r o b l e m st ob e s t u d i e df u r t h e ra r ei nt h ef o r t hc h a p t e r 第一章预备知识 1 1 图论术语的介绍 本节简单介绍图的基本概念和在以后的讨论中要用到的记号文中没有定义 的有关图的术语和记号可参见【2 8 ，2 9 1 所谓图( g r a p h ) 是指有序三元组( u e ，妒) ，其中y 非空称为顶点集( v e r t e x - s e t ) ，e 称为边集( e 匆e s e t ) ，而妒是e 到矿中元素有序对或无序对簇v v 的 函数，称为关联函数( i n c i d e n t f u n c t i o n ) v 中元素称为顶点( v e r t e x ) ，e 中元素 称为边( e d g e ) ，妒刻划了边与顶点之间的关联关系若v v 中元素全是有序对， 则( ke ，1 j f ，) 称为有向图( d i r e c t e dg r a p h ) 若v x v 中元素全是无序对，则e ，妒) 称 为无向图( u n d i r e c t e dg r a p h ) 我们把e 中的元素e 直接表示成v v 中的元素( 。，! ，) ，记e = ( 善，y ) = x y 此 时，边与顶点之间的关联关系已明确，则可简记( v e ，妒) = ( v e ) 两顶点。与9 称 为边鲫的两个端点( 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 ) 具有相同的两个端点的两条边称为平行边( p a r a l l e l e d g e s ) 或重边( m u l t i e 由e s ) 无环并且无平行边的图称为筒单图( s i m p l eg r a p h ) 设( v e ) 是图，y 中元素的个数v s u e 中元素的个数g ，即 = | v l 和= l e i ，分 别称为该图的顶点数或阶( o r d e r ) 和边数( s i z e ) u 和都是有限的图称为有限图 ( f i n i t eg r a p h ) 如不加特殊说明本文以下所涉及的图均为有限简单无向图 顶点z v ( v ) 的邻点集记为n a c z ) 顶点z 的顶点度( v e r t e xd e g r e e ) 定义 为g 中与z 关联的边的数日，记为d g ( 。) 对简单图有如( 。) = j n d = ) i 如果 对g 的每个顶点2 均有d a ( z ) = k ，我们称g 是k 正则的( k - r e g u l a r ) 中国科学技术大学硕士学位论文 2 任何不同两顶点之间都有边相连的简单无向图称为完全图( c o m p l e t eg r a p h ) ， n 阶完全图记为k 。若无环图的顶点集可以划分为两个非空子集x 和y ，使得x 中 任何两顶点之间无边相连并且y 中任何两顶点之间也无边相连，则称该图为2 部 分图( b i p a r t i t eg r a p h ) ， x ，y ) 称为2 部划分( b i p a r t i t i o n ) 二部划分为 x ，y ) 的 2 部分图可记为( x u k e ) ，任两点若同属于x 或，则称为同色点，否则称为异色 点若x 中每个顶点和y 中每个顶点之间均有边相连，则称该2 部分图为完全2 部分图( c o m p l e t eb i p a r t i t eg r a p h ) ，记为j o m 其中i x l = m 和i y i = n 设g 和y 是图g 中两顶点，连接和g 长度为k 的路( p a t h ) ，记为硼路，是 指顶点和边e j 交错出现的序列p = $ 0 ( = z ) e 。文，e i 。( = v ) ，其中与 边e 。，相邻的两顶点。b 一，和z q 恰好是e 。，的两个端点，且除点z 和y 外，其余的顶 点互不相同，有时我们简记= ；。墨。y z 和y 称为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 ) p 中边的数目岛称为p 的长度两个 端点相同的路称为圈( c y c l e ) 本文中我们将长度为k 的路简记为r ，长度为的 圈简记为晚当为偶数时，称g 为偶圈；当k 为奇数时，称g 为奇圈包含图 中所有顶点的路称为h a m i l t o n 路( h a m i l t o n i a np a t h ) 包含图中所有顶点的圈称 为h a m i l t o n 圈f h a m i l t o n i a nc y c l e ) 图g 中最短圈的长度称为g 的圄长( g i r t h ) ， 记为9 ( g ) 图g 中两顶点和y 之间的最短路的长度称为两点间的距离( d 妇一 t a n c e ) ，记为南( 。，y ) ，当图g 明确时，简记为d ( z ，爹) 图g 中任意两顶点z 和掣之 间的距离的最大值，称为图g 的直径( d i a m e t e r ) ，记为d ( g ) 设g = ( y ( g ) ，e ( g ) ，g ) 和日= ( y ( 日) ，e ( h ) ，日) 是两个图若v ( h ) 妄 y ( g ) ，e ( h ) e ( g ) ，并且妇是如在e ( h ) 上的限制，则称日是g 的子图( s u b g r a p h ) ，记为日g 称g 是日的母图( s u p e r g r a p h ) 若日g 并且v ( h ) = y ( g ) ，则称日是g 的支撑子图( s p a n n i n gs u b g r a p h ) 图中的路和圈是该图的子图， 而h a m i l t o n 路和h a m i l t o n 圈是图的支撑子图若日g 并且v ( h ) y ( g ) ，则 称日是g 的真子图( p r o p e r5 “b g r a p h ) ，记为cg 中国科学技术大学硕士学位论文 3 设y 是v ( g ) 的非空真子集，以y 7 为顶点集，并以g 中两端点均在矿中的边 为边集，所得到的子图称为g 的由y 7 导出的子图，简称导出子图( i n d u c e ds u b g r a p h ) ，记为g i v 1 导出子图g 1 记为g 一若v = 扛 ，贝b 筒记g 一 为g 一霉 设是e ( c ) 的非空子集，以f 为边集，并以g 中由f 中的边的端点为顶点 集，所得到的子图称为g 的由e ，导出的子图，记为g 【e ，】由e 、e ，导出的子图记 为g e 若e 7 = e ) ，则简记g 一 e ) 为g e 设g 1 g ，g 2 g ，若v ( g 1 ) n v ( g 2 ) = o ，则称g l 和g 2 是点不交的 ( v e r t e x - d i s j o i n t ) ；若e ( g 1 ) n e ( g 2 ) = o ，则称g 1 和g 2 是边不交的( e e d i s j o i n t ) g l 和g 2 的并( u n i o n ) ( 记为g l u g 2 ) 是指图日，其中v ( h ) = v ( g 1 ) u y ( g 2 ) ， e ( h ) = e ( g 1 ) ue ( g 2 ) 设e 中各边端点集为v ( e 7 ) 并且有v ( e ) v ( 9 1 ) ，则 g l + 是子图日，其中v ( h ) = y ( g 1 ) 且s ( h ) = e ( c t ) u f ，若e = e ) ，则 简记g 1 + f 为g l + e 对于两个图g 和日如果存在一个双射 p ：v ( c ) 一y ( 日) ，使得0 ，y ) e ( g ) = 兮( 口( 士) ，口( ) ) e ( 日) 那么称图g 和日是同构的( i s o m o r p h i c ) ，记为g 型h ，并称日为图g 和日的一 个同构映射( i s o m o r p h i cm a p p i n g ) 如果g = h ，则称p 为图g 的一个自同构映 射( a u t o m o r p h i s m m a p p i n g ) 图g 的所有自同构构成的群，称为图g 的自同构群 ( a u t o m o r p h i s mg r o u p ) ，记为a u t ( g ) 图g 称为点可迁的( v e r t e x - t r a n s i t i v e ) ，如果对于任意的两点茹，g y ( g ) ，存 在图g 的自同构p ，使9 ( 。) = y 图g 称为边可迁的( e d g e t r a n s i t i v e ) ，如果对于 任意的两条边e l = 伽，e 2 = x y e ( g ) ，有g 的一个自同构日，使得口( ( u ， ) = 缸，9 即将边e l 映到边e 2 设mce ( g ) ，如果m 中任意两边在图g 中是不相邻的，则m 称为图g 的一 中国科学技术大学硕士学位论文4 个匹配( m a t c h i n g ) 如果图g 的匹配j l i f 的端点集等于y ( g ) ，则 彳称为图g 的完 备匹配( 筘咖c t - m a t h i n g ) 1 2 笛卡尔乘积图 设a 和b 是两个有限集，a 和b 的笛卡尔乘积axb = ( n ，b ) ：b a ，b 占 为使记号简单起见，在不至于引起混淆的情况下，篱记a x b 中元素妨为曲 同样地，简记礼重笛卡尔乘积a ix a 2 a 。= ( 口1 ，d 2 ，a n ) ：啦a ，i = l ，2 ，n ) 中的元素( 0 1 ，0 2 ，) 为n l n 2 a n 笛卡尔乘积方法是一个重要的构图方法，它是由s a b i d u s s i ( 1 9 5 7 ，1 9 6 0 ) ( 参见 f 2 4 ，2 5 1 ) 首先提出来的笛卡尔乘积方法是从已知图构造更大图的有效方法由这 种方法构造的图保持了因子图的许多性质，并且它的许多的图论参数，例如直径、 顶点度、连通度等等都能由其因子图计算出来，正是由于这些好的性质，使得笛卡 尔乘积方法成为网络设计的重要方法之一 设g t = m ，厩) 是顶点数为i k i = 啦，边数为i 历i = 岛，t = 1 ，2 ，k 的 无向图图g l ，g 2 ，g 的笛卡尔乘积是一个无向图，称为笛卡尔乘积图，记 为g l x g 2 瓯，其中v ( a l g 2 瓯) = k ；两个不同顶 点z l 2 钆和”l 抛执在g i x g 2 x x g k 中相邻甘z l ，钇，z k 和l ，轨，弧 仅有一个坐标不同，不妨设为第f 个坐标，并且。蕊e ( g ) 1 3 图的嵌入 图的嵌入问题不但是图论的重要研究专题，也是网络设计和分析中重要的研 究内容互连网络的许多问题可以归结为图的嵌入问题 按照h a y e s 【1 4 】的说法，算法也可以用图g 来表示g 的顶点表示执行该算 中国科学技术大学硕士学位论文5 法所要求的设备，g 的边表示这些设备之间的连线这样的图g 叫做该算法的通信 模式( c o m m u n i c a t i o np a t t e r n ) 因此，算法能在计算机系统g 中执行当且仅当该 算法的通信模式同构于g 的子图， 在互连网络中，一个结构能是否能被另一个结构来模拟是重要的网络模拟 问题能归结为图的嵌入问题 正如前面所说，一个算法的通信模式可以用一个图来表示因此，算法在系 统中的实现就是该算法的通信模式在该系统网络中的嵌入许多多处理系统是为 。一般目的”而设计的，这意味着只要时间和空问允许，任何算法如果能给予合适 的编码总是可以在该系统中执行存在大量的算法，它们能有效的解决某些应用 问题，并且有最好的为该算法的执行而设计的通信模式对于这些算法，为达到希 望的性能，某些拓扑结构的存在性是一个重要因素因此，对于这些应用，被设计 的网络最好能在逻辑上提供个特殊的拓扑结构以确保该算法有效地执行另一 方面，有些算法只要稍作修改就可以完全适用于另外的拓扑结构，即对算法稍加修 改就能运行如果原始算法结构能被嵌入到一个新网络中，已有的算法就很容易 运行 嵌入是一个拓扑结构到另一个拓扑结构的映射，它保留某些被要求的性质文 献中讨论了各种类型的嵌入我们讨论的嵌入是指下列定义： 设g 和日是两个给定的图，图g 到h 的嵌入( e m b e d d i n 9 ) 是一个从g 到日 的映射妒：v ( g ) 一y ( 日) ，使得边( 名，y ) s ( c ) 对应日中的一条边似( z ) ，妒( g ) ) 或 者汀中一条( z ) ，妒( y ) ) 路称g 为客图( 9 u e s t ) ，h 为主图( h o s t ) ， 衡量嵌入优劣的两个常用度量是膨胀数( 度量传输延迟) 和负载( 度量处理器 的利用率) 嵌入妒的膨胀教( d i l a t i o n ) 定义为： d i t ( 妒) = m a x d t t ( 妒( x ) ，妒臼) ) ：扛，y ) e ( g ) 中国科学技术大学硕士学位论文 6 显然，存在嵌入妒：v ( c ) 一v ( h ) 使得d i l ( 妒) = l 当且仅当g 是日的子图 当d l z ) 1 时，主图片模拟客图g 的有效率将降低 如果g 同构于日的某一个子图t ，则g 到t 的任何一个同构映射口可以扩充 为g 到h 的一个嵌入妒这种嵌入称为同构嵌入( 妇d m o 印 f ce m b e d d i n g ) 同构嵌 入是最理想的，因为它是点对点的，而且当客图被用来表示一个算法的通信模式 时，在主图运行该算法与客图上运行该算法有相同的速度在这种情况下，主图能 以同样的速度有效的模拟客图 负载( 1 0 a d ) 是指当客图g 被嵌入主图日后，g 用到日的某一个顶点的最大 次数， 毋容置疑，最好的嵌入应是这两个参数都很小因此最理想的嵌入是同构嵌 入，即客图同构于主图的某个子图，因为此时膨胀数和负载都是1 路是总线网络( b u sn e t w o r k ) 或线形阵列网络( 1 i n e a ra r r a yn e t w o r k ) 的拓扑 结构，圈是环网( 1 0 0 pn e t w o r k ) 的拓扑结构形阵列网络和环网是最通用的，最 简单的，且是最有用的互联网络之一本文主要研究路和圈在网络中的同构嵌入问 题 如果对任意整数l 满足9 ( g ) ( g ) ，图g 含有长为的圈，其中9 ( g ) 是 图g 的围长，v ( c ) 是图g 的阶，称图g 是泛圈的( p a n c y c l i c ) 特别的，含有h a m i l - t o n 圈的图称为h a m i l t o n 图，或称该图具有h a m i l t o n 性如果图g 是泛圈的，则 一定是h a m i l t o n 图网络是否具有泛圈性可以度量该网络是否可以嵌入任意长 度的圈 泛圈性的概念被推广到点泛圈性【1 4 1 和边泛圈性【2 】如果图g 的每个顶点 位于长从g ( c ) 到v ( c ) 的圈上，则称g 是点泛圈的( v e r t e x - p a n c y e l i c ) 如果图g 的 每条边位于长从g ( c ) 到v ( g ) 的圈上，则称g 是边泛圈的( e 由e p a n c y c 如c ) 显然， 边泛圈的图一定是点泛圈的 中国科学技术大学硕士学位论文 7 如果图g 中的任意两个顶点之间存在条h a m i l t o n 路，则称g 是h a m i l t o n 连通的( h a m i l t o n i a nc o n n e c t e d ) 如果图g 中的任意两个顶点z 与之间有长 为的路，其中满足d a ( x ，y ) 曼fs 口( g ) 一1 ，则称g 是泛连通的( p a n c o n n e c t e d ) 显然，泛连通的图一定是h a m i l t o n 连通的 1 口l 1 4 超立方体网络 0 1 0 0 m 0 1 0 口3 o i l 口 图1 1 ：超立方体网络口1 ，q 2 ，醌和口 1 l l 1 1 1 0 起立方体网络( h y p e r c u b i cn e t w o r k ) ，亦称扎c u b e ，b i n a r yn - c u b e ，b o o l e a n “ c u b e ，通常记为仉，它的图论模型是一个简单无向图q 。= ( ke ) h a r a r y1 1 5 】已 列出它的许多等价定义，最常见的是如下定义 中国科学技术大学硕士学位论文 8 定义1 4 1 q 。的顶点集是所有长为n 的 o ，1 ) 有序二元数组( 亦称为长为n 的2 元序列( b i n a r y 厅t u p l e s ) ) ，即v = ： 正”z 。一l z 1 ：z t o ，l ，i = 1 ，2 ，一r ，n ；两 顶点$ = z 。一l z l 和y = 孙一1 y l 在矾中相邻铮皂lk 一筑 = i ，即 有且仅有一个坐标不同 图1 1 所示的是超立方体网络q l ，q 2 和q 3 n 维超立方体网络有下面一些性质 性质1 4 2 q 。有2 “个顶点j 是n 正则的i 有佗2 ”1 条边 性质1 4 3 q k 的直径d ( q 。) 是礼 性质1 4 4 q 。是二部分图 性质1 4 5 q 。是c a y l e y 图， 性质1 4 6 q 。是点可迁和迪可迁图 1 5 纽立方体网络 纽立方体是由h i l b e r s 等人f 1 7 首先提出来的，记为r q _ t o , 。的顶点集是 所有长为扎的 0 ，1 有序二元数组( 亦称为长为竹的2 元序列( b i n a r yn - t u p t e s ) ) ， 这里n 是奇数? 。中的一个顶点可以表示为u = t ，l 。一2 x l x o 定义 只= “l o 让t 1 0 o u o ，0 l 佗一1 ， o 是二元运算符”e x c l u s i v e - o r ”， 即是：0 0 0 = 0 ，1 0 1 = 0 ，0 0 1 = 1 ，1 00 = 1 t q 。可以递归定义如下： t q l 是完全图尬，由两个项点o , 1 组成当n 是大于1 的奇数时，可以将t 仉 中国科学技术大学硕士学位论文 9 分成四个部分： t q 。0 , 一0 2 ，t q 0 。, 一1 2 ，t q 翌2 ，t o 1 , 一1 2 t q 能2 由一1 = t ，一2 = j 的顶点1 t 址2 z 1 知组成，并且每个丁q 2 2 同构 于t 魏一2 t 0 。i , j2 之间的连边( t ，u ) 定义为： “= t h 、1 n 一2 2 ：1 2 ：0 ， = l 一2 霉l z o ，或一l 一2 z l z o ，如果r 一3 ( ) = 0 秽= 乱n 1 豇i i 一2 x l 茁o ，或一l 一2 z l z o ，如果r 一3 ( 让) = 1 为方便起见，用g o n 9 1 分别表示由t o o , 一0 2u 丁q 娑2 和t g ) 0 , 一1 2ut o 1 , 一1 2 导 出的子图称g 0 和g l 之间的连边为临界边；把t q 。o0 2 和丁紫2 之间，f q 。o 二1 2 和 t q 2 2 之间的连边称为交叉边 图1 2 ( a ) ( b ) 显示了这两种不同的连法 国 图1 2 ：纽立方体网络的两种连法 第二章纽立方体的边泛圈性 2 1 引言 纽立方体网络t q 。是由h i l b e r s 等人f 1 7 】提出来的种超立方体网络q 。的 变型，其直径约是超立方体的一半在文献f 1 ，1 0 ，9 ，1 7 ，2 1 】中研究了纽立方体网 络的性质 在互连网络中，一个结构能是否能被另一个结构来模拟是重要的网络模 拟问题能归结为图的嵌入问题在嵌入问题中，圈的嵌入问题是一个基本而重要 的问题圈的嵌入就是在图中寻找给定长度的圈如果对任意整数满足k fs ( g ) ，图g 含有长为z 的圈，其中后给定，口( g ) 是图g 的阶，称图g 是七泛 圈的( k - p a n c y c f i c ) 3 i 泛圈性的概念被推广到点泛圈性【1 4 】和边泛圈性( 2 i 如 果图g 的每个顶点位于长从k 到v ( a ) 的圈上，则称g 是点泛圈的( v e r t e x & - m n c v d i c ) 如果图g 的每条边位于长从到v ( a ) 的圈上，则称g 是边泛圈的 ( e e k - p a n c y c 托c ) 显然，边泛圈的图一定是点后泛圈的由定义可知? q 。不 含长度为3 的圈，c h a n g 【1 0 】证明了t q 。是4 泛圈图，徐俊明和马美杰【3 0 证明 了t q 是点4 泛圈图在本章第二小节中我们要证明t q 。是边4 泛圈图 2 2 纽立方体的边泛圈性 引理2 2 1 如果t q 中锋任意一紊边在长为4 到2 4 的圈土，那幺，t k k 2 中 的任意一条边在长为4 到2 “+ 1 ( 除了5 ) 的圈上，其中n 之3 证明令e 为t q 。j 已中的任意一条边，令z 为整数，满足4s s2 ”1 ，5 为方便起见，把丁q k k 2 中的两个? 。分剐记为? 询i 和丁锐下面分两种情况 讨论 中国科学技术大学硕士学位论文 情形j ：e = ( z 。z 舾1 z 1 。o ，牙。一l z l z o ) 是t q k 鲍中的任意交叉边 如果= 4 。 c o ：= 是t q 。k 2 中含有e 长为4 的圈 对6 s2 “+ 1 ，记t = t l + f 2 ，其中 z l = 2 ，4 如扩， 或4 s 1s2 “，4 如2 “ 如果l 4 ，由引理的假设，t q 中存在一条含有 ( a a 一1 z l z o ，z n z n 一1 x l x o ) 长为1 的圈a r 0 中存在一条含有 ( z n 一1 x l x o ，孟n z ”一1 x l x o ) 长为如的圈c 2 令 b = ( z n z n _ 1 x l x o x n x n - i x i 牙o ) z 。勘，：主耋三： 尼= e 2 一( 一1 x l x o ，z 1 x l 雪o ) 则 p l + ( z n z n l z l x o ，z n z n l z l 牙o ) + b + ( 牙n a 一1 x l x o ，牙n z n 一1 z l z o ) 中国科学技术大学硕士学位论文 是t q 。k 2 中含有e 长为的圈( 见图2 1 ( a ) ) 情形象e 是t q ：或t q ：中的边 不失一般性，设e e ( 丁破) 对4 2 铲，由引理的假设，r 固_ 娲中存 在含有e 长为的圈 对2 ，i + 1 zs2 ”1 ，记z = 1 14 - 如，其中4sp l 2 “，4s 如2 ，i 由引理 的假设，t q o 中存在一条含e 长为l 的圈岛，取一条与e 不同的边e o = ( u o ，v o ) 用e 。= ( 仉，h ) 来表示e o 在丁矾中的对应边则由引理的假设，丁q ：中存在一条 含e l 长为如的圈g 令r = g 0 一e o 且p l = g e l ，则p o + ( u d ，巩) + p 1 + ( ，v o ) 是t q 。j 已中含有e 长为p 的圈( 见图2 1 ( b ) ) 引理得证 口 丁q 挈t q 争：r q i t q ： n e，、 1 u gq 图2 1 ：引理2 2 1 证明的图示说明 引理2 2 2 当n 3 时，t q 。中的任意一条交叉边和临界边都在长为5 和7 的圈 上 证明令e 为t q 。中任意一条交叉边或临界边下面考虑三种情形： 情形je = ( ，1 一2 一2 l x 0 ，牙n * 1 3 f f2 i z o ) 若r 一3 ( 善。一1 一2 。l 跏) = 1 ，构造所要的圈如下： 中国科学技术大学硕士学位论文1 3 长为5 的圈 长为7 的圈 若p n 一3 ( x * , - 1 x 。2 2 ；1 。o ) ；0 ，构造所要的圈如下 长为5 的圈 长为7 的圈 情形兽je = ( 1 一2 x l z ：o ，一l i 2 2 ；1 2 ：0 ) 中国科学技术大学硕士学位论文 1 4 若只i 一3 ( z l z 。一2 茹1 2 ：0 ) = 1 ，构造所要的圈如下 长为5 的圈 长为7 的圈 情形3 ：e = = ( x , r - l z n 一2 z 1 ，：t n l 雪n 一2 x i z 0 ) 若r 一3 ( z 。l 札2 z 1 勘) = 0 ，构造所要的圈如下 长为5 的圈 长为7 的圈 中国科学技术大学硕士学位论文 1 5 引理得证 口 定理2 2 。3 当竹为任意大于2 的奇数时，? q k 中的每务边者f 在长为4 到扩的圈 上 证明对n 3 用归纳法证明对n = 3 ，只需证明t q 3 的每条边都在长为4 到8 的圈上 下面四个长为4 的圈覆盖了t q 3 的所有边： ， ， ， 下面四个长为5 的圈覆盖了t q 3 的所有边 ， ， 下面三个长为6 的圈覆盖了t q 3 的所有边： 下面三个长为7 的圈覆盖了t q 3 的所有边： ， 中国科学技术大学硕士学位论文 1 6 下面两个长为8 的圈覆盖了t q 3 的所有边： ， 故定理对7 l = 3 成立 假定定理对所有奇数七成立，3s 惫 乱令e 为t q 中的任意一条边，为整 数且满足4 2 “，n 为大于等于3 的奇数考虑下列两种情形： 情形j je 是丁0 。中的临界边 如果= 5 或f = 7 ，由引理2 2 2 ，t q 。中存在含e 的长为z 的圈因为e 是临 界边，记e = ( u o ，u 1 ) ，其中 u o = 一1 0 b ，u 1 = 磊一l i b ，若r 一3 ( u o ) = 0 ， 俨= 。一1 0 b ，u 1 = x n - i i b ，若r 一3 ( 矿) = i ， 其中b 是n 一2 位的2 元序列， 令 v o = 磊一l o b ，v 1 = 一1 i b ，若r 一3 ( v o ) = 0 ， v o = 孟n 一1 0 b ，v 1 = 一l i b ，若r 3 ( 伊) = i ， 则 是t q 。中存在含e 的长为4 的圈， 假设z = 6 或8 2 n 此时，记f = n + 如，其中段“= i ，2 ) 满足以下条件 中的一个： 1 1 = 2 ，如= 4 ，或 l = 2 ，2 = 6 ，或 l = 2 ，如= 7 ，或 l l24 ，f 1 5 ，如6 中国科学技术大学硕士学位论文 1 7 由归纳假设和引理2 2 1 ，如果。4 ，则g 0 中存在一条含( u o ，v o ) 的长为z - 的 圈c o g l 中存在一条含( u 1 ，v 1 ) 的长为岛的圈a 令 岛= 慨翟鬣薹 只= a 一( u 1 ，y 1 ) 则马+ ( 俨，伊) + p l + ( u 1 ，v 1 ) 是? q 。中存在含e 的长为的圈 情形2 ：e e ( g o ) 或e e ( g 1 ) ，不妨设e e ( g o ) 当4sz 2 1 时，由引理2 2 1 和引理2 2 2 可知，t q 。中存在一条含e 的长 为z 的圈对礼25 ，当2 - 1 + 1 z 2 “时，记= 岛+ 如，其中n2 护以+ 221 0 ， 且如6 ，对他5 成立由归纳假设和引理2 2 1 可知，g o 中存在一条含e 的长 为l 的圈c b 因为122 n 一2 + 2 ，在c o 中取一条与e 不同的交叉边为( u o ，俨) 令( 扩，v o ) = ( 0 0 b ，1 0 曰) ，其中b 是n 一2 位的2 元序列 则( u 1 ，v 1 ) 是g l 中的边，其中： u 1 = l i b ，v 1 = 0 1 b ，若r 一3 ( v o ) = 0 ， u 1 = 0 1 b ，v 1 = l l b ，若r 一3 ( 俨) = 1 ， 其中b 是 一2 位的2 元序列 由引理2 2 1 ，在g l 中存在含( u 1 ，v 1 ) 的长为2 的圈a ， 令p o = c o 一( 俨，俨) 且冗= g - ( u 1 ，v 1 ) 则p o + ( v o ，v 1 ) + p l + ( c ，1 ，( ，o ) 是 购。中含e 的长为的圈 定理得证 1 3 第三章纽立方体的h a m i l t o n 连通性 3 1 引言 纽立方体网络t q 是由h i l b e r s 等人f 1 7 1 提出来的一种超立方体网络q 。的 变型，其直径约是超立方体的一半在文献【1 ，1 0 ，9 ，1 7 ，2 1 】中研究了纽立方体网 络的性质 包含图中所有顶点的路称为h a m i l t o n 路( h a m i l t o n i a np a t h ) 如果图g 中的 任意两个顶点之问存在一条h a m i l t o n 路，则称g 是h a m i l t o n 连通的( h a m i l t o n i a nc o n n e c t e d ) 在本章第三小节中我们讨论t q 。的h a m i l t o n 连通性 纽立方体是由h i l b e r s 等人f l7 1 首先提出来的，记为t q 。t q 。的顶点集是 所有长为礼的 o ，1 有序= 元数纽( 亦称为长为7 ；的2 元序列( b i n a r yn - t u p l e s ) ) ， 这里n 是奇数t q 。中的一个顶点可以表示为t = u ，l u 。一2 x l x 0 定义：只= 撕。饥一l o 0 u o ，0 s i s n 一1 ， o 是二元运算符：e x c l u s i r e - o r t q 。可以递归定义如下： t 0 1 是完全图鲍，由两个项点0 , 1 组成当扎是大于1 的奇数时，可以 将t q 。分成四个部分： r q n 0 , 一0 2 ，t o o , 一1 2 ，t q 罂2 ，t o i , 一1 2 t q 2 2 由u 。一1 = ，一2 = j 的顶点一l 一2 x 1 2 ：0 组成，并且每个t q 甚2 同构 中国科学技术大学硕士学位论文 1 9 于r q ，2 t q 甚2 之间的连边( t ， ) 定义为 “= t h l u n 一2 z l z o ， = 豇”1 一2 z l z o ，或f i n - 1 一2 z i x o ，如果r 一3 ( t ) = 0 口= u n - l u n 2 。l x o ，或面”1 一2 x l z o ，如果r 一3 ( “) = 1 首先来说明定理证明所需要得引理其中，t q ，2 j g 表示t q 。一2 和尬的 笛卡尔乘积 引理3 1 1 ( h u a n g 等人f 2 l 】) 由t o o , 一0 2 u 丁q 0 10 2 和t o 1 2 u t o 1 , 一1 2 导出的子图 同构于? 仉一2 凰， 3 2 纽立方体的h a m i l t o n 连通性 引理3 2 1 。当n23 时，若t q 。是h a m i l t o n 连通的，则t q 。鲍也是h a m i l t o n 连通的 证明令t 。矿和y 是r q 。k 2 中的任意两个顶点，其中c 厂和y 是n 位的2 元 序列要证明此引理，只需证明u 和y 之间存在一条长为2 ”+ 1 1 的路为方便起 见，记r 识和r 砚为t q 。k 2 中的赡。的两个部分下面考虑两种情形 情形j ? u v c t q o ) 且y v ( t q ：) 此时。i ) n ，假设t 。= o r v = 1 取一个不同于o 【厂和0 y 的顶点o x 由 本引理的假设可知，o u 和o x 之间存在一条长2 n 一1 的路昂，1 v 和1 x 之间存在 一条，长2 n 一1 的路p l ，则 岛+ ( 0 x ，1 x ) + p l 是t q 。x 鲍中c ，和矿之间长2 ”1 一l 的路 情形2 j t f i 以y ) v ( t 识) 或 y y ( 丁q ：) 中国科学技术大掌硕士学位论文2 0 此时，= 。假设u 。= 0 由本引理的假设可知，0 u 和0 v 之间存在一条 长2 “一1 的路蜀。取一条边e = ( 0 x ，0 y ) 使得 o x ，0 y o 矾o y 则( 1 义，1 y ) 为t 娥中的边由本引理的假设可知，1 x 和1 y 之间存在一条长2 ”1 的路只 令瑞= e o ( o x ，o y ) ，则 瑞+ ( o x ，1 x ) + p 1 + ( 1y ，o y ) 是t q 。中连接，和矿的一条长扩“一1 的路 引理得证 口 定理3 2 2 对任何奇数n ，纽立方体t q 。是h a m i l t o n 连通的 证明n = 1 时，定理显然成立 n = 3 时，因t q 3 是点可迁的，只需要证明t q 3 中u 和矿之间存在长为7 的 路，其中y 为任意一个与u = 0 0 0 不同的顶点构造路如下： 故n = 3 时，定理成立 ， ， 对n 23 用归纳法，假设对任何小于n 的奇数定理均成立令u 和y 是t q 。 中的任意一对项点，其中n 的大于3 的奇数，为证明定理，只需证明u 和y 之间存 在一条h a m i l t o n 路下面考虑两种清形 中国科学拄术大学硕士学位论文 2 1 情彤：y ( g o ) 且y v ( g 1 ) 因砣5 ，存在条临界边e = 伍，y ) ，使得 x ，nn 以v ，= 毋，其中x y ( g o ) 且y v ( a 1 ) 由归纳假设以及引理3 2 1 可知，在g o 中u 和x 之间 存在一条长2 ”1 1 的路岛，g 1 中y 和y 之间存在一条长矿一一1 的路p 1 则岛+ ( x ，y ) + p 1 是r q 。中u 和y 之问的一条长为2 “一1 的路 婧影2 ： 弘矿 y ( g 。) 且 以y ) y ( g 1 ) ，苇妨设 以y ) y ( g o ) ， 由归纳假设和引理3 ，2 ，1 可知，g o 中盯和y 之间存在长为2 n 一1 的路r ， 取条交叉边为e = ( o o b ，1 0 b ) ，使得 y ) o o b ，o l b ) ，令 x 1 = 1 1 b ，y 1 = 0 1 b ，若r 一3 ( 0 0 b ) = 0 ， x 1 = 0 i b ，y 1 = i l 曰，着冀一3 ( o o b ) = 1 ， 其中b 为 2 2 位2 元序列则由归纳假设和引理3 2 1 可知x 和y 之间存在一 条长为2 ”1 1 的路b 令昂= 岛一e ，则 只4 - ( 0 0 b ，x ) + p 1 + ( 1 , 1 0 b ) 是r q 。中c 厂和y 之间的长2 “一1 的路 定理得证 口 第四章结束语 4 1 本文的主要结果 图的嵌入问题不但是图论的重要研究专题，也是网络设计和分析中重要的研 究内容互连网络的许多问题可以归结为图的可嵌入性问题因为圈结构和路结构 具有结构简单，易于扩充等优良性质，我们主要研究网络中的圈和路的嵌入问题 纽立方体网络7 。是超立方体网络的q 。的一个变型，它更多的保留了超立 方体网络的许多优良特性 我们研究纽