（基础数学专业论文）基于cayley图的互连网络的研究.pdf

摘要 众所周知，凯莱图在计算机局域网及大规模并行处理系统的设计与分析中起着 重要的作用超立方体网络( h y p e r c u b e ) ，双环网络( d o u b l el o o pn e t w o r k ) ，星图( s t a r g r a p h ) 等都是凯莱图全文共分为五章。围绕凯莱网络中以下两部分的重要课题进 行讨论1 双环网络的寻径策略与最优设计；2 交错群网络与洗牌交换置换网络 的路由算法下面是本文的一些主要结果t 1 本文给出了一个方法用于构造b 紧优无限族( k 1 ) ，并用此方法构造出了 4 族3 _ 紧优无限族，3 族新的4 紧优无限族。3 族5 - 紧优无限族及2 族6 紧优无 限族另外我们利用计算机搜索还找到了2 7 族新的o 紧优无限族，2 6 族新的1 一 紧优无限族，8 族新的2 - 紧优无限族，2 族3 - 紧优无限族 2 本文给出了一个方法用于构造奇异1 一紧优无限族我们用此方法构造出3 族奇异1 一紧优无限族及1 族奇异2 紧优无限族 3 利用预先计算出来的l 形瓦的四个参数及同余方程s z + s 2 y ；1 ( r o o dn ) 的一个解，我们给出了有向双环网络g ( n ；s l ，8 2 ) 的时间复杂性为常数的最优路由算 法也就是经过常数时间的计算便可得到任意两点间的一条最短路径 4 对于一个给定的正整数n ，本文给出了一个算法用于求出一个k 一紧优的双环 网络g ( m1 ，s ) ，该算法的时间复杂性为o k 2 5 n o 2 5l o gn ) 5 利用预先计算出来的l 形瓦的四个参数及同余方程s l z + s 2 yil ( m o dn ) 的一个解，我们给出了无向双环网络g ( n ；+ s x ，q - s 2 ) 的时间复杂性为常数的最优路 由算法也就是经过常数时间的计算便可得到任意两点间的一条最短路径 6 我们给出了无向双环网络g ( n ；：k s l ，：k s 2 ) 的直径公式，此公式用l 形瓦的四 个参数表示 7 我们给出了交错群网络a 的个最优路由算法 8 我们给出了洗牌交换置换网络s e p n 的一个新的路由算法并给出了s e p 直 径下界的一个估计 关键词t 凯莱图；双环网络；交错群网络；洗牌交换置换阿络s e p ；直径；l - 形 瓦；k 紧优；路由；算法 a b s t r a c t ni sn o ww e l lk n o w nt h a tc a y l e yg r a p h sp l a yav e r yi m p o r t a n tr o l e i nt h ed e s i g n a n da n a l y s i so fi n t e r c o n n e c t i o nn e t w o r k sf o rp a r a l l e lp r o c e s s i n ga n do fl o c a la r e ac o m m u - n i c a t i o nn e t w o r k s t h eg r a p h ss u c ha sh y p e r c u b e s ，d o u b l el o o pn e t w o r k s ，s t a rg r a p h sa 弛 e x a m p l e so fc a y l e yg r a p h 8 t h ep a p e rc o n t a i n sf i v ec h a p t e r s i tc e n t r e so nt h ef o l l o w i n g t w oi m p o r t a n tp a r t so fc a y l e yn e t w o r k s ： 1 t h ed e s i g na n do p t i m a lr o u t i n ga 】g n s i t h mf o rd o u b l el o o pn e t w o r k s ； 2 t h er o u t i n ga l g o r i t h mf o ra l t e r n a t i n gg r o u pn e t w o r k sa n ds h u f f l e - e x c h a n g e p e r m u t a t i o nn e t w o r k s h e r ea r es o m eo fm a i nr e s u l t si nt h i sp a p e r ： 1 w eg i v eam e t h o dt oc o n s t r u c tk - t i g h to p t i m a li n f i n i t ef a m i l i e s b yu s i n gt h i s m e t h o d ，w eo b t a i nf o u r3 - t i g h to p t i m a li n f i n i t ef a m i l i e s ，t h r e e4 - t i g h to p t i m a li n f i n i t e f a m i l i e s ，t h r e e5 - t i g h to p t i m a li n f i n i t e 白m i l i ，a n dt w o6 - t i g h to p t i m a li n f i n i t ef a m i l i e s b yt h ea i do fc o m p u t e r ，w ea l s of i n d2 7n e w0 - t i g h to p t i m a li n f i n i t ef a m i l i e s ，2 6n e w1 t i g h to p t i m a li n f i n i t ef a m i l i e s ，8n e w2 - t i g h to p t i m a li n f i n i t ef a m i l i e s ，a n d23 - t i g h to p t i m a l i n f i n i t ef a m i l i e s 2 w eg i v eam e t h o dt oc o n s t r u c ts i n g i i l a r1 - t i g h to p t i m a li n f i n i t ef a m i l i e s b yu s i n g t h i sm e t h o d ，w eo b t a i nt h r e es i n g u l a r1 - t i g h to p t i m a li n f i n i t ef a m i l i e sa n do n es i n g u l a r 2 - t i g h to p t i m a li n f i n i t ef a m i l i e s 3 f o rag i v e nd i r e c t e dd o u b l el o o pn e t w o r kg ( n ；s l ，3 2 ) ，b yc o m p u t i n gf o u rp a r a m e - t e r so ft h el - s h a p et i l ea n das o l u t i o no f8 1 x + s 2 y ；1 ( r o o dn ) i na d v a n c e ，w eg i v ea n o p t i m a lr o u t i n ga l g o r i t h mf o rg ( s l 8 2 ) w h i c hr e q u i r e sc o n s t a n tp r o c e s s i n gt i m et of i n d as h o r t e s tp a t hb e t w e e na n yt w on o d e s 4 f o rag i v e np o s i t i v ei n t e g e rn ，w eg i v ea no ( k 2 - 5 n o 2 5l o gn ) a l g r i t h mt of i n da k - t i g h to p t i m a ld o u b l el o o pn e t w o r kg ( n ；1 ，3 ) 5 f o rag i y e nu n d i r e c t e dd o u b l el o o pn e t w o r kg ；4 - s l ，士8 2 ) ，b yc o m p u t i n gf o u r p a r a m e t e r so ft h el - s h a p et i l ea n das o l u t i o no f8 1 z + s 2 y 兰1( r o o d 礼) i na d v a n c e ，w e i i g i v ea l lo p t i m a lr o u t i n ga l g o r i t h mf o rg ( n ；：k s l ，士s 2 ) w h i c hr e q u i r 髑c o n s t a n tp r o c e s s i n g t i m et of i n das h o r t e s tp a t hb e t w e e na n yt w on o d e s 6 w eg i v ead i a m e t e rf o r m u l af o ra l lu n d i r e c t e dd o u b l el o o pn e t w o r kg ( n ；土5 l ，士s 2 ) ， w h i c hc 强b er e p r e s e n t e db yf o u rp a r a m e t e r so ft h el - s h a p et i l e 7 a no p t i m a lr o u t i n ga l g o r i t h mi sp r e s e n t e df o rt h en e wa l t e r n a t i n gg r o u pn e t w o r k r 。 8 an e wm u t i n ga l g o r i t h mi sp r o p o s e df o rt h es h u f f l e - e x c h a n g ep e r m u t a t i o nn e t w o r k s e p na n dal o w e rb o u n dd i a m e t e re s t i m a t i o ni sg i v e nf o rt h i sn e t w o r k k e yw o r d s ：c a y l e yg r a p h ；d o u b l el o o pn e t w o r k ；a l t e r n a t i n gg r o u pn e t w o r k ； s h u f f l e - e x c h a n g ep e r m u t a t i o nn e t w o r k ；d i a m e t e r , l - s h a p et i l e ；k - t i g h to p t i m a l ；r o u t i n g ； a l g o r i t h m i i i 序言 自从英国数学家凯莱( a c a y l e y ) z 3 在1 8 9 5 年首先提出用群来构造图以 后，对凯莱图的研究就持续不断，特别是s b a k e r s 与b k r i s h n a m u r t h y f6 9 】提出 把凯莱图作为对称互连网络模型之后，人们对凯莱图的研究更是有增无减，许 多新的互连网络模型被提出来研究，比如：星图( s t a rg r a p h ) ： 1 ，4 7 , 6 0 , 6 2 , 6 6 , 6 9 , 7 2 - 7 4 , 9 3 ， 交错群图( a l t e r n a t i n g g r o u p g r a p h ) 2 0 , 4 2 - 4 4 , 9 2 , 9 7 , t o s ，薄煎饼图( p a n c a k e g r a p h ) 。9 ，8 1 洗牌交换置换网络( s h u t , e - e x c h a n g ep e r m u t a t i o nn e t w o r k ) 7 5 , 1 0 3 】，墙式网托( 7 | w a l l t o r u s ) 4 , 8 】，超圆环面 s u p e r - t o r u s ) 3 1 , 14 刈，蜂窝网络i ：h o n e y c o m bn e t w o r k s ) 7 0 j 等一 些网络随着网络的结点数的增加，其每个结点的度也随着增加，比如t 超立方体 网络【1 6 t 4 7 ，6 2 ，64 | ，星图网络，交错群网络，薄煎饼图等然而有不少网络是固定度 的互连网络，比如l 双环网络 2 , 3 , 6 , 9 - 1 8 , 1 7 , 2 1 - ：3 0 ，3 2 ，3 8 4 1 ，4 5 ，4 8 5 7 ，5 9 ，6 8 ，7 1 ，8 2 8 6 ，9 6 ，1 0 9 1 1 2 三环( 或者多环) 网络i 2 8 4 5 9 8 ，蚓，洗牌交换网络( 4 j ，墙式网托，超圆环面，旋转 交换网络吲，蜂窝网络，d eb r u i j n 网络1 3 4 ，4 6 ，m ；e b i u s 图【7 9 】等因为顶 点的度对应于组件的可供使用的输入与输出端口( i o ) 的数目，每个组件的物 理连接受限于该组件的端口数目，小顶点度意味着小的物理连接，从而减少网 络的建造成本，所以固定度的互连网络倍受青睐 本文研究的重点是双环网络的寻径策略及最优设计双环网络是循环图 中的一种，它广泛应用于计算机局域网及大规模并行处理系统 自从1 9 7 4 年c k w o n g 与d c o p p e r s m i t h s 利用l 一形瓦证明了有向双 环网络g ( n ，1 ，s ) 的直径大于或等于娟_ 1 2 以后，有向双环网络与三一形瓦 便形影不离，利用工形瓦来构造 紧优无限族，利用l 形瓦来计算双环网 络的直径。利用l 形瓦来研究双环网络的路由等 c y i n g , f k h w a n g 【1 1 】给出了一个时间为o ( 1 0 9n ) 的算法用于计算有 向双环网络g ( 嗡钆s 2 ) 的直径，本文也给出了一个新的算法虽然我们算法的 时间复杂性与文献 1 1 一样为o o o gn ) ，但我们的算法易于分析，原因在于我 们利用平行四边形为工具来计算双环网络的直径 1 对于m i n d ( n ；1 ，s ) 2 s n ) ，这里d ( n ；1 ，。) 表示有向双环网络g ( n ；l ，s ) 的直径。f k h w a n g 与y h x u 证明了当n 6 3 4 8 时，其上界为t 瓶元+ 2 弧i + 5 1 9 9 6 年r f d s e t h 【6 1 】证明了当n 1 2 0 0 时，其上界为 、丽+ 瓶元+ 2 5 对于l 形瓦l ( n ；l ，h ，z ，y ) 的两个参数$ 与”差的绝对值k y l 的估计， p e s q u e ，f a g u i l o ，m a f i o l 证明了t 当厶形瓦l ( n ；l ，屯，”) 是o - 紧瓦 时，k y i 3 f a g u f l o ，m a f i o l 【2 目证明了t 当l 形瓦三( n _ f h ，z ，y ) 是k 一 紧瓦时，k y i 的上界为d ( 女) 我们证明了：对于k 一紧优的正整数n ，若厶 形瓦l ( n ；l ，h ，霉，y ) 是b 紧的，则忙一v i 2 k + 6 利用这个结论我们给出了一 个时间复杂性为o ( k 2 5 n o 衢l o gn ) 算法用于寻找k 紧优的双环网络g ( n ；1 ，s ) 我们的算法优于刘焕平，杨义先，胡铭曾【5 l 】在2 0 0 1 年给出了一个时间复杂 性为o ( n l o gn 1 的算法 f k h w a n g 与y h x u1 3 0 1 构造了紧优有向双环网络无限族，紧接着p e r d o s ，d f h s u ( 6 5 】，李乔，徐俊明，张忠良【5 4 】，p e s q u e ，f a g u f l o ，m a f i o l 等也构造了许多紧优与几乎紧优的双环网络无限族。文献阻】给出了6 9 族 紧优双环网络无限族与3 3 族几乎紧优双环网络无限族徐俊明p 2 】在1 9 9 9 年 给出了两族不含紧优与几乎紧优的无限族，随后构造出了9 族二紧优的双环 网络无限族【8 3 ，髓】，紧接着在2 0 0 3 年构造出了1 族4 - 紧优的双环网络无限族 从文献【8 3 ，8 6 ，8 5 l 可看出当k22 时，欲构造肛紧优的双环网络无限族 并非易事本文给出了一个方法用于构造b 紧优双环网络无限族( k 兰1 ) ，利 用此方法可以比较容易地构造出k 紧优无限族利用这个方法我们构造了4 族3 - 紧优无限族，3 族新的4 - 紧优无限族，3 族5 - 紧优无限族及2 族6 - 紧 优无限族另外利用计算机搜索我们还找到了2 7 族新的m 紧优无限族，2 6 族新的1 紧优无限族，8 族新的2 紧优无限族，2 族孓紧优无限族 徐俊明| 8 4 】，f a g u n o ，e s i m o ，m z a r a g o z a 2 2 1 给出了构造奇异0 - 紧优双 环网络无限族的方法，并给出了若干族奇异0 - 紧优双环网络无限族然而构 2 造奇异i 一紧优双环网络无限族比构造奇异o 紧优双环网络无限族要难得多， 本文给出了一种行之有效的方法用于构造奇异1 紧优无限族我们用此方法 构造出3 族奇异1 紧优无限族根据此方法我们也构造出了1 族奇异2 紧优 无限族 信息路由是通信网络的基本功能若每个信息总是沿着从信源到信宿的 最短路传送，则称为最优信息路由对于有向双环网络g ( m 8 1 ，8 2 ) 的路由及 容错路由算法的研究，有许多学者对此进行了研究，比如：李晓明，方滨兴 ( 1 9 9 0 ) 1 5 5 ，冯斐玲，金林钢( 1 9 9 4 ) 2 4 ，刘焕平，朱延功，杨义先( 1 9 9 9 ) 5 2 】，陈忠 学，靳蕃( 2 0 0 i ) 12 1 ，c * c h o u ，d j g u a n ，k - 1 w a n g ( 1 9 9 8 ，1 9 9 9 ) 1 1 4 】，陈协 彬( 2 0 0 3 ) 9 1 在文献【1 4 】中的最优路由算法动态地确定信息应传送的下一个结 点，其时问复杂性为o ( a 3 ，这里d 是信源到信宿的距离文献 5 2 】的最优路由 算法的时间复杂性为o ( d ) ，这里d 是g ( n ；l ，8 ) 的直径文献【1 2 】给出的算法 类似于文献f 5 2 】，不过要在每个结点预先存储所有非正常结点的编号及结点0 到这些结点的距离，以便提高寻径效率最近陈协彬【9 1 对于步长有限制的双 环网络给出了时间复杂性为常数的最优路由算法，此算法适用于许多双环网 络，但并不能对所有的双环网络都适用我们的一个工作是利用预先计算出来 的l 形瓦的四个参数及同余方程8 1 z + s 2 yi1 ( r o o dn ) 的一个解( 面，可) ，给出 了双环网络g ( n - 8 ，s 2 ) 的时间复杂性为常数的最优路由算法，也就是通过常 数时间的计算便可得到从源结点到任意其它结点的最短路径 y c h e n g ，f k h w a n g 8 9 】给出了g ( 川士s 1 ，+ s 2 ) 的一个最优路由算法， 利用预先计算好的1 2 个参数，常数处理时问就可动态地确定信息应传送的下 一个结点 k m u k h o p a d h y a y a ，b p s i n h a 4 8 1 给出了g ( n ；- t - 1 ，：k s ) 的最优路 由算法，其时间复杂性为o ( , - a 3 ，此算法给出了任意两点间的一条最短路径 n c h a l a m a i a h 与b r a r a a a u r t y 5 9 l 给出了g ( n ；4 - 1 ，士s ) 的一个时间复杂性为 o ( g + l o gs ) 的最优路由算法，这里9 = g c d ( n ，s ) 我们利用预先计算好的l 形瓦4 个参数及同余方程s l z 十s 硝il ( m o dn ) 的一个解( i ，可) ，常数处理时 3 间就可计算出任意两点问的一条最短路径我们的另一个主要工作是给出了 无向双环网络g ( n ；- - s t ，- - 8 2 ) 的直径公式，它可用l 形瓦4 个参数表示，此 结果未见报道过另外我们还给出了一类无向双环网络g ( n ；士1 ，士。) 的直径公 式，此公式可用n 与s 的表达式表示 人们对超立方体网络与星图网络进行了许多研究而交错群网络作为星 图网络可能的替代网络，也在1 9 9 3 年由j s j w o ，s l a k s h m i v a r a h a n 和s k d h a l l 4 2 l 首先提出来，他们定义了交错群网络a 瓯，相继地有一些学者【9 2 ，舯】对 交错群网络a g 。进行了研究 冀有虎【“】提出了一种新的交错群网络a ，此网络与且戗比较，每个 结点的度大约是旧网络的一半且直径与旧网络大致相同，因此新交错群网络 的优越性显见冀有虎阳】给出了此交错群网络的一个路由方案，然而此方案 不完善因为对于 7 中的两个结点( ；：；：i ；：) ，( ：；：；) ，此路由方 案并不能给出这两个结点间的一条路径本文给出了交错群网络a 。的一个 最优路由算法 s l a t i f l 等 7 5 1 在1 9 9 8 年提出了一种新的互连网络洗牌交换置换网络 s e p n ，它是基于对称群晶的c a y l e y 网络，是一种固定度( 度为3 ) 的互连网 络该图的点连通度为3 ，即它是极大容错的( m a x i m a l l yf a u l tt o l e r a n c e ) 在 v l s i 实现方面，就正则性与容错性而言，该图比d eb r r 【i j n 图或m s e b i u s 图【7 9 】 更加具有吸引力 s l a t i f i 和p k s r j m a i 【7 5 】提出了一种简单的路由算法， 得到了s e p 直径d 的估计，ds ( 9 n 2 2 2 n + 2 4 ) 8 我们给出了一种新的 s e r 路由算法，算法碍到的此网络直径的上界估计为( 2 一l o n ) 8 另外还 给出了此网络直径下界的一个估计，并证明了zd o 5 n 2 一n 4 第一章基本概念 1 1 网络的拓扑结构与图 计算机在人类社会的各个方面发挥着越来越大的作用，在计算机科学的 迅猛发展中，不断地提出了许多重要的问题尚待解决在并行处理领域。研究 并行机中处理器连接的方式( 互连网络) 与路由问题是一个很重要而且基本的 课题 我们这里所说的互连网络是有更广泛的含义，泛指组件( 计算机子网络， 计算机，计算机内部的处理器，存储器，通信设备，其它元件或设备) 集合与 通信信道( 有线或无线的) 集合按一定的点对点方式相互连接所形成的系统 组件之间的连接方式是决定网络性能和价格比的一个重要因素，因此研究网 络之间的连接方式显得尤为重要网络中组件和组件之间的连接方式称为网 络的拓扑结构网络的拓扑结构是设计计算机互连网络或制造超大规模并行 计算机系统的第一步，也是实现各种协议的基础，它对网络的性能、系统可靠 性和费用都有重大影响 在分析网络拓扑结构时，人们通常把网络中组件抽象成一个点，把通信信 道抽象成两点之间的连线，那么该网络的拓扑结构就被抽象成一个图研究网 络的拓扑结构问题就归结为研究图的结构问题，换言之，图是网络拓扑结构 的数学模型，我们可以通过图论的方法来研究网络的拓扑结构 通常衡量个互连网络好坏的标准是。对称性，可扩展性，低度，直径短， 简单方便的最优路由，递归结构，平行路的存在性等 凯莱( c a y l e y ) 网络作为一种正则、点对称的互连网络倍受人们的青睬， 它在计算机互连网络的设计与分析中起着重要的作用本文所研究的双环网 络，交错群网络，洗牌交换置换网络均是凯莱图 论文中总是把组件( n o d e s ) 与图的顶点( v e r t i c e s ) ，通信信道( c h a n n e l so r l i n k s ) 与图的边( e d g e s ) 或弧( a r c s ) 等同并且，网络的拓扑结构，网络，图这 三者指的是同一对象，不加以区分 1 2 基本定义与符号 为了给出图的严格定义，我们先引进下面的 5 定义1 2 1 ：设y 是集合，称y 的所有无序元偶的集合 y v = ( u ， ) l “，口y ) 为y 和y 的无序积( 所谓( ”) 是无序元偶，指的是( ”，“) = ( u ，”) ) 称y 的所有有序元偶的集合 v v = ( “， ) l “，口y ) 为y 和y 的笛卡儿积记v o = ( 仉 ) i y ) 定义1 2 2 ：称一对集合y 和e 为一个无向图g ，记作g = ( k e ) ，如果 y 是一个非空有限集的元素叫做图g 的顶点) ，而e 是y y 的一个子集 旧的元素叫做图g 的边) 如果e y y ，则称图g 为简单无向图 定义1 2 3 ：称一对集合y 和e 为一个有向图g ，记作g = ( k e ) ，如果 y 是一个非空有限集( y 的元素叫做图g 的顶点) ，而e 是v v 的一个子集 ( e 的元素叫做图g 的有向边或弧) 如果e v v ，则称图g 为简单有 向图 本文所讨论的图皆为简单无向图或简单有向图 设g 是一个有向( 或无向) 简单图我们将采用以下符号； z ，z + ，r 分别表示整数集，非负整数集，实数集 表示集合 1 ，2 ，3 ，n ) ，其中t i 是一个自然数 训表示不大于z 的最大整数，这里$ r m 表示不小于t 的最小整数，这里z r h 表示对z 四舍五入得到的整数。r 例如；【3 6 7 】= 4 ，【一3 4 6 = 一3 y ( g ) ：图g 的顶点集 e ( g ) ：图g 的边集( 或弧集) 一( g ) ：图g 的连通度 d g ( u ， ) ：图g 中从点u 到点的最短路径的长度 d ( g ) ：图g 的直径定义为：图g 中所有点对的距离的最大者，即 d ( g ) = m a x d c ( u ，”) iu ， y ( g ) 6 定义1 2 4 ：设g 为有限群( e 为g 的单位元) ，s 是g 的生成子集且满足 下列条件：e 芒s ，则群g 关于子集占的c a y l e y 有向图x = c a y ( g ，s ) 定义 为；v ( x ) = g ，e ( x ) = ( z ，卵) iz g ，g s ) 有向环网络，有向双环网络等 均可看作是c a y l e y 有向图 定义1 2 5 ：设g 为有限群( e 为g 的单位元) ，s 是g 的生成子集且满足 下列条件t ( 1 ) e 隹s ，( 2 ) 9 4 s 当且仅当9 s 财群g 关于子集s 的c a y l e y 无向图x = c a y ( g ，s ) 定义为；v ( x ) = g ，e ( x ) = ( z ，z g ) i g ，g s ) 熟知的环网络，无向双环网络圆环面网络超立方体网络，立方体连接 圈，星图( s t a rg r a p h ) 等均可看作是c a y l e y 无向图 定义1 2 6 设g 为有向圈，若g 的每一个顶点的出度与入度都等于k ， 则称g 是七- 正则的 定义1 2 7 ：设g 为无向图，若g 的每一个顶点的度都等于k ，则称g 是 k 一正则的 定义1 2 8 ：两个有向( 或无向) 图g 和日称为同构的，如果存在一个双 射妒：v ( g ) _ + v ( h ) 使得( 。，y ) e ( g ) 当且仅当( p ( z ) ，l p ( g ) ) e ( 日) 双射妒 称为g 和日的一个同构映射如果g = h ，则称妒为g 的一个自同构映射 定义1 2 9 ：有向( 或无向) 图g 称为是点对称的，如果对于任意的z ，y y ( g ) ，均有g 的一个自同构p ，使得i p ( $ ) = v 有向( 或无向) 图g 称为是弧 ( 或边) 对称的，如果对于任意的两条弧( 或边) ( 马v ) ，( “，”) e ( g ) ，均有g 的一 个自同构协使得妒( z ) = u ，妒( v ) = ” 定义1 2 1 0 ：一个有向( 或无向) 图g 是，一容错的，如果对于任意的 f y ( g ) ，i f l ，g f 仍是连通的图g 的容错性( f a u l tt o l e r a n c e ) 定义为 最大的，使g 是，容错的 定义1 2 1 1 ：设有向( 或无向) 图g 是女正则的，如果一( g ) = ，则称g 是极大容错的( m a x i m a l l yf a u l tt o l e r a n t ) 定义1 2 1 2 ：设g 是有向( 或无向) 图g 的一个圈，如果y ( c ) = y ( g ) ， 则称c 为图g 的一个h a m i l t o n 圈此时该图也称为h a m i l t o n 图 本节中没有给出的符号和定义我们将在适当的地方给出 7 第二章有向双环网络 2 1 引言 有向( 或无向) 双环网络具有如下优点网络直径较小，易于扩展，具有 对称性且有一定的容错能力因而这类网络广泛应用于计算机网。局域网及大 规模并行处理系统对该问题的研究是当前局域网络和并行分布系统理论与 应用中一个重要的课题许多学者对有向双环网络的研究感兴趣他们的兴趣 主要在最优双环网络，网络直径，与路由算法等 设1 8 l ，s 2 n ，8 1 8 2 有向双环网络g ( n ；8 l ，8 2 ) 是如下定义的有向 图( u e ) ：其结点集是v = z 。= o ，1 ，2 ，n l ，弧集是e = “- + + 8 1 ( r o o d n ) ，i - + i + 8 2 ( r o o dn ) ii = 0 ，1 ，2 ，n 1 ) 有向双环网络g ( n ；8 1 ，8 2 ) 是强连通的充分必要条件是g c d ( n ，8 l ，8 2 ) = 1 事实上g ( n ；s l ，8 2 ) 是凯莱图 c a u ( z 。， s l ，8 2 ) 本文所考虑的有向双环网络均是强连通的，即g e d ( n ，8 1 ，8 2 ) = 1 _ 图2 1 1 所示的是有向双环网络0 ( 8 ；2 ，3 ) 欲研究g ( n ；8 - ，8 2 ) 的直径( 或者路由) 只需考察从结点0 到其它结点的 距离( 或者路径) 为此在笛卡尔平面直角坐标系中，第一象限中的所有格点 ( 。，v ) 按下列顺序排成序列t ( 0 ，o ) ，( 1 ，o ) ，( 0 ，1 ) ，( 2 ，o ) ，( 1 ，1 ) ，( o ，2 ) ，( o ) ，0 1 ，1 ) ，u 一2 ，2 ) ，( j i ，f ) ，( 1 ，j 一1 ) ，( o ，j ) ，每个格点用它右上角的单位 方格为代表，并且依次在每一方格) 处放置数t ( o ，1 ，2 ，n 1 ) ，其 中ez s l + 们2 ( r o o dn ) 如在此前数k 已出现过，则空出此方格，考察下一 个格点，直到数0 ，1 ，2 ，n l 都出现为止易知若数位于方格( $ ，) 处， 则g ( q 8 1 ，8 2 ) 中从结点0 到结点的距离是+ p 已经证明( 参见【6 ，5 4 j ) ，由 g ( n ；8 1 ，s 2 ) 所确定的n 个方格组成的构图呈图2 1 2 所示的上_ 形区域( 矩形区 域是特例) 定义2 1 1 ：如图2 1 2 所示的l 形区域称为具有参数( z ， ，) 的一 个厶形瓦( l - s h a p et i l e ) ，其中f ，h ，z ，口都是整数，并规定f ，h 2 ，0sz f ， 0s 挈 h 这个厶形瓦记为l ( n ；t ，h ，z ，珐用a ( l 0 2 ；t ，h ，z ，暂) ) ( 简记为d ( 二) ) 表 示m “ 2 + h z 一2 ，z + h y 一2 ) ，称为工( qr ，h ，z ，) 的直径由g ( n ；s 1 ，j 2 ) 所 确定的l 形瓦记为工( g ( n ；8 l ，8 2 ) ) 用d ( n ；s l ，8 2 ) 表示双环网络g ( n ；3 1 ，s 2 ) 的直径 壶玎果三( n ；z ，h ，。，扩) = ( g ( n ；5 l ，s 2 ) ) ，则d ( n ；8 1 ，8 2 ) = m a x t + h 一。2 ，z + h 一 8 y 一2 ) c y i n g ，f k h w a n g 1 1 】给出了一个时间为o ( 1 0 9n ) 的算法用于计算有向 双环网络g ( n ；8 1 ，s 2 ) 的直径 令d ( n ) = m i n d ( n ；8 1 ，s 2 ) i1 8 1 ，s 2 n ) ，d l ( n ) = m i n d ( n ；1 ，s ) i1 k ) 比如；g ( 4 5 0 ；1 ，5 9 ) 是1 紧优的，其直径为3 6 ，但不是o 紧最优的g ( 4 5 0 ；2 ，1 8 5 ) 是o 紧最优 的，其直径为3 5 定义2 1 4 ：如果n 是奇异k 紧的整数且g ( n ；s 1 ，s 2 ) 是女一紧最优的，则 称g ( n ；s i ，s 2 ) 是奇异k 一紧优的双环网络 定义2 1 5 ：l - 形瓦工( n ；f ，h ，。，y ) 称为b 紧的，如果d ( l ( n ；l ，h ，v ) ) = l b ( n ) + k 当k 茎4 时，李乔，徐俊明，刘琦，张忠良，刘焕平，杨义先等对如紧优的双 环网络无限族已进行了一些研究，参见文献【5 4 ，8 2 8 6 ，5 0 从文献【8 3 ，8 5 ，8 6 】 可看出：当女2 时，构造k 紧优的双环网络无限族并不容易本文给出了 一个方法用于构造k 紧优双环网络无限族( k21 ) ，利用此方法可以比较容易 地构造出b 紧优无限族利用这个方法我们构造了4 族3 紧优无限族，3 族 新的4 - 紧优无限族，3 族5 - 紧优无限族及2 族6 - 紧优无限族 另外利用计算机搜索我们还找到了2 7 族新的m 紧优无限族，2 6 族新的 1 紧优无限族，8 族新的2 紧优无限族。2 族3 - 紧优无限族 对于奇异0 - 紧优的双环网络无限族，徐俊明，f a g u i l o ，e s i m o 和m z a r a g o z a 【8 4 ，2 2 】进行了一些研究，并给出了一些奇异0 - 紧优的双环网络无限 族本文将给出一些新的奇异0 紧优的双环网络无限族另外我们给出了一 种行之有效的方法用于构造奇异l 一紧优无限族，利用此方法我们构造出3 族 奇异1 一紧优无限族根据此方法我们也构造出了1 族奇异2 紧优无限族 另外我们证明了：对于b 紧优的正整数n ，若厶形瓦l ( q l ，h ，z ，y ) 是k 紧的，则i z y i 2 k + 6 利用这个结论我们给出了判断一个正整数是否奇异 的算法，此算法的时间复杂性为o ( k 2 。5 护。l o gn ) 1 0 2 2 计算有向双环网络直径的一个新的算法 c y i n g ，f k h w a n g 【1 1 1 给出了一个时间为o ( 1 0 9n ) 的算法用于计算有向 双环网络g m s l ，s 2 ) 的直径这一节我们也将给出一个新的算法用于计算有 向双环网络的直径虽然我们算法的时问复杂性与文献【1 1 】一样为o ( 1 0 9n ) ， 但我们的算法易于分析，原因在于我们利用平行四边形为工具来计算双环网 络的直径 设n ，8 1 与s 2 均是正整数且满足lss 1 ，8 2 n ，s l s 2 ，g c d ( n ，8 l ，8 2 ) = l l 对于双环网络g ( n ；8 1 ，s 2 ) ，从点i 到点( i + 8 1 ) ( r o o dn ) 的边称为【+ s l 】边，点 i 到点( i + 却) ( m o dn ) 的边称为【+ 3 2 】边若一条从点i 到点j 的路径，它包 含2 条【+ s l 】边，y 条【+ s 2 1 边，则有j i ( i + z 8 1 + y 8 2 ) ( m o dn ) ，且等 式成立与路径中边出现的先后顺序无关因为我们仅对路径的长度感兴趣， 此路径将记为x + s t l + 讣 5 2 】 对于给定的双环网络g ( n ；8 1 ，s 2 ) ，我们在z 2 平面上构建一个无限的网格 g 。，给每一个格点( f ，j ) 一个标号如l + i s 2 ( m o dn ) 每一个标号m ( 0 1 7 1 n ) 在网格g 。；“。上无限次地重复出现因为( 一t s 2 ) s l + ( t s l ) s 2 = 0 ， 所以格点( 一t s 2 ，拈1 ) 与0 对应，这里t z ，即格点( 一s 2 ，t s l ) 的标号为0 标号 为0 的格点称为零格点 定义2 2 1 ：两个格点(