（应用数学专业论文）容错网络的路和圈嵌入研究.pdf

容错网络的路和圈嵌入研究 杜正中 中国科学技术大学数学系 中国合肥2 3 0 0 2 6 导师：徐俊明教授 专业：应用数学 时间：2 0 0 6 年4 月 雠兰 摘要 互连网络通常表示为一个图g = ( ke ) ，图g 的顶点集v ( c ) 代表处理器，图g 的边集e ( g ) 代表处理器之间通信线路，在文献中提及的许多互连网络拓扑结构中 都含有成百上千个处理器最简单，最基本的互连网络拓扑结构是线性阵列和环， 前人在此结构上设计了简单低消耗的并行算法和分布式算法超立方体网络q 。是 一种非常通用的互连网络拓扑结构要在超立方体网络中应用线性阵列和环上的 已有算法，就需要研究对应的路和圈在超立方体中的嵌入互连网络的可靠性是 评估网络性能的重要概念本文研究的容错网的路和圈嵌入是指，对于给定的互 连网络，最多能容忍多少个结点和连线同时发生故障，而剩余的子网络中仍然能嵌 入适当长度的路和圈 本文主要研究超立方体网络及折叠立方体网络在容错意义下的路和圈嵌入问 题全文共分五章，其中第三章和第四章是本文的主要部分 第一章引言，主要说明研究工作的背景，理论意义和实用价值等 第二章介绍图和网络的基本概念，容错性的定义，图的可嵌入性的定义超立 方体网络和折叠立方体网络的定义，基本性质以及关于容错图嵌入问题目前已 经取得的些结果 第三章研究容错超立方体网络矾的路和圈嵌入得到如下四个结果： 1 超立方体网络q 。m 4 ) 的故障边集为r ，i 疋1 n l ，并且满足所有故障 边不邻接于q 。中同一点，则q 。一r 中每条边都在长度从6 到2 ”的偶圈上 2 超立方体网络q 。2 ) 的故障边集为f e ，| 足1 n 一2 对于q 。一e 中 任意两点 和 ，存在长为的不含故障边的一路，其中d 口。( u ，v ) + 2sf 2 “一1 且2 1 9 d q 。( u ， ) ) 如果奶。( u ， ) 2n 一1 ，则还存在长为d o 。( u ， ) 的不含故障边 的w 路 3 超立方体网络q 。( n 5 ) 中故障点集为r ，1 日l _ 2 n 一3 则钆一r 中含有 中国科学技术大学博士学位论文 长度至少为2 n 一2 f r l 的偶圈 4 超立方体网络仉( n 3 ) 中故障点集为r ，l r is2 n 一4 ；故障边集为足， j 足i 2 n 一5 ，并且满足条件q 。一日一足中每个点至少与两个非故障边关联，那 么q k r 一足中含有长度至少为2 n 一2 f r i 的偶圈 第四章研究容错折叠立方体网络f q 。的路和圈嵌入得到如下三个结果： 1 折叠立方体网络f q 。( 3 ) 如果n 是奇数，则f q 。是一1 ) 边容错边偶 泛圈的如果n 是偶数，f q 。的故障边集为e ，i f e l n 一1 ，则f q 。一f e 中任意一条 边e 位于长为l 的偶圈上以及长为的奇圈上其中4 f s 铲，n 十l s 矿一1 2 折叠立方体网络f v 。( n 3 ) 中，故障边集为r ，i r i 2 n 一3 且f q 。一足 中的每个顶点至少与两条非故障边关联，则f q 。一r 有h a m i l t o n 圈 3 折叠立方体网络。( n 3 ) 中，故障边集为f c 当n 为偶数且i 足i 曼n 一2 ， f q 。一最中任意两个点之间有h a m i l t o n 路当n 为奇数且i 足lsn l ，f q 。一f e 中 任意两个异色点之间有h a m i l t o n 路；任意两个同色点之间有长为妒一2 路 第五章中对本文的主要工作进行了总结，并且提出了几个有待进一步研究的 问题 a b s t r a c t i n t e r c o n n e c t i o nn e t w o r k sa r eu s u a l l yr e p r e s e n t e db yag r a p hg = ( k e ) ， w h e r et h es e to fv e r t i c e sv ( a ) r e p r e s e n t sp r o c e s s o r s ，a n dt h es e to fe d g e se ( g ) r e p r e s e n t sl i n k sb e t w e e np r o c e s s o r s m a n yi 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 sh a v e b e e np r o p o s e di nt h el i t e r a t u r ef o rt h ep u r p o s eo fc o n n e c t i n gh u n d r e d so rt h o u - s a n d so fp r o c e s s i n ge l e m e n t s a m o n gt h e s et o p o l o g i e st h eh y p e r c u b e s ，d e n o t e db y q n ，i so n eo ft h em o s tp o p u l a rt o p o l o g i e s o nt h eo t h e rh a n d ，l i n e a ra r r a y sa n d r i n g s ，w h i c ha r et w oo ft h em o s tf u n d a m e n t a ln e t w o r k sf o rp a r a l l e la n dd i s t r i b u t e d c o m p u t a t i o n ，a r es u i t a b l ef o rd e v e l o p i n gs i m p l ea l g o r i t h m sw i t hl o wc o m m u n i - c a t i o nc o s t s t h ei m p l e m e n t a t i o no ft h e s ea l g o r i t h m si nt h eh y p e r c u b e si sa l l e m b e d d i n go fp a t h sa n dc y c l e si n t ot h eh y p e r c u b e s r e l i a b i l i t yi st h em o s tu s e - f u lm e a s u r eo fan e t w o r k sp e r f o r m a n c e i ti su s e f u lt oc o n s i d e rf a u l t yn e t w o r k s b e c a u s en o d ef a u l t so rl i n kf a u l t sm a yo c c u ri nn e t w o r k s i nt h i sd i s s e r t a t i o n ，w e d i s c u s st h ee m b e d d i n go fp a t h so rc y c l e si n t ot h ef a u l t yh y p e r c u b e so rt h ef a u l t y f o l d e dh y p e r c u b e s i tc o n s i s t so ff i v ec h a p t e r s ，w h e r ec h a p t e rt h r e ea n dc h a p t c r f o u ra r em a i np a r t s i nt h ef i r s tc h a p t e r ，w ei n t r o d u c et h eb a c k g r o u n do fo u rw o r k s i nt h es e c o n dc 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 r m i n o l o g ya n dn o - t a t i o nu s e di no u rd i s c u s s i o n w ea l s oi n t r o d u c et h ec o n c e p t so ff a u l tt o l e r a n c e a n dg r a p he m b e d d i n g a n dt h ed e f i n i t i o n so fh y p e r c u b e sa n df o l d e dh y p e r c u b e s t h e nw el i s ts o m ek n o w nr e s u l t so nt h e m i nt h et h i r dc h a p t e r ，w es t u d yt h ee m b e d d i n go fp a t h so rc y c l e si n t of a u l t y h y p e r c u b e s w eg e tf o u rm a i nr e s u l t sa sf o l l o w s 1 f o ra n ys e t 足o f f a u l t ye d g e so f q 。( n 4 ) w i t hj r l n 一1 ，e v e r ye d g e o fq n 一疋l i e so nac y c l eo fe v e r ye v e nl e n g t hf r o m6t o2 ”i n c l u s i v ep r o v i d e da l l e d g e si nf ea r en o ti n c i d e n tw i t ht h es a m ev e r t e x 2 f o ra n ys e tf co ff a u l t ye d g e so fq 。( 他2 ) w i t hi f e i n 一2a n d e v e r yp a i r ( “，u ) o fn o d e si nq n f e ，t h e r ee x i s t sau v p a t ho fl e n g t h w i t h d o 。( u ， ) + 2 2 ”一1 ，2 1 ( e d o 。( u ，u ) ) i fd 口。u ，u ) 竹一1 ，t h e r ee x i s t sa u y p a t ho fl e n g t hd o 。( u ，u ) 3 f o ra n yf a u l t yn o d es e tro fq 。( n25 ) w i t hi r i = 2 n 一3 ，q 。一r v i 中国科学技术大学博士学位论文 c o n t a i n sac y c l eo fe v e nl e n g t ha tl e a s t2 ”一2 1 蜀1 4 f o ra n ys e tro ff a u l t yn o d e sa n ds e t 兄o ff a u l t ye d g e so fq n 3 ) w i t hi r l = 2 n 一4 ，i 足 s2 n 一5 ，q 一r 只c o n t a i n sac y c l eo fe v e nl e n g t ha t l e a s t 垆一2 l r ip r o v i d e de v e r yn o d eo f 魏一蜀一疋i n c i d e n t sw i t ha tl e a s tt w o n o n - f a u l t ye d g e s i nt h ef o r t hc h a p t e r ，w es t u d yt h ee m b e d d i n go fp a t h so rc y c l e si n t of a u l t y f o l d e dh y p e r c u b e s w eg e tt h r e er e s u l t sa sf o l l o w s 1 ， f o r 礼3 ，i f 礼i so d d ，t h e nf q ni s ( n 一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 fn 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 n - f a u l t ye d g eo ff q n l i e so naf 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 + 1t o2 “一1 2 ，f o ra n ys e tr o f f a u l t ye d g e so f f q 。( n23 ) w i t hi 疋is 2 n 一3a n de v e r y n o d eo ff q n ei n c i d e n t sw i t ha tl e a s tt w on o n - f a u l t ye d g e s ，f q n ec o n t a i n s ah a m i l t o n i a nc y c l e 3 f o r a n ys e t 最o d f a u l t y e d g e s o f f q n ( 诧23 ) ，i f 礼i se v e n a n d f c ls 订一2 ， t h e na n yt w on o d e so ff q n ea r ej o i n e db yaf a u l t - f r e eh a m i l t o n i a np a t h ；i fn i s o d da n di 足i n 一1 ，t h e na n yt w od i f f e r e n tc o l o r e dn o d e so ff q n f ca r ej o i n e d b yaf a u l t - f r e eh a m i l t o n i a np a t ha n da n yt w os a m ec o l o r e dn o d e so ff q n r a r e j o i n e db ya f a u l t - f r e ep a t ho fl e n g t h 护一2 c o n c l u s i o n 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 第一章引言 现今高性能计算技术在国内外受到高度的重视，它在科学研究，工程技术以及 军事等方面的应用，己取得了巨大的成就国际上科学家普遍认为，没有万亿次以 上的高性能计算，2 1 世纪人类所面临的基因工程，全球气候准确预报，海洋环流循 环等“巨大挑战”问题( g r a n dc h a l l e n g e ) 是无法解决的现代高性能计算凹q 是 指能在互连网络上进行并行数据处理和数值模拟的大规模运算这里所说的互连 网络( i n t e r c o n n e c t i o nn e t w o r k 并不是通常意义下的i n t e r n e t 或者i n t r a n e t 而是泛指 一些运算节点通过通讯信道( 包括有线的和无线的) 按照一定的方式相互连接而 构成的系统这些运算节点可以是计算机子网络，计算机，计算机内部的处理器，存 储器，通信设备，其他元件或设备等，这种互连网络与传统的大型计算机相比具有 更高的性能价格比，在近年来已经引起了很大的研究关注很多这方面的系统已 经被实现 随着技术的不断提高，可以制造更高运算峰值的超级计算机，但是现有的超级 计算机的实际使用效率并不令人满意，这个问题要靠优化高性能计算机的系统结 构，软件和大规模并行算法和它们之间的密切匹配来解决 互连网络节点之间具有较多的消息传递，它们之间的连接方式是决定网络性 能和价格比的一个主要因素，因此研究网络组件之间的连接方式显得尤为重要网 络中节点之间的连接方式称为该网络的拓扑结构( t o p o l o g i c a ls t r u c t u r e s ) 网络的拓 扑结构是设计计算机互连网络的第一步，也是实现各种协议的基础，它对网络的性 能系统可靠性和费用都有重大影响 在分析网络拓扑结构时，人们通常把网络中运算节点抽象成一个点，把通信信 道抽象成两点之间的连线，那么该网络的拓扑结构就被抽象成一个图研究网络的 拓扑结构问题就归结为研究图的结构问题换句话说，图是网络结构的数学模型， 图论就成为设计和分析互连网络的重要工具 模块型，扩展性，软件和算法可移植性是大规模超级计算机技术发展方向用 2 中国科学技术大学博士学位论文 户可以根据自己的条件和需要任意购买模块，并用方便方法扩展成更多模块组成 的更高性能超级计算机现代大规模超级计算机上大型应用软件的编制往往要花 费很多工夫，在被扩展成超级计算机后，软件应能很容易的移植，大多数实际应用 问题有它们固有的应用软件或算法的通信模式这就要求被扩充或新建的计算机 系统应包含某种供某些软件或算法运行的拓扑结构，这是现代大规模超级计算机 设计或网络扩充时所必须考虑的重要问题。这个问题可以归结为图的可嵌入性问 题 h a y e s ( 1 9 7 6 ) 提出算法图的概念设 是一个算法，由算法a 可以定义一个无 向图c ( a ) 其中顶点表示执行算法a 所要求的设备，边表示这些设备之间所要求 的连线图c ( a ) 称为算法a 的算法图，亦称为算法a 的通信模式( c o m m u n i c a t i o n p a t t e r n ) 设图t 是一个计算机系统s 的拓扑结构，如果算法a 能在系统s 上执行， 那么c ( a ) 同构于t 的一个子图 另外，当在一个超级计算机上进行大规模计算时总是把要执行的程序分成若 干子程序，这些子程序同时在若干个不同的子系统上运行在一个给定的网络中， 分配子程序到若干子系统中的问题也能归结为图的可嵌入性问题 网络的可扩性问题也能归结为图的可嵌入性问题一个小网络要扩充为一个 大网络，并保留小网络的结构性质用图论的术语来说，一个给定的n 阶图g 可扩 充为m ( n ) 阶新图，如果存在m 阶图日使得g 是日的子图从最小费用的观点来 看，新图日的边数应尽可能少，这个最少数称为g 到日的可扩充数 线性阵列( l i n e a ra r r a y s 和环( r i n g s 是并行和分布式计算的基础网络结构， 也是最简单的网络结构，适合设计出简单，低通信消耗的算法目前，用于解决代 数，图论问题的许多有效的并行和分布式算法都在线性阵列和环上实现( 参见文献 【2 ，2 8 】) 另外，线性阵列和环还可以应用于任意互连网络上分布式计算的控s u 数 据流( c o n t r o l d a t af l o w ) 结构中在a s e h e u e r 的博士论文( 参见文献【1 1 ) 中有一个 实际应用的例子，关于弹性制造系统( f m s ：f l e x i b l em a n u f a c t u r i n gs y s t e m ) 的实时 优化( o n - l i n eo p t i m i z a t i o n ) 问题所以考虑线性阵列和环在网络中的嵌入成为近年 3 来许多人关注的问题( 参见文献( 1 1 ，1 3 ，1 4 ，1 9 ，4 3 】) 互连网络的可靠性是评估网络性能的重要概念，高可靠性的互连网络一直是 网络设计者追求的重要目标之一然而，可靠性是一个非常抽象的概念我们只从 网络的拓扑结构上考虑硬件故障对网络可靠性的影响，即在网络结点和( 或) 连线 可能发生故障的情况下的数据传输可靠性在这种意义下，对于一个给定的互连网 络，最多能容忍多少个结点和( 或) 连线同时发生故障，而剩余的子网络中每个结点 之间还仍能继续保持通信为区别其他含义可靠性，文献上习惯称这种可靠性为容 错性伽u “t o l e r a n c e ) 网络容错性的实质是当故障发生时，剩余网络的重组能力 网络容错性有多个方面的含义，不同的含义有不同的度量从网络拓扑结构的观 点这些度量可分为随机性度量( p r o b a b i l i s t i cm e i m ) 和确定性度量( d e t e r m i n i s t i c m g a s u m ，两种可靠性的概率性度量是最符合客观实际的，然而已经证明，各种具 有实际意义的概率性度量在其计算复杂性上都是n p h a r d 的( 参见b a l l ( 1 9 8 0 ) 【5 】) ，因而各种各样的多项式近似算法是重要的我们所研究的确定性度量是指网络 中至少需要多少数目的结点和( 或) 边同时发生故障才导致网络瘫痪；这个数目越 大，网络的容错性越大 迄今为止，国际上已经提出了许多种互连网络，其中超立方体网络的总体性 质是较好的，如它具有对数级的直径和最高连通度( 从而也具有最高容错度) 以及 正则性等等，特别是l i v i n g s t o n 和s t o u t 【3 1 】证明了每个图都可以嵌入超立方体网 络因而也研制出了多种超立方体型并行机，如c o s m i cc u b e 3 8 】，i n t e li p s c 【3 6 】， a m t e k ss y s t e m 1 4 【1 0 ，n c u b e 1 0 2 5 】，c a l t e c h j p lm a r ki i i ( 3 5 】和c o n n e c t i o n m a c h i n ef 1 7 1 而这些并行机的研制和使用又引起了人们对超立方体网络深入研究 的兴趣但是，超立方体网络并非各方面性质都是最好的，于是超立方体网络的变 型：折叠立方体网络，交叉立方体网络等被提出来研究，它们的直径都大约是超立 方体网络的一半 本文主要研究超立方体网络和折叠立方体网络的容错性质第二章介绍图和 网络的基本概念，容错性的定义，图的可嵌入性的定义超立方体网络和折叠立方 4 中国科学技术大学博士学位论文 体网络的定义基本性质以及关于容错超立方体网络和折叠立方体网络路和圈 嵌入问题目前已经取得的一些结果第三章是容错超立方体网络的路和圈的嵌入 问题第四章是容错折叠立方体网络的路和圈的嵌入问题第五章总结了前两章的 结果并且提出今后继续研究的问题 第二章预备知识 2 1 图论术语的介绍 本节简单介绍图的基本概念和在以后的讨论中要用到的记号文中没有定义 的有关图的术语和记号可参见【4 7 ，4 8 1 所谓图( g r a p h ) ：是指有序三元组e ，妒) ，其中v 非空称为顶点集( v e r t e x s e t ) ， e 称为边集( e d g e s e t ) ，而妒是e 到y 中元素有序对或无序对簇v v 的函数，称为 关联函数( i n c i d e n tf u n c t i o 叫v 中元素称为顶点( v e r t e x ) ，e 中元素称为边( e d g e ) ， 讪刻划了边与顶点之间的关联关系若v v 中元素全是有序对，则( e e ，妒) 称为 有向图( d i r e c t e dg r a p h ) 若v v 中元素全是无序对，则( ke ，妒) 称为无向图( u n d i r e c t e dg r a p 叫 我们把e 中的元素e 直接表示成v x v 中的元素( z ，) ，记e = ( z ，y ) = x y 此时， 边与顶点之间的关联关系已明确，则可简记( v e ，妒) = ( u e ) 两顶点。与称为 边x y 的两个端点( e n d v e r t i c e s ) 边与它的两端点称为关联的o n c i d e n t ) ，与同一条 边关联的两端点或者与同一个顶点关联的两条边称为相邻的( a d j a e e n o 两端点相 同的边称为环( 1 0 0 p ) 具有相同的两个端点的两条边称为平行边( p a r a l l e le d g e s ) 或 重边( m u l t i e d g e s ) 无环并且无平行边的图称为简单图( s i m p l eg r a p h ) 设( ue ) 是 图，v 中元素的个数u 和e 中元素的个数e ，即”= i v l 和e = i e l ，分别称为该图的 顶点数或阶( o r d e r ) 和边数一证e 和都是有限的图称为有限图( f i n i t eg r a p h ) 如 不加特殊说明，本文以下所涉及的图均为有限简单无向图 顶点z y ( a ) 的邻点集记为g ( z ) 顶点z 的顶点度( v e r t e zd e g r e e ) 定义为g 中 与z 关联的边的数目，记为d g ( z ) 对简单图有d a ( x ) = i b ( z ) | - 如果对g 的每个顶 点z 均有如( z ) = k ，我们称g 是k 正则的( k - r e g u l a r ) 任何不同两顶点之间都有边相连的简单无向图称为完全图( c o m p l e t eg r a p h ) ， n 阶完全图记为。若无环图的顶点集可以划分为两个非空子集x 和y ，使得x 中 任何两顶点之间无边相连并且y 中任何两顶点之间也无边相连，则称该图为2 部 5 6中国科学技术大学博士学位论文 分图( b i p a r t i t eg r a p h ) ， x ，y 称为2 部划分( b i p a r u t w n ) 二部划分为 x ，y ) 的2 部分图可记为( x uy e ) 任两点若同属于x 或y 则称为同色点，否则称为异色点 若x 中每个顶点和y 中每个顶点之阃均有边相连，则称该2 部分图为完全2 部分 图( c o m p l e t eb i p a r t i t e9 唧m ，记为所m ，其中l x i = t t t 和i y l _ t i 设z 和g 是图g 中两顶点，连接z 和y 长度为k 的路细删，记为x y 路，是指顶 点吼和边e j 交错出现的序列p = x i o ( = x ) e i 。嗣1 8 b e i k 戤( = 口) ，其中与边e i ，相 邻的两顶点。* 。和z t ，恰好是e t ，的两个端点，且除点z 和外，其余的顶点互不相 同，有时我们简记r = “1 1 t 。“一t f 。和称为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 ) 本文中我们将长度为的路简记为r ，长度为k 的圈简记 为仇当k 为偶数时，称仉为偶圈；当为奇数时，称瓯为奇圈包含图中所有顶 点的路称为h a m i l t o n 路( h a m i l t o n i a n p a t h ) 包含图中所有顶点的圈称为h a m i l t o n 困 ( h a m i l t o n i a nc y c l e ) 图g 中最短圈的长度称为g 的围长伽r 制，记为目( g ) 图g 中 两顶点。和之间的最短路的长度称为两点间的距离( d i s t a n c e ) ，记为d o ( x ，9 ) ，当 图g 明确时，简记为a ( x ，口) 图g 中任意两顶点z 和口之间的距离的最大值，称为 图g 的直径伸a m e t e r ) ，记为_ d ( g ) 设g = ( 矿( g ) ，e ( g ) ，毋g ) 和h = ( 明，e ( 日) ，妇) 是两个图若v ( h ) 矿( g ) ， e ( h ) e ( g ) ，并且妇是抛在e ( h ) 上的限制，则称h 是g 的子图f b g m v h ) ，记 为日g 称g 是日的母图d 印e 聊驯若日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 rs u b g r a p h ) ，记为hc g 设是v ( c ) 的非空真子集，以y 为顶点集，并以g 中两端点均在y ，中的边 为边集所得到的子图称为g 的由导出的子图，简称导出子图( i n d u c e ds u b g r a p h ) ， 记为c v ，1 导出子图e l y v 】记为g v 若= 。) ，则简记g 一扣) 为g z 设是e ( g ) 的非空子集，以为边集，并以g 中由中的边的端点为顶点 2 1 图论术语的介绍 7 集，所得到的子图称为g 的由e 导出的子图，记为g e ，】由e e 导出的子图记 为g e 若e = t e ，则简记g 一 e ) 为g e ， 设g l g ，g 2 g ，若v ( g 1 ) n v ( g 2 ) = 0 ，则称g 1 和g 2 是点不交的 v e r 泐一 d i s j o i n t ) ；若e ( g 1 ) ne ( g 2 ) = 0 ，则称g 1 和g 2 是边不交的( e d g e - d i s j o i n t ) g 1 和g 2 的并阻n t d 叫( 记为g l u g 2 ) 是指图h ，其中v ( h ) = v ( g i ) u v ( g 2 ) ， e ( h ) = e ( g 1 ) u e ( g 2 ) ，设e 7 中各边端点集为v ( e ) 并且有y ( ) v ( g o ，则 g 1 + e 是子图h ，其中v ( h ) = v ( g 1 ) 且e ( h ) = e ( g i ) u e r 若= e ，则简 记g 1 + e 为g 1 + e 对于两个图g 和如果存在个双射 p ：v ( g ) 一y ( h ) ，使得( z ，y ) e ( g ) 褂徊扛) ，p ( ) ) e ( 日) 那么称图g 和胃是同构的佃o m o r p h i c ) ，记为g 掣日，并称口为图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 mm 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 ) ，如果对于任意的两点z ，y y ( g ) ，存在 图g 的自同构口，使o ( x ) = y 图g 称为边可迁的( e d g e + t r a n s z 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 的一 个匹配( m a t c h i n g ) 如果图g 的匹配m 的端点集等于y ( g ) ，则m 称为图g 的完备 匹配扫e r ，比一m a t h i n g ) 可迁图是一类重要的图，它具有高度的对称性，是比较理想的高性能超大规模 计算机系统互连网络的拓扑结构这里我们介绍构造一类重要可迁图一c a y l c y 图 的方法因为构造涉及到群论的概念，因而被称为代数方法 设r 是一非平凡有限群，s 是r 的不包含单位元e 的非空子集定义一个有向 8 中国科学技术大学博士学位论文 图g 如下： v ( g ) = r ；( z ，y ) e ( g ) 铮z - l y s ，对于任意z ，r 如上定义的有向图，是由英国数学家c a y l e y 6 】首先提出，所以一般教科书和文献 都称它为群r 关于子集s 的c a y l e y 图，记为c r ( s ) 或c a ( f ，s ) 当s 4 = s 时，群r 关于子集s 的c a y l e y 图c r ( s ) 是对称有向图，它可以看成 是无向图 c a y l e y 图有许多好的性质，一个最明显的性质就是c a y l e y 图是点可迁的 2 2 图的嵌入和它的网络意义 图的嵌入问题不但是图论的重要研究专题，也是网络设计和分析中重要的研 究内容互连网络的许多问题可以归结为图的嵌入问题 按照h a y e s 【1 6 的说法，算法也可以用圈g 来表示g 的顶点表示执行该算法 所要求的设备，g 的边表示这些设备之间的连线这样的图g 叫做该算法的通信模 式( c o m m u n i c a t i o np a t t e r n ) 因此，算法能在计算机系统g 中执行当且仅当该算法 的通信模式同构于g 的子图 在互连网络中，一个结构能是否能被另一个结构来模拟是重要的网络模拟 问题能归结为图的嵌入问题 正如前面所说，一个算法的通信模式可以用一个图来表示因此，算法在系统 中的实现就是该算法的通信模式在该系统网络中的嵌入许多多处理系统是为“一 般目的”而设计的，这意味着只要时间和空间允许，任何算法如果能给予合适的编 码总是可以在该系统中执行存在大量的算法，它们能有效的解决某些应用问题， 并且有最好的为该算法的执行而设计的通信模式对于这些算法，为达到希望的 性能，某些拓扑结构的存在性是一个重要因素因此，对于这些应用，被设计的网 络最好能在逻辑上提供一个特殊的拓扑结构以确保该算法有效地执行另一方面， 有些算法只要稍作修改就可以完全适用于另外的拓扑结构，即对算法稍加修改就 2 2 图的嵌入和它的网络意义 9 能运行如果原始算法结构能被嵌入到一个新网络中，已有的算法就很容易运行 嵌入是一个拓扑结构到另一个拓扑结构的映射，它保留某些被要求的性质文 献中讨论了各种类型的嵌入我们讨论的嵌入是指下列定义： 设g 和h 是两个给定的图图g 到日的嵌入( e m b e d d i n g 是一个从g 到h 的 映射咖：v ( c ) 一y ( ) ，使得边( z ，y ) e ( g ) 对应h 中的一条边( 妒( z ) ，妒( ) ) 或 者h 中一条) ，妒( f ，) ) 路称g 为客图国u e s ，h 为主图( h o s t ) 衡量嵌入优劣的两个常用度量是膨胀数( 度量传输延迟) 和负载( 度量处理器 的利用率1 嵌入曲的膨胀数( d z l a t i o n ) 定义为： d i l ( 妒) = m a x d l t ( 妒( x ) ，妒( g ) ) ：( z ，y ) e ( g ) ) 显然，存在嵌入妒：v ( c ) 一v ( h ) 使得d i t ( 妒) = 1 当且仅当g 是h 的子图 当d i t ( 妒1 1 时，主图h 模拟客图g 的有效率将降低 如果g 同构于日的某一个子图t ，则g 到t 的任何一个同构映射日可以扩充 为g 到h 的一个嵌入币这种嵌入称为同构嵌入( i s o m o r p h i ce m b e d d i n g ) 同构嵌 入是最理想的，因为它是点对点的，而且当客图被用来表示一个算法的通信模式 时，在主图运行该算法与客图上运行该算法有相同的速度在这种情况下，主图能 以同样的速度有效的模拟客图 负载t o a d j 是指当客图g 被嵌入主图h 后，g 用到h 的某一个顶点的最大次 数 毋容置疑，最好的嵌入应是这两个参数都很小因此最理想的嵌入是同构嵌 入，即客图同构于主图的某个子图，因为此时膨胀数和负载都是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 ) 的拓扑结构形阵列网络和环网是最通用的，最简单 的，且是最有用的互联网络之一本文主要研究路和圈在网络中的同构嵌入问题 中国科学技术大学博士学位论文 如果对任意整数满足e ( c ) s 口( g ) ，图g 含有长为的圈，其中g ( c ) 是 图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 6 】和边泛圈性如果图g 的每个顶点位 于长从g ( c ) 到v ( c ) 的圈上，则称g 是点泛圈的( v e r t e z - p a n c y c l i c ) 如果图g 的每条 边位于长从g ( c ) 到v ( c ) 的圈上，则称g 是边泛圈的( e d g e - p a n c y c l i c ) 显然，边泛圈 的图一定是点泛圈的 a ：h a x a i l t o n 性 b ：h a m i l t o n 连通性 e ：泛圈性 d ：点泛圈性 e ：边泛圈性 f ：泛连通性 图2 1 共h a m i l t o n 性的包含关系 如果图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 中的任意两个顶点$ 与可之间有长为l 的路， 其中满足如扛，) f t ，( 研一1 ，贝目称g 是泛连通的( p a n c o n n e c t e d ) 显然，泛连 通的图一定是h a m i l t o n 连通的 h a m i l t o n 性、h a m i l t o n 连通性、泛圈性、点泛圈性、边泛圈性、泛连通性统称 为类h a m i l t o n 性。它们之间的包含关系见图2 1 对i = i y i 的二部分图g = ( x uy i e ) ，s i m m o n s 【3 7 】提出了二部分h a m i l t o n 连通的概念图g = ( x uy l e ) 是二部分h a m i l t o n 连通的( h a m i l t o n i a nl a c e a b l e ) 是指g 中任何异色两点之间有h a m i l t o n 路h s i e h 等人 2 2 l 进一步提出了强二 2 3 图的容错度量 部分h a m i l t o n 连通的概念二部分h a m i l t o n 连通图g = uy ，e ) 是强二部分 h a m i l t o n 连通的( s t r o n g l yh a m i l t o n i a nl a c e a b l e ) 是指g 中任何同色两点之间有长 为l x u y i - 2 路 因为二部分图不含奇圈，故对二部分图提出了偶泛圈的概念如果对任意 偶数f 满足9 ( v ) s ( g ) ，图g 含有长为z 的偶圈，称图g 是偶泛圈的( e v e n p a n c y c l i c ，【3 4 】如果对任意满足d c ( x ，) s ( g ) 一1 ，2 1 ( e d g ( 。，) ) ，图g 中任 意两个顶点z 与y 之间有长为f 的路，称g 是偶泛连通的r e ”e n p a n c o n n e d t e d ) 【3 2 1 2 3 图的容错度量 互连网络的可靠性是评估网络性能的重要概念高可靠性的互连网络一直是 网络设计者追求的重要目标之一然而，可靠性是一个非常抽象的概念，我们只从 网络的拓扑结构上考虑硬件故障对网络可靠性的影响，即在网络结点和( 或) 连线 可能发生故障的情况下的数据传输可靠性在这种意义下，对于一个给定的互连网 络，最多能容忍多少个结点和( 或) 连线同时发生故障，而剩余的子网络中每个结点 之间还仍能继续保持通信为区别其他含义可靠性，文献上习惯称这种可靠性为容 错性f ，0 u l tt o