（应用数学专业论文）互连网络超连通度的研究.pdf

摘要 我们通常用一个连通的无向图或强连通有向图g = ( v e ) 作为互连网络的 拓扑结构，这时图g 的顶点代表网络中的计算机，计算机之间的通信联系用相应 顶点之间的边来表示连通度圪( g ) 和边连通度a ( g ) 则是衡量该互连嘲络可靠性 的重要参数，它们表明对应的互连网络可以容许一( g ) 一1 个结点或a ( g ) 一1 条信 息传输信道同时发生故障仍能保证剩余子网络中各结点之间的通信所以( 边) 连 通度越大，网络的可靠性越高 为了更准确地度量网络的容错性，人们提出了图的超连通度和超边连通度的 概念设图g = ( v e ) ，s 是顶点集y 的一个子集，若g s 不连通并且g s 不含孤立点，则称s 是g 的一个超顶点割图g 的超连通度k ( g ) 定义为g 的 所有超顶点割的最小基数同样地，设f 是边集e 的一个子集，若g f 不连通 并且g f 不舍孤立点，则称f 是g 的一个超边割图g 的超边连通度a ，( g ) 定义为g 的所有超边割的最小基数 本文的主要研究内容是互连网络的超连通度和超边连通度全文共分五章 第一章介绍了本文用到的一些图和网络的基本概念，超连通度和超边连通度 的定义、应用背景以及目前已经取得的一些结果 第二章对一般有向图展开讨论，给出了正则有向图的超边连通度的一个下界 第三章研究线图的超连通度和原图的超边连通度之间的关系，分别对有向图 和无向图的线图进行讨论，得到了如下结论：如果d 是最优超边连通的平衡有向 图，则它的线图的超连通度恰好是原图的超边连通度的两倍；如果g 是a 7 连通的 无向图，则它的线图的超连通度和原图的超边连通度相等的充要条件是g 不是超 a 7 的 第四章是本文的主要部分，在前两章的研究基础上确定了一些特殊网络的超 连通度和超边连通度，得到了以下几个结果： 1 确定了d eb r u i j n 有向图和k a u t z 有向图的超边连通度和超连通度：对任 l v 中国科学技术大学博士学位论文 意的整数d 3 ，凡3 ，d eb r u i j n 有向图b ( d ，规) 的超边连通度是2 d 一2 ；对任意 的整数d 2 ，n22 ，。k a u t z 有向图k ( d ，凡) 的超边连通度是2 d 一2 ，超连通度是 4 d 一4 ( 除了k ( 2 ，2 ) ) 2 确定了广义d eb r u i j n 有向图和广义k a u t z 有向图的超边连通度：对任意 的直径不小于4 的广义d eb r u i j n 有向图b g ( d ，n ) 和广义k a u t z 有向图( d ，n ) ， 如果d 4 ，则它们的超边连通度都是2 d 一2 3 确定了d eb r u i j n 无向图和k & u t z 无向图的超边连通度：对任意的整数 d 3 ，n 3 ，d eb r u i j n 无向图u b ( 。d ，n ) 和k a u t z 无向图u k ( d ，礼) 的超边连 通度都等于4 d 4 在第五章中，我们对本文的工作进行了总结，并且提出了几个有待迸一步研究 的问题 a b s t r a c t i ti sw e l l - k n o w nt h a tw h e nt h eu n d e r l y i n gt o p o l o g yo fa ni n t e r c o n n e c t i o nn e t w o r ki s m o d e l l e db yac o n n e c t e dg r a p ho rs t r o n g l yc o n n e c t e dd i g r a p hg = ( v 目) ，w h e r evi st h e s e to fp r o c e s s o r sa n dei st h es e to fc o m r n u n i c a t i o nl i n k si nt h en e t w o r k ，t h ec o n n e c t i v i t y k ( g ) a n de d g e c o n n e c t i v i t ya ( g ) a r ei m p o r t a n tm e a s u r e m e n t sf o rf a u l t t o l e ia l i c eo ft h e n e t w o r kt h en e t w o r kc a r lt o l e r a t ek ( g ) 一1c o m p o n e n tf a i l u r e so ra ( g ) 一1l i n kf a i l u r e s t or e m a i nc o n n e c t e d t h u s jt h eh i g h e rt h ec o n n e c t i v i t ya n de d g e - c o n n e c t i v i t y8 e ，t h e m o r er e l i a b l et h en e t w o r ki s t om e a s u r ef a u l tt o l e r a n c eo fn e t w o r k sw e l la n dt r u l y , m o r er e f i n e di n d i c e st h a n c o n n e c t i v i t ya n de d g e c o n n e c t i v i t y ，s u p e rc o n n e c t i v i t ya n ds u p e re d g e c o n n e c t i v i t yw e r e p r o p o s e d as u b s e tscv ( g ) ( r e s p fce ( g ) ) i sc a l l e das u p e rv e r t e x c u ( t ( r e s p s u p e re d g e c u r ) i fg s ( r e a p g f ) i sn o tc o n n e c t e da n de v e r yc o m p o n e n t lc o n t a i n s a tl e a s tt 。w ov e r t i c e s t h es u p e rc o n n e c t i v i t y ( g ) ( r e s p s u p e re d g e c o n n e c t i v i t ya 7 ( g ) ) i st h em i n i m u mc a r d i n a l i t yo v e ra l ls u p e rv e r t 。e x - c u t s ( r e s p s u p e re d g e - c u t s ) i ngi fa n y 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 es u p e rc o n n e c t i v i t ya n ds u p e re d g e c o n n e c t i v i t y o fn e t w o r k s i tc o n s l l s t so ff i v ec h a p t e r s 一i 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 r m i n o l o g ya n dn o t a t i o nu s e d i 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 fs u p e rc o n n e c t i v i t ya n ds u p e re d g e c o n n e c t i v i t ya n dl i s ts o m er e s e a r c hr e s u l t so nt 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 h es u p e re d g e c o n n e c t i v i t yo fa g e n e r a l d i g r a p h ，a n de s t a b l i s hal o w e rb o u n do ft h es u p e re d g e c o n n e c t i v i t yo fr e g u l a rd i g r a p h i nt h et h i r dc h a p t e r ，w ec o n s i d e rt h er e l a t i o n s h i pb e t w e e nt h es u p e re d g e c o n n e c t i v i t y o fag r a p ha n dt h es u p e rc o n n e c t i v i t yo f i t sl i n eg r a p h f o rs ，c o n n e c t e db a l a n c e d d i g r a p hda n di t sl i n ed i g r a p hl ( d ) ，i fd i so p t i m a l l ys u p e re d g e c o n n e c t e d ，t h e n k ( l ( d ) j = 2 a ( d ) f o ra c o n n e c t e dg r a p hgw i t ho r d e ra t l e a s tf o u rr a t h e rt h a na s t 。a r a n di t s1 i n eg r a p h 上( g ) ，托7 ( l ( g ) ) = a ( g ) i fa n do n l y 1 i fg i sn o ts u p e r - a t h em 缸nr e s u l t sc o n t a i n e di nt h e 】f o u r t hc h a p t e ra r el i s t e db e l o w 1 d e t e r m i n et h es u p e rc o n n e c t i v i t ya n dt h es u p e re d g e c o n n e c t i v i t yo ft h ed eb r u i j n d i g r a p ha n dt h ek a u t zd i g r 印h ：f o ra n yd 3 ，n 3 ，t h es u p e re d g e c o n n e c t i v i t y o ft h ed eb r u i j nd i g r a p hb ( d ，n ) i s2 d 一2 ，a n dt h es u p e rc o n n e c t i v i t yi s4 d 一4 ； v v i中国科学技术大学博士学位论文 f o ra n yd 2 jn 2 it h es u p e re d g e - c o n n e c t i v i t yo ft h ek a u t zd i g r a p hk ( d ，n ) i s 2 d 一2 ，a n dt h es u p e rc o n n e c t i v i t yi s4 d 一4 ( e x c e p tk ( 2 ，2 ) ) 2 d e t e r m i n et h es u p e re d g e c o n n e c t i v i t yo ft h eg e n e r a l i z e dd eb r u i j nd i g r a p ha n d t h eg e n e r a l i z e dk a u t zd i g r a p h ：f o ra n yg e n e r a l i z e dd eb r u l j nd i g r a p hb a ( d ，n ) a n d g e n e r a l i z e dk a u t zd i g r a p hk g ( d ，n ) w i t hd i a m e t e r ，i fd 4 ，4 ，t h e nt h e i r s u p e re d g e - c o n n e c t i v i t ya r eb o t he q u a lt o2 d 一2 3 d e t e r m f n et h es u p e re d g e c o n n e c t i v i t yo ft h ed eb r m j nu n d i r e c t e dg r a p ha n dt h e k a u t zu n d i r e c t e dg r a p h if o ra n yd 3 ，仡3 ，t h es u p e re d g e - e o n n e c t i v i t yo fd e b r u i j nu n d i r e c t e dg r a p hu b ( d ，n ) a n dt h ek a u t zu n d i r e c t e dg r a p hu k ( d ，n ) a r e b o t he q u a lt o4 d 4 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 第一章图与网络 计算机互连网络( i n t e r 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 lu r e s ) 在分析网络拓扑结构时，人们通常以( 有向或无向) 图作为数学模型，这时图中的顶 点代表网络中的计算机，而一对计算机之间的直接通信联系则用连接这对顶点的 边来表示研究网络的拓扑结构问题就归结为图的结构问题，换句话说，图是网络 拓扑结构的数学模型，我们可以通过图论方法来研究网络的拓扑结构因此网络 拓扑的性能可以通过图的性质和参数来度量 互连网络可以用图来模拟，因此互连网络与图论有着密切的关系事实证明， 图是互连网络设计和分析的最有用的数学工具，并已被计算机科学家广泛接受和 采用本章将会在第一节简单介绍图和网络的基本概念以及在以后讨论中要用到 的记号；第二节介绍互连网络的连通度及应用背景；第三节介绍超连通度的概念； 第四节列举了近年来在超连通度方面取得的一些结果有关图的术语和记号可参 见徐俊明的图论及其应用f 4 2 1 1 图与网络的基本概念 设( 谚e ) 是图，其中矿非空称为顶点集( v e r t e x s e t ) ，e 称为边集( e d g e s e t ) ，v 中元素的个数u 和e 中元素的个数e ，即u = l v i 和s = i e l 分别称为该 图的顶点数或阶( o r d e r ) 和边数( s i z e ) 用无序对x y 来表示成对的对称边( x ，可) 和( y ，z ) 有序对e = ( z ，y ) e 称为有向边，z 称为边e 的起点，y 称为边e 的终点；而e = x y 称为无向边， 起点和终点统称为边e 的端点边的两端点称为相邻的( a d j a c e n t ) ，两端点相同 的边称为自环( 1 0 0 p ) 无自环无平行边的图称为简单图( s i m p l eg r a p h 或s i m p l e 1 2中国科学技术大学博士学位论文 d i g r a p h ) 任何两个顶点之间都有边相连的简单无向图称为完全 ( c o m p l e t eg r a p h ) ， 完全图的对称有向圈称为完全有向p e ( c o m p l e t ed i g r a p h ) 在同构意义下，”阶 完全图和完全有向图都是唯一的，分别记为墨。和k ： 设e = x y e ( g ) ，白( e ) = d e ( x ) + d c ( 掣) 一2 称为边e 的度f ( g ) = m i n 如( e ) ：e e ( g ) ) 称为图g 的边度 设d 是有向图若站( ) = d d ( y ) ，则称y 为平衡, , 占, , ( b a l a n c e dd e g r e e ) 每个点都为平衡点的有向图称为平衡有向 ( b a l a n c e dd i g r a p h ) 用+ ( d ) ， 一( d ) ，6 + ( d ) ，5 - ( _ d ) 分别表示d 的最大( m a x i m u m i i 和最小( m i n i m u m ) 顶点 出、入度这4 个参数都等于盼图称为正则有向图f k - r e g u l a rd i g r a p h ) 设d = ( v e ) 是有向图，s 和t 是v 中两个不交的非空真子集，用点1 d ( s ，t ) 表示g 中起点在s 而终点在t 的边集，并且令正1 d 【s ，t 】= e d ( s ，t ) u e d ( ：t ，s ) ， 当所考虑的图只有一个时，就分别简记e o ( s ，t ) 和点1 d 瓯t 】为( s ，t ) 和晦刁 若t = s 7 = v 号，则简谒e d ( s ，s ，) 为磁( s ) ；e d ( s ，s ) 为j e 芴( s ) ；e n s ，s 】 为如研记妨( s ) = l 磁( s ) l ，蛄( s ) = 1 ( 趴 习惯上称完全二部分图k 1 。为星( s t a r ) 设z ，y v 若d ( 或g ) 中存在连接z 和y 的路，则称z 和y 是连通的若 d ( 或g ) 中每对顶点都是连通的，则称d ( 或g ) 为连通 ( c o n n e c t e dd i g r a p h o rg r a p h ) ，反之为非连通图( d i s c o n h e c t e dg r a p h ) 设d 是有向图，并设z ，y v ( d ) 若d 中既存在从z 到y 的有向路又存在 从y 到z 的有向路，则称茁和y 是强连通 s t r o n g l yc o n n e c t e d ) 若d 的每 对顶点都是强连通的，则称d 为强连通图t 反之，称为非强连通图 如不加特殊说明，本文所涉及的图均为有限简单图 1 2 互连网络的连通度及应用背景 3 1 2 互连网络的连通度及应用背景 互连网络的可靠性( r e l i a b i l i t y ) 是： 平估网络性能的重要概念高可靠性的互 连网络直是网络设计者追求的重要目标之一 影响可靠性的因素很多这里我们只从网络的拓扑结构上考虑硬件故障对网 络可靠性的影响，即在网络结点和( 或) 连线可能发生故障的情况下的数据传输可 靠性也就是说当部分处理机或连线失效时，剩余的子网络中各结点之间仍能正 常工作，这种可靠性文献上习惯称为容错1 i ：生( f a u l tt o l e r a n c e ) 网络容错性的实质是当故障发生时，剩余网络的重组能力 任何高性能网络，个别组件和( 或) 连线在运行过程中失灵是难免的我们以后 所说的网络容错性是指该网络能容忍多少组件和( 或) 连线同时失灵，剩余的予网 络中各结点之间仍能继续保持通信 度量网络容错性的一个重要参数就是该网络模拟图的连通度 设z 和y 是有向图d 中两个不同的顶点，汐是d 中从z 到y 的有向路集 若汐中任何两条路只和局均有y ( r ) ny ( 弓) = z ，9 ) ，则称汐是d 中内 点不交的( i n t e r n a l l yv e r t e x - d i s j o i n t ) ( z ，y ) 路集；若驴中任何两条路只和局 均有e ( 只) nf ( 弓) = 0 ，则称汐是d 中边不交的( e d g e d i s j o i n t ) ( z ，) 路集 我们用白( z ，y ) 和佃( z ，y ) 分别表示d 中内点不交和边不交的( z ，y ) 路的最大 条数 若存在一个非空子集scv ( d ) 。，可) 使得d s 中不存在( z ，y ) 路，则称 s 为d 中( 。，y ) 分离集( s e p a r a t i n gs e t ) 具有最少顶点数的( z ，y ) 分离集称为 最小( 。，y ) 分离集用k d ( z ，) 表示d 中最小( z ，y ) 分离集中的顶点数目若 存在一个非空子集bce ( d ) 使得d b 中不存在( z ，y ) 路，则称日为d 中 ( x ，y ) 截边集( c u te d g e - s e t ) 具有最少边数的( z ，) 截边集称为最小( zy ) 截边 集用a 口( z ，y ) 表示_ d 中最小( 。，y ) 截边集中的边数 无向图也有类似的定义但是，对于有向图d ，点集s 是( z ，y ) 分离集，却不 4中国科学技术大学博士学位论文 一定是妇，) 分离集；而对无向图g ，若s 是( ，曹) 分离集，刚s 必是0 ，) 分 离集若在有向图d 中没有以z 为起点并且以y 为终点的有向边( 或z 和y 在 无向图g 中不相邻) ，则在d ( 或g ) 中( z ，y ) 分离集一定存在由定义立即有 白( z ，可) s 托d ( z ，笋) ； r l d ( x ，) a d ( x ，) 事实上，上面两个不等式的等号是成立的，这就是图论中著名的m e n g e r 定理， 它阐述了上述四个参数之阔的关系是互连网络拓扑结构设计和可靠性、容错性 分析的基础，叙述如下： 定理1 2 1 ( m e n g e r 定理) 设z 和可是d 中不同的两个顶点，则 ( 1 ) f 7 d ( z ，y ) = a 口( o ，鲈) ； ( 2 ) ( d ( z ，) = k d ( 石，) ，岔口果( 。，y ) 隹e ( d ) m e n g e r 定理的证明参见徐俊明 4 2 中的定理42 和4 3 m e n g e r 定理中的 两个结沦是等价的因为无向图可以看成特殊的有向图，上述四个参数的定义和 。m e n g e r 定理同样适合于无向图 设g = ( k e ) 是连通的无向图( 或强连通的有向图) ，若矿的子集矿7 使得 g y 不连通( 或不强连通) ，则v 称为g 的顶点割( v e r t e x - c u t ) 若g 至少有 一对相异的不相邻顶点，则g 必有顶点割。定义k ( g ) = r a i n s f ：s 是g 的顶 点割或l s i = l v l 一1 ) 为g 的连通度( c o n n e c t i v i t y ) 若圪( g ) k ，则称g 为k 连通的 著e 的子集e 使得g e7 不连通( 或不强连通) ，则e 称为g 的边割( e d g e c u t ) 边割是指有k 个元素的边割于是把g 的所有k 边割中最小的，称 为g 的边连通度( e d g e - c o n n e c t i v i t y ) ，记为a ( g ) 若g 是平凡图或不连通时， a ( a ) = 0 若a ( g ) ，则称g 为边连通的所有非平凡连通图都是1 边连通 的 w h i t n e y 于1 9 3 2 年首次发现无向图g 的连通度k ( g ) 、边连通度x ( a ) 和 1 2 互连网络的连通度及应用背景 5 最小度5 ( a ) 之间有的关系，这就是著名的w h i t n e y 不等式 定理1 2 2 ( w h i t n e y 不等式) ( 3 8 】) 对任何连通无向图g ，k ( g ) 墨 ( g ) 6 ( g ) w h i t n e y 不等式对有向图d 也成立，其证明可以参见3 9 1 定理1 2 3 对任何强连通的有向图d ，n ( d ) t ( d ) s6 ( d ) w h i t n e y 在同一篇文献中给出了一个无向图是七连通或七边连通的充分必 要条件，有时称它为w h i t n e y 连通判别准则而对强k 连通或强k 边连通的有 向图也有类似的判别准则( 证明可以参见f 39 ) 定理1 2 4 设k 1 ，并且设g 是( 七+ 1 ) 阶无向图( 或有向图) ，则 ( 1 ) 圪( g ) 当且仅当( g ( z ，y ) k ，对任意的x ，y y ( g ) ( 2 ) a ( g ) 膏当且仅当w ( z ，y ) 七，对任意的x ，y y ( g ) 连通度的网络应用是很明显的若图的连通度为，则表明对应的瓦连网络 可以容许k 一1 个结点同时发生故障而不会导致剩余予网络中各结点之间的通信， 同样的，若图的边连通度为，则表明对应的互连网络可以容许k 一1 条信息传输 信道同时发生故障而不会导致剩余子网络中各结点之问的通信因此，连通度常 被视为互连网络可靠性和容错性的重要度量连通度越大、网络的容错性越好 连通度不仅是度量网络性能的重要参数之一，也是互连网络拓扑结构分析的 基础许多更精确度量网络性能的概念都是建立在连通度概念的基础上。所以连 通度是图论中最基本又是应用最广泛的概念，引起众多学者的广泛深入研究，并获 得许多很好的结果8 0 年代以前的研究主要是着重图论本身，m a d e r 给出了有关 这一方面早期研究结果的综述8 0 年代以后，m e n g e r 定理和连通度概念在计算机 科学中得到了广泛应用，特别是在网络拓扑结构方面，有关这方面的研究结果、进 展和应用可参见b e r m o n d ，h o m o b o n o 和p e y r a t 8 1 的综述文献 6中国科学技术大学博士学位论文 1 3 互连网络的超连通度 在计算机互连网络拓扑结构的设计和分析中，连通度是度量网络可靠性的重 要参数之一为了能更精确度量网络的容错性，人们提出了超连通度的概念这一 节我们介绍超连通度的有关概念 用连通度和边连通度来度量网络的容错性有三个缺陷：首先、两个图的连通 度( 或边连通度) 即使相同，它们的可靠性也不一定一样，因为它们的最小顶点割 数( 或最小边割数) 可能不同其次，这两个参数不能区别按不同方式移去仡个点( 或 a 条边) 后所产生的不同的连通分支的情况这说明连通度和边连通度不能反映 由于处理机或通讯信道损坏造成的系统损坏程度因而这两个参数在某些应用上 不够精确第三，在分析和应用这两个参数时我们都不言而喻的假定了系统的任 何部分都可能同时失灵，也就是说对这些参数没有加任何限制然而，在带有某种 类型故障可诊断算法的计算机互连网络中，人们可以安全地假定网络组件的某些 子集是不会同时失灵的，或者对这些参数加上某些限制对于这样的网络、经典的 连通度就不能精确的度量其可靠性了 确定图g 的连通度或边连通度时，我们只是计算使得g s 不连通( 或不强 连通) 的顶点割或边割s 的最小基数，忽略了相应的集合s 同时发生故障的可能 性换句话说，在连通度和边连通度的定义中，对g s 的分支和分离集s 没有 加任何条件或限制所以为了弥补以上缺陷，人们很自然的想到对g s 的分支 和分离集s 加上一些条件或限制，从而推广了经典连通度的概念 h a r a r y 于1 9 8 3 ( 1 9 1 ) 年首先提出条件连通度的概念，e s f a h a n i a n 和h a k i m i 于 1 9 8 8 ( 1 4 ) 年把条件更具体化，提出了限制连通度的概念这些参数能更准确的分 析各种互连网络的可靠性近几年来，它们已经引起了许多理论计算机科学工作 者和数学工作者的研究兴趣 假设图g = ( ke ) 的每个顶点发生故障的可能性均为( o p ， 1 ) ，且各 顶点能否正常工作是相互独立的；每条边发生故障的可能性也相同，均为p c ( 0 a f 固 对有向图也有类似的定义，只须将上述定义中的“连通”改为“强连通”即可 这里就不再赘述了， 从互连网络的实际应用来考虑，研究网络的超连通度( 或超边连通度) 是很有意 义的因为与同一个处理机直接相连的处理机( 或连线) 同时失灵的可能性实际上 是很小的另外，如果图g 是超连通( 或超边连通) 的，且k ，( g ) ( 或a7 ( g ) ) 存在，则 圪( g ) ( g ) ( 或a ( g ) a 7 ( g ) ) ，因此等式( 1 1 ) 中对于i = k + 1 ，仡+ 2 ，k l l l 都有k = 0 ( 或等式( 1 2 ) 中对于i = a4 - 1 ，a + 2 ，一，a ，一1 都有c 。：0 ) 由超连通度( 超边连通度) 的定义可知，图g 的超连通性( 超边连通性) 可以用参数 超连通度x g ) ( 超边连通度a 7 ( g ) ) 来度量所以研究图的超连通度f 或超边连通 度) 比仅仅研究其超连通性( 或超边连通性) 更有意义 1 4 超连通度的已知结果 超边连通度是b 直u e r 5 1 等人研究网络可靠性时提出的概念，由于它反映了图 的比最大边连通度更深入的边连通性质，因而获得了广泛的关注和研究( 5 ， 6 ， 1 1 ， 1 2 ) 有些文献把它称为限制边连通度 关于超连通度的一般性结论很少，一般图的超连通度k ，( g ) 的存在性到目前 为止还是一个尚未解决的问题，但是，如果无向图g 的超连通度存在，则必有 k ( g ) 兰k ( g ) ( g ) ， 5 1 , 4 超连通度的已知结果 9 其中( g ) 是图g 的边度， 现在日经证明了有些图的超连通度是存在的而且恰好等于其边度例如，e s - f a h a n i a n ( 【1 5 ) 证明了当n 3 时，n 阶超立方体的超连通度等于其边度，即 g t ( ) = 2 n 一2 ；李乔和张翊( f 2 5 ， 2 6 ) 确定了2 连通的无向d eb r u i j n 图和 k a u t z 图的超连通度：k 7 ( u b ( 2 ，n ) ) = 3 ，i g t ( u k ( 2 ，n ) ) = 4 ，其中札3 值得高兴的是无向图超边连通度的研究却取得了比较好的结果首先它的存 在性已由e s f a h a n i a n 和h a k i m i ( 1 4 1 ) 解决，并给出了它的上界和下界 定理1 4 1 若无向圈g 既不是星1 ，。也不是三阶完全图j b ，则图g 的 超边连通度州g ) 存在，并且 ( g ) 7 ( g ) s ( g ) 连通图g 被称为连通图( y - c o n n e c t e dg r a p h ) ，如果图g 既不是星 k 1 ，。也不是三阶完全图k 3 显然，连通图的阶数至少是4 ，它的超边连通度一 定存在， 下面的定理给出了图g 的最小度d ( g ) ，边连通度a ( c ) 和超边连通度a ( g ) 之间的关系： 定理1 4 2 ( 【3 9 】) 设图g 是a 连通图，那么 ( 1 ) 女口果a ( g ) d ( g ) ，贝0a 7 ( g ) = a ( g ) ； ( 2 ) 如果a 7 ( g ) sd ( g ) ，贝0 a 7 ( g ) = a ( g ) ； ( 3 ) 如果a ( g ) a 7 ( g ) ，贝qa ( g ) = 6 ( g ) 如果a 7 连通图的超边连通度达到上界，即a 7 ( g ) = ( g ) ，称g 为a 7 最优的 ( k - o p t i m a l ) ，否则称为a 7 非优的( a t - n o n o p t i m a l ) 例如长度为4 的圈q 就 是a ，最优的 在网络的容错性和可靠性研究中，人们更关心的是：什么条件可以保证g 的 超边连通度达到其最大值，即使得g 是a 7 最优图目前已经得到一些充分条件： 1 0中国科学按术大学博士学位论文 定理1 4 3 ( 3 9 ) 如果n 阶a ，连通圈g 的最小度6 ( g ) ；l + 1 ，则图g 是a 最优的 这个结果被王应前和李乔( 3 5 1 ， 3 6 ) 推广成下述结果： 定理1 4 4 设礼( 24 ) 阶图g 的任意一对不相邻顶点z 和y 的度和满足 d ( x ) - l d ( y ) n + 1 ，或图g 的直径为2 ，最小度d ( g ) 3 并且不含三角形，则图 g 是a 7 最优的 如果图g 中有圈，把g 的最短圈的长度叫做g ! 的国长( g i r t h ) ，记作9 = 9 ( a ) 已经发现直径d 和围长9 之间的不同约束蕴含着图的各种不同的连通 性( 6 ， 1 2 ， 16 j ， 1 7 ， 1 8 ， 3 2 ) f 磊b r e g a 和f i o l ( 1 1 6 ) 通过用直径d 和围长 g 的约束条件给出了g 是超边连通的充分条件：如果g 的最小度6 ( g ) 3 ，直 径ds 2 旦； 一1 ，则c 是超边连通的受到这个结果的影响，王应前和李 乔( 3 7 】) 得到了g 是a7 最优图的充分条件 定理1 _ 4 5 如果a 7 连通图g 的最小度6 ( g ) 3 ，直径d 和围长g 满足 d 茎g 2 ，则图g 是) 、最优的 为了更进一步的研究入7 连通图g 的超边连通度，人们开始研究超边原子 设图g 是礼阶a 连通图，f = 虽7 = ，x ，j 是g 的一个超边割，简称为 a 7 割子集x 和x 7 都称为图g 的超边片f ( s u p e re d g e f r a g m e n t ) ，简称a 7 片 ( x - f r a g m e n t ) 图g 的a 原子数( , v - a t o m i cn u m b e r ) 定义为g 的所有a 片 的基数的最小值，记做n ( g ) 显然，2 曼( g ) l 等i g 中使得i x l = 凸，( g ) 的a 7 片x 称为g 的超边原子( s u p e re d g e a t o m ) ，简称为 原子( a a t o m ) 下面 的定理给出了a 7 连通图是a 7 最优图的一个充分必要条件： 定理1 4 6 ( 4 1 】)a 7 连通图g 是a 最优的当且仅当a t ( g ) = 2 如果a7 连 通图g 是非优的，则g 中任何两个不同的a 原子是不交的特别的，如果g 是d 正则的) 、7 非优图，则。7 ( g ) d23 在此基础上，得到下面的结论： 定理1 4 7 ( 【4 1 ) 如果g 是d 正则d 边连通图且o ( g ) 3 ，那么g 的任 1 4 超连通度的已知结果 何两个a 原子都是不交的 孟吉祥( 【3 1 ) 也独立得到上面的结论很多人考虑了刮迁图的超边连通度，得 到了下面的几个结论 定理1 4 8 ( 4 1 】) 设g 是一个阶至少为4 的边可迁连通图，若g 不是星， 则g 是a 最优的，即a 7 ( g ) = ( g ) 下面考虑点可迁图的超边连通度徐俊明等( f 4 1 j ) 首先证明了下面的原子分解 定理： 定理1 4 9 设g 是d ( 3 ) 正则的点可迁连通图，x 是g 的a7 原子如 果g 是a 7 非优的，则 ( 1 ) a x 是g 的点可迁子图且含三角形，正则度为1 ； ( 2 ) g 的阶数为偶数，并且v ( g ) 存在一个划分 x 。，恐，五。) 使得对每 个i = 1 ，2 ，m ，( m 2 ) 都有g 五 掣a i x 定理1 4 1 0 ( 4 0 )设g 是阶至少为4 ，顶点度为尼( 2 ) 的点可迁连通图 若g 是奇阶的或者不含三角形，则g 是川最优的，即a 7 ( g ) = ( g ) = 2 k 一2 ；否 则存在整数仃l ( 2 ) ，使得k a ( g ) = 兰2 k 一3 7 ，6 对于某些特殊的点可迁图，豳定理1 4 1 0 就可以直接得到它们的超边连通度 推论1 4 1 ( 1 5 1 )札阶超立方体q 。( 礼2 ) 是a 7 最优的，即a 7 ( q ，。) = 2 n 一2 推论1 4 2 ( 2 )礼阶s t 盯图& ( n 3 ) 是a 7 最优的，即a7 ( s 。) = 2 儿一4 推论1 4 3 ( f 2 2 ) 无向超环面网( u n d i r e c t e dt o r o i d a lm e s h ) c ( d 1 ，d 2 ，厶) ， 定义为n 个无向圈q ，q 。，o 。的笛卡尔乘积c d ，c d 。q 。，如果 对每个i = 1 ，2 ，礼，都有喀4 ，则c d ，是a 7 最优的，即 a 7 ( c t d ，c d 。- c t d 。) = 4 n 一2 推论l 4 4 ( 2 8 ) 对任何连通的循环无向图g ( n ；s 1 ，s 2 ，一，s k ) ，如果n 4 ， 且它不含三角形或s k 芸，则g ( 礼；s 1 ，8 2 ，s k ) 是a 7 最优的，即a ( g ( 礼；s 1 ，8 2 ， 一，) ) = 4 k 一2 1 2中国科学技术大学博士学位论文 事实上，下面的定理完全解决了连通循环无向图的a 最优性： 定理1 4 1 1 ( 2 8 1 ) 个连通的循环无向图g ( n ，5 1 ，s 2 ，s ) ( 女2 ) 是a 最优的当且仅当下面的三个条件之一成立： ( 1 ) 5 女 兰； ( 2 ) 轧= 芸且g c d ，( n ，8 1 ，8 2 ，s k 一1 ) = 1 ； ( 2 ) 8 k = 芸，g ，c d ( 礼，3 1 ，s 2 ，- ，s k 1 ) = 2 且札8 k 8 w - , 除了上面提及的几类图，还有一些图的超边连通度也确定了( ( 2 7 7 ，( 2 8 j ，f 2 9 1 ， f 3 0 ， 3 1 ) 迄今为止，关于有向图的超( 边) 连通性和超( 边) 连通度的结论很少本文对一 般有向图的超边连通度作了一些研究，并确定了著名的d eb r u i j n 有向图和k a u t z 有向图的超边连通度以及广义d eb r u i j n 有向图和广义k a u t z 有向图的超边连通 度，从而得到了它们的超边连通性 线图是种重要的构图方法，在网络设计和分析中有很重要的作用本文研究 了线图的超连通度和原图的超边连通度之间的关系，在此基础上确定了d eb r u i j n 网络和k a u t z 网络的超连通度，证明了它们是超连通的 另外，吕长虹等人( 【2 9 1 ) 证明了d eb r u i j n 无向图是超边连通的，并指出2 d 一 2 a 7 ( u b ( d ，n ) ) 4 d 一4 ，其中d 2 和n 2 他们在| 刮一篇文章中证明了 a 7 ( u b ( 2 ，3 ) ) = 3 且当扎4 时) 、7 ( u b ( 2 ，礼) ) = 4 但对丁d 3 的情形没有更好 的结果，本文确定了其他情形的d eb r u i j n 无向图u b ( d ，礼) 的超边连通度；而日 对任意的整数d 和凡，确定了k a u t z 无向图u k ( d ，凡) 的超边连通度；证明了d e b r u i j n 无向图和k a u t z 无向图都是超边连通图， 第二章正则有向图的超边连通度 2 1 引言 超边连通度是经典边连通度概念的推广，而且是计算机互连网络容错性的一 个重要度量超边连通度的