（运筹学与控制论专业论文）de+bruijn图的限制边连通度.pdf

摘要 多处理机系统的互连网络拓扑通常以( 无向或有向) 图为数学模型，这 时图的顶点代表处理机，而一对处理机之间的直接通信联系则用连接这对 顶点的边来表示，因此网络拓扑的性能可以通过图的性质和参数来度量 对互连网络性能的一个关键要求是希望网络的可靠( 容错) 性好，这对应于 图论的术语来说，就是希望图的连通度和边连通度大不过用连通度和边 连通度这两个参数考究系统的可靠性有缺陷，因而作为传统边连通概念的 推广，e s f a h a n i a n 和h a k i m i 提出了限制边连通的概念：设g 是无向简单连 通图，f 是g 的一个边割，如果g f 不含孤立点，则称f 是g 的一个 限制边割最小限制边割所含的边数称为g 的限制边连通度( 有向图的限 制边连通度可类似给出) 限制边连通度是计算机互连网络可靠性的一个重 要度量超级限制边连通性是比限制边连通度更精确的一个网络可靠性指 标一个图是超级限制边连通的，如果它的任一最小限制边割都孤立一条 有最小边度的边本文主要研究了有向d eb r u i j n 图的限制边连通度和无向 d eb r u i j n 图的超级限制边连通性 在第一章我们给出本文将用到的图论方面的主要的术语、记号并介 绍了d eb r u i j n 图和限制边连通度方面的基本概念和基本结论 d eb r u i j n 图是重要的d eb r u i j n 网络的拓扑结构，曾受到广泛的研究不 过对有向d eb r u i j n 图的限制边连通度的研究还不多在本文第二章我们计 算了有向d eb r u i j n 图的限制边连通度，给出：当d 3 ，礼2 或d = 2 ，n23 时，有向d eb r u i j n 图b ( d ，n ) 的限制边连通度为( 2 d 一2 ) 根据这个结果我们 可直接得到有向d eb r u i j n 图是超级边连通的 在第三章我们将在已有结论的基础上继续对无向d eb r u i j n 图的超级限 制边连通性作更深入的研究，得到了一个有关无向d eb r u i j n 图超级限制边 连通性方面更好的结果：若无向d eb r u i j n 图u b ( d ，扎) 的阶至少为4 ，则它是 超级限制边连通的，除非d = 2 且n 3 从而全面解决了无向d eb r u i j n 图 的超级限制边连通性 关键词：网络；限制边连通度；超级限制边连通性；有向d eb r u i j n 图； 无向d eb r u i j n 图 中图分类号：0 1 5 7 5 a b s t r a c t g r a p h sa r eo f t e n a sm o d e l sf o rt h em u l t i p r o c e s s o ri n t e r c o n n e c tn e t w o r k s ，i nw h i c h t h ev e r t e xs e tc o r r e s p o n d st op r o c e s s o r s ，a n dt h ee d g es e tc o r r e s p o n d st oc o m m u n i c a - t i o nl i n k s i nt h i sc a s e ，s o m ep r o p e r t i e so ft h eg r a p h sc o r r e s p o n dt ot h ec a p a b i l i t yo f t h en e t w o r k s o n ef u n d a m e n t a lc o n s i d e r a t i o ni nt h ed e s i g no fs u c hn e t w o r k si so v e r a l l r e l i a b i l i t y ，w h i c hc a nu s u a l l yb em e a s u r e db yt h ec o n n e c t i v i t yo rt h ee d g e c o n n e c t i v i t y o ft h eg r a p h s s i n c et h e r ea r es o m el i m i t a t i o n si nm e a s u r i n gt h er e l i a b i l i t yb yt h et h e c o n n e c t i v i t yo rt h ee d g e c o n n e c t i v i t y , t h er e s t r i c t e de d g ec o n n e c t i v i t y , a sag e n e r a l i z a - t i o no fc l a s s i c a le d g ec o n n e c t i v i t y ，w a si n t r o d u c e db ye s f a h a n i a na n dh a k i m i l e tg b ea nu n d i r e c t e d ，s i m p l ea n dc o n n e c t e dg r a p h ar e s t r i c t e de d g e c u tfo fgi sa ne d g e c u ts u c ht h a tg fh a sn oi s o l a t e dv e r t e x t h er e s t r i c t e de d g e c o n n e c t i v i t ya ( 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 lr e s t r i c t e de d g e - c u t s t h er e s t r i c t e de d g ec o n n e c - t i v i t yi s a ni m p o r t a n tm e a s u r eo ff a u l t t o l e r a n c ef o ri n t e r e o n n e c t i o nn e t w o r k s t h e s u p e rr e s t r i c t e de d g ee o n n e e t i v i t yp r o v i d e sam o r ea c c u r a t ei n d e xo ff a u l t t o l e r a n c e o fn e t w o r k s gi sc a l l e das u p e rr e s t r i c t e de d g ec o n n e c t e dg r a p hi fe v e r ym i n i m u m r e s t r i c t e de d g ec u ts e p a r a t e se x a c t l yo n ee d g e i nt h i st h e s i s ，w em a i n l ys t u d yt h e r e s t r i c t e de d g ec o n n e c t i v i t yf o rt h ed eb r u i j nd i g r a p h sa n dt h es u p e rr e s t r i c t e de d g e c o n n e c t i v i t yf o rt h ed eb r u i j nu n d i r e c t e dg r a p h s i nc h a p t e r1 ，a f t e ras h o r ti n t r o d u c t i o nt ot h eu s e db a s i cn o t a t i o na n dt e r m i n o l o g yo ng r a p h s ，w eg i v ei ns e c t i o n1 2s o m ec o n c e p t sa n dp r o p e r t i e so nd eb r u i j n g r a p h s ，a n dg i v ei ns e c t i o n1 3s o m ec o n c e p t sa n db a s i cr e s u l t sc o n n e c t i v i t y d eb r u i j ng r a p h s ，a sa ni m p o r t a n tt o p o l o g ym o d e lo fd eb r u i j nn e t w o r k s ，w e r e w i d e l ys t u d i e d b u tt h e r ea r ef e wr e s u l t so nt h er e s t r i c t e de d g ec o n n e c t i v i t yo fd e b r u i j nd i g r a p h s i nc h a p t e r2 ，w ec o n s i d e rr e s t r i c e de d g ec o n n e c t i v i t yo fd eb r u i j nd i g r a p hb ( d ，n ) a n do b t a i nt h ef o l l o w i n gr e s u l t s ：a ( b ( d ，扎) ) = 2 d - 2f o rd 3 ，n 三2o r d = 2 ，礼3 ，w h i c hi m p l i e st h a tt h o s ed eb r u i j nd i g r a p h sa r es u p e re d g ec o n n e c t i v i t y i nc h a p t e r3 ，w ec o n s i d e rt h es u p e rr e s t r i e e de d g ec o n n e c t i v i t yo fd eb r u i j n u n d i r e c t e dg r a p hu b ( d ，n ) o nt h eb a s i so fs o m eo l dr e s u l t s ，a n do b t a i nt h ef o l l o w i n g r e s u l t s ：i ft h eo r d e ro fd eb r u i j nu n d i r e c t e dg r a p hu b ( d ，”) i sn o tl e s st h a n4 ，t h e ni t i ss u p e rr e s t r i c e de d g ec o n n e c t e d ，u n l e s sd = 2a n dn 3f u r t h e r m o r e ，w ea n a l y z e t i l es u p e rr e s t r i c e de d g ec o n n e c t i v i t yf o ra l ld eb r u i j nu n d i r e c t e dg r a p h s k e yw o r d s ：n e t w o r k s ；r e s t r i c t e de d g ec o n n e c t i v i t y ；s u p e rr e s t r i c t e de d g ec o n n e c t i v i t y ； d eb r u i j nd i g r a p h s ；d eb r u i j nu n d i r e c t e dg r a p h s 引言 引言 多处理机系统的互连网络拓扑结构通常以( 有向或无向) 图为数学模型，此时网 络拓扑的性能可以通过图的性质和相关参数来度量对互连网络性能的一个关键要求 是希望网络的可靠性好在假定网络的顶点不发生故障的前提下，我们已经有度量一 个网络的可靠性多项式人们常考虑m o o r s h a n n a n 模型f 3 1 ：它假定节点不发生故障， 而边以相同概率独立地发生故障设g 是一个m o o r - s h a n n a n 模型，它的边数为e ， 边发生故障的概率为p ，用m 。表示阶为i 地边割的数目那么，g 的可靠多项式可 以表示为 n e t ( a ；p ) = 1 一m i p i ( 1 一p ) 。4 t = p r o v a n 等人在1 2 1 中证明：确定所有的m ；是尸困难的为了较好的估计网络可 靠性，b a u e r 等人f 1 7 1 在上世纪8 0 年代中期提出了图的超级边连通性的概念其后 为了定量刻画超级边连通性，e s f a h a n i a n 等提出了图的限制边连通度的概念f 3 1 l i ql 等人在研究循环图的可靠性时引进超级限制边连通图的概念【4 】，更精确的度量图 的可靠性以上几个参数和性质由于能部分的解决网络的可靠性问题，提供了求网络 可靠性多项式的系数的一个较可行的途径而受到关注和研究 能高效地进行计算的多计算机系统结构的一个关键设计问题是互连网络拓扑的 选择在设计互连网络时，一般要考虑通信延迟、路由算法、顶点的度、容错性、可 扩展性、其它拓扑的可嵌入性以及v l s i 布线等方面的要求这些要求本身蕴涵着矛 盾，能在这些矛盾的要求之间取得较好的平衡并适用于顶点数目超过几千的真正大型 下一代多计算机系统的互连网络之一是d eb r u i j n 网络 3 ，4 ，1 5 ，1 6 - d eb r u i j n 图作为 描述d eb r u i j n 网络拓扑性质的数学模型，被广泛的应用在互连网络的理论设计和分 析上 d eb r u i j n 图的性质，尤其是一些连通性，由于它对应网络的容错性而被广泛研 究1 9 9 2 年，s o n e o k at 指出d eb r u i j n 图是超级边连通的m 此后，徐俊明和范英 梅在2 0 0 4 年给出了d eb r u i j n 图是超级边连通的一个简短证明f 1 3 2 0 0 2 年吕长虹 和张克民首先研究了一类特殊无向d eb r u i j n 图的限制边连通度 1 虬其后吕敏，徐俊 明等在2 0 0 4 年完全给出了无向d eb r u i j n 图的限制边连通度f 9 1 欧见平在2 0 0 4 年指 出二元d eb r u i j n 网络是极大限制边连通但不是超级限制边连通的 1 1 欧见平，张 福基在2 0 0 4 年就部分无向d eb r u u n 图，证明了它们是超级限制边连通的【1 0 咀上 工作都是在特定条件下的近似估计，由于现代科技对精度的要求越来越高，网络可靠 性进一步的精确估计有重要的实用价值和理论意义目前，我们需要进一步确定无向 d eb r u i j n 图的限制边连通度，全面的解决无向d eb r u i j n 图的超级限制边连通性；并 对有向d eb r u i j n 图得限制边连通度作具体的研究 第一章预备知识 1 图论的一些基本概念、基本术语和记号 本节只考虑有限图我们首先给出一些关于有向图的基本概念： 定义1 1 1 一个有向图d = ( ua ) 它包含一个顶点集v ( d ) 和一个弧集a ( d ) 其中弧集是不同顶点间的有序对 对于一条弧( u ，u ) ，它的第一个顶点u 称为弧的尾，第二个顶点 称为弧的头 包含平行弧( 即一些有相同的尾和头的弧) 和环( 即一条弧的尾和头重合) 的图称 为有向伪图 定义1 1 2 设d = ( k a ) 是一个有向图，对于d 中的任意一个顶点 ，我们定 义集合去( u ) = “v u ：抛a ) ， 坛( u ) = v 一口：w v a ) 其中集合 去( ) ，n d ( v ) 分别表示点u 的外邻集和内邻集 定义1 1 3 设d = ( ka ) 是一个有向图，、d 中的一条途径是指一个有限非空序 列w = x l a l x 2 a 2 x 3 x k l a k l x k ，它的交替项为顶点和弧，使得对i = 1 ，2 ，k 一1 ， 弧o 。的尾是顶点孔头是顶点z m 其中弧不重的途径又称为迹，顶点不重的途径又 称为路 命题1 1 1 【2 】设x , y 是一个有向图d 的一对相异顶点如果d 中有一条( z ，) 途径w ，那么d 中一定包含一条( z ，y ) 路p ，使得a ( p ) a ( w ) 如果d 中有一条 ( x ，y ) 闭途径，那么d 中一定包含一个通过点z 的圈c ，使得a ( c ) 垦a ( w ) 定义1 1 4 一个有向图d 称为强连通的，如果对d 中任意两个不同顶点z ，y 都 有一条( z ，y ) 途径和一条( y ，x ) 途径 有向图d 的一个强连通分支是d 的最大诱导强连通子图 定义1 1 5 设d = ( k a ) 是一个有向图，x ，y 是y 的一个二分划，即x u y = v ， xny = 0 记a ( x ，y ) = ( z ，y ) a ：z x ，y y 为d 中从x 发出到y 的弧 集，4 ( x ) = ( g ，z ) a ：9 f z x ，) 为d 中从y 发出到x 的弧集 定义1 1 _ 6 有向图d 被称为是d - 正则的，如果d 中每个顶点的出度和入度都 等于d 下述关于正则有向图的引理是简单但有用的，详细证明可参考文献 8 】 命题1 1 2 【8 】如果d = ( k a ) 是一个正则有向图，x ，y 是v 的一个二分划， 则1 a ( x ，y ) i = f a ( y ) x ) 1 对于文中其它未加定义而被使用的图论记号可参考文献 1 和2 - 第一章预备知识 2 d eb r u i j n 图的基本概念和基本结论 3 d eb r u i j n 图作为一种网络模型 5 1 6 ，它的性质已被广泛研究我们首先给出有向 d eb r u i j n 图的概念如下： 定义1 2 1 有向d eb r u i j n 图，记为b ( d ，n ) ，有顶点集y 和弧集a 其中v = 。1 2 2 - z 。：z ； o ，1 ，- - ，d 1 ) ，i = 1 ，2 ，一，n ) 对z ，y v ，若x = x l x 2 - x 。， 则( z ，y ) a 营y = x 2 x 3 x n z 凡+ 1 ，z 。+ 1 o ，1 ，d 一1 ) 显然b ( d ，佗) 是一个 d 一正则有向图，即z ( d ，礼) 的每个顶点z 的出度d + ( z ) 和入度d 一( z ) 都为d 定义1 2 2 无向d eb r u i j n 图，记为u b ( d ，n ) ，是一个简单无向图，它是通过删 去b ( d ，n ) 中的所有弧的方向并去掉由此产生的多重边和环而得到的 定义1 2 3 有向d eb r u i j n 图b ( d ，几) 中一对有向弧称为是对称的，如果它们有 相同的端点而方向不同它对应u b ( d ，n ) 中的一条边( a b a b ，b a b a ) ，称为奇异 边 定义1 2 4 设g = z l z 2 z 。是b ( d ，n ) 或u b ( d ，扎) 的一个顶点，如果z 1 = 奶一= a b x 2 x 4 ，则称x 为交错点；如果z l = x 2 一= x 。，则称x 为常点 若( z ，y ) 和( y ，茁) 为一对对称弧，以下为方便起见我们也称它们之中的一条弧为 一条对称弧 我们规定u b ( d ，1 ) 是顶点数为d 的完全图记为u b d 为方便读者理解d eb r u i j n 图的定义，我们在下面给出b ( 2 ，3 ) ，u b ( 2 ，3 ) ，的一个 图表示 b ( 2 ，3 ) 图l 他乡入 。八以 通过对d eb r u i j n 图的观察，我们易得下列性质 性质1 2 1 | v ( u b ( d ，n ) ) l = i w ( b ( d ，n ) ) i = d “ 性质1 2 2 对称弧( 奇异边) 的端点必为交错点 性质1 2 3b ( d ，礼) 中的环只出现在常点上 u b ( 2 ，3 ) 4d eb r u 玎n 图的限制边连通度 性质1 2 4b ( d ，, o ( u b ( d ，凡) ) 中恰有砑个交错点，d 个常点，四对对称弧( 四 条奇异边) 性质1 2 5u b ( d ，扎) 中每个常点的度为2 d 一2 ，每个交错点的度为2 d 一1 ，其余 点的度为2 d 而且g b ( d ，2 ) 中只有常点和交错点 3 有关连通性的基本概念和基本结论 多处理机系统的互连网络通常以( 无向或有向) 图为数学模型，这时图的顶点代 表处理机，而一对处理机之间的直接通信联系则用连接这对顶点的边来表示，因此网 络拓扑的性能可以通过图的性质和参数来度量对互连网络性能的一个关键要求是希 望网络的可靠( 容错) 性好，这个要求用图论的术语来说，就是希望图的连通度和边 连通度大首先我们回忆一下图的连通度和边连通的概念 定义1 3 1 设g ( d ) 是无向简单连通图( 强连通有向图) ，k 是g ( d ) 的非空顶 点子集，如果g ( d ) 一v 不( 强) 连通，则称k 是g ( d ) 的顶点割g ( d ) 的连通度记 为“( g ) ( ，c ( d ) ) ，定义为g ( d ) 的最小顶点割的点数 定义1 3 2 设g ( d ) 是无向简单连通图( 强连通有向图) ，f 是g ( d ) 的非空边子 集，如果g ( d ) 一f 不( 强) 连通，则称f 是g ( d ) 的边割a ( d ) 的边连通度记为 a ( g ) ( a ( d ) ) ，定义为g ( d ) 的最小边割的边数一个图a ( d ) 是最大边连通的，如果 a ( a ) = 6 ( g ) ( a ( d ) = 铲( d ) ) 一个最大边连通图g ( d ) 是超级边连通的，如果g ( d ) 中每个阶数为a 的边割孤立度为d ( 铲) 的顶点 不过用连通度和边连通度这两个参数考究系统的可靠性有两个缺陷：其一，这两 个参数不能区别按不同方式移去心个点( 或a 边) 后所产生的不同的连通分支的情 况这说明连通度或边连通度不能反映由于处理机或信关的损坏需造成的系统损坏程 度其二，这两个参数都假定了系统的任何部分都可能损坏这两个参数在处理某些 部分不会同时损坏的网络时不准确在此背景下，图的极大( 边) 连通性、超级( 边) 连通性、限制( 边) 连通度、极大限制( 边) 连通性和超级限制( 边) 连通性的概念先后 被提出f 3 ，4 1 ，它的具体定义如下： 定义1 3 3 设a ( d ) 是无向简单连通图( 强连通有向图) ，f 是g ( d ) 的非空边子 集，如果g ( d ) 一f 不( 强) 连通且g ( d ) 一f 的任一( 强) 连通分支至少有两个点，9 l l l = 弥 f 是g ( d ) 的限制边割a ( o ) 的限制边连通度记为a 。( g ) ( a ( d ) ) ，定义为g ( d ) 的 最小限制边割的边数为方便，也把g ( d ) 的最小限制边割称为o ( d ) 的a 一c u t 定义1 3 4 设g 是一个连通无向图，若a ( g ) = ( g ) 则称g 是极大限制 边连通的其中a ( g ) 为g 的边连通度，( g ) 为g 的最小边度，定义为( g ) = m i n d ( x ) + d ( y ) 2 ：v x y e ( g ) ) ，这里d ( z ) ，d ( ) 分别表示顶点z 和y 的度如 第一章预备知识 5 果图g 的任一a 一c u tf 都只能分离一条孤立边，即f 是某条边的相邻边集，则称 g 是超级限制边连通的 由超级限制边连通的定义，我们容易得到如下性质： 性质1 3 1 若d24 ，那么u b ( d ，1 ) 就是超级限制边连通的 因此在下面若无特别强调，对d eb r u i j n 图我们总是假设n 2 性质1 3 2 若图g 是超级限制边连通的，则它也是极大限制边连通的 但反之不然，例如一个长至少为6 的圈就是极大限制边连通但不是超级限制边连 通的 在文献 2 】的4 6 节可知b ( d ，n ) 有如下性质： 命题1 3 1 【2 】当d 2 ，礼2 时，b ( d ，n ) 的连通度，c ( b ( d ，佗) ) = d 一1 在文献f 9 1 有如下性质： 命题1 3 2 【9 1 设g 是阶至少为4 的连通无向图且不为星图，则a ( g ) 存在且 a ( g ) ! ( g ) f ( g ) 因此除了n = 1 ，d 茎3 的情况，a ( u b ( d ，佗) ) 都存在 命题1 3 3 2 ( m e n g e r 定理) 一个i v l ，c + 1 的图g 是k 连通的当且仅当g 的任意两个相异顶点至少被k 条内部不相交的路所连 第二章有向d eb r u i j n 图的限制边连通度 1 准备工作 s o n e o k at 在f 7 j 中证明了有向d eb r u i j n 图是超级边连通的本文完全确定了有 向d e1 3 r u i j n 图的限制边连通度，并且把有向d eb r u i j n 图是超级边连通的这一结论 作为它的直接推论为证明本章的主要结论，我们先给出几个引理 引理2 1 1 设( ，y ) 是有向d eb r u i j n 图b ( d ，n ) ( d22 ，n 3 或d 3 ，n 2 ) 中任意一条对称弧，则从 盘，) 发出的弧集a + ( z ，) ) 是b ( d ，n ) 的限制边割，且 i a + ( z ，y ) l = 2 d 一2 证明记d = b ( d ，n ) ( d 2 ，礼3 或d 3 ，n 2 ) ，设z = x l z 2 z 。和 y = x 2 x 3 - o n z n + 1 ，其中x l = z 320 5 “= a b 3 3 2x 4x 65 一，且 o ，b o ，1 ，d 一1 ) 下证a + ( 。，g ) ) 是b ( d ，礼) 的限制边割记d 1 = d 【( z ， 】 显然d 1 是强连通的记d 2 = d d 1 ，因为当d 三2 ，n 兰3 或d 3 ，扎2 时有 i d 2 | = i dj i d l i = d ”一2 2 ，所以只需要证明d 2 是强连通的任取u ， v ( d 2 ) 情形1d = 2 由命题1 3 1 知k ( d ) = d 一1 = 1 ，所以由命题1 3 3 知d 中存在一 条( 7 1 , ， ) 一路尸若p 不经过z 和y ，则尸中必有一条( u ， ) 路若p 既经过z 又经过 y ，设( ，z ) a ( p ) ，( ，z ) 4 ( p ) ，则( 加，。) a ( p ) 于是p 【u ，叫 ( ，z ) p z ，w 】是d 2 中的一条( 札，”) 路若p 只过。或y ，不妨设p 经过o ，只需证d 2 中有一条( u ，u ) 一 路下设( w ，x ) a ( p ) ，( 。，z ) a ( p ) ，并设z = x l 。2 茁。，y = x 2 x 3 - 一x n z 卅i ，叫= 。2 2 1 2 2 一x r l x n l ，z = 2 j 2 x 3 - x n 2 9 n - 1 z n z t t ，其中t l = z 3 = x 5 = = 1 , x 2 = 轧= x 6 一= 0 于是可以找到山的另一个外邻点w 。= 2 9 1 2 2 9 9 n - l x 。1 到。的另一个 内邻点z = x 2 x 2 2 3 2 9 n - 1 z 。的一条有向途径p l 如下； ， ， 删_ t 2 x 3 z n 一1 z n l x 2 _ z 3 击n 卅l x1 x 2 x 2 - + - o n l x 2 2 2 z n 一2 3 2 n l _ z 易见p l 经过的点中的坐标要么有x n - l o 。一。在一起要么有x 2 x ：在一起，故p l 不经 过z 和y ，且p l 包含一条不经过z 和y 的有向路b 则p “，训】( 叫，叫) p 2 ( 2 ，z ) p k 口 是d z 中的一条( 钍，口) 一路 情形2d = 3 由命题1 3 1 知k ( d ) = d 一1 = 2 ，所以命题1 3 3 知d 中存在两条 内点不相交的( n ， ) 一路p l 和p 2 若尸l 和p 2 中有一条既不含x 也不含y ，则d 。中必 有一条( ，u ) 一路下设。尸1 ，y 尸2 ，并设( t 3 ，茁) p 1 ，( g ，z ) p 2 ，则( ，z ) a ( d 2 ) 于是p l 札，w 1 ( 叭z ) p 2 k ”】是d 2 中的一条( “， ) 一路 情形3d24 由命题1 3 1 知k ( d ) = d 一1 3 ，所以命题1 3 3 知d 中至少存 在3 条内点不相交的( 珏， ) 一路，因此伤中必包含一条( “， ) 一路 由情形1 ，情形2 和情形3 知，让和u 在d 2 中是强连通的又由“，u 的任意性 知，d 2 是强连通的故a + ( z ，y ) ) 是b ( d ，n ) 的限制边割，显然1 a + ( z ，) ) 1 = 2 d 一2 引理得证 口 第二章有向d eb r u i j n 图的限制边连通度 7 引理2 1 2 设z ，和( 让， ) 是b ( d ，n ) ( d 三2 ，n 3 ) 中任意两条无公共端点的 弧且( z ，) 是一条对称弧，设o = a b a b ，y = b a b a ，( o 6 ) ；u = “1 扎2 u 。，u = “2 “3 u 。“。+ l ，若u 2 ，u 3 ，“。不全相等，则b ( d ，n ) 中存在( 2 d 一2 ) 条弧不重的从 ，g 到 u ， 的有向路 证明先考虑n 为偶数且u 2 b 时的情形记d = b ( d ，n ) ，考虑从 z ，”) 到 f u ，” 的有向途径眦，w 2 ，w d 一1 ，孔，马，乃一如下； w i ：z = a b a bb _ b a h b 训t n b b w i u l _ b b w i t q “2 _ _ + t i i i u l 。u n l _ u l u 2 u n = u 乃：v = b a b a a _ a b a 。o ，_ 妇a t j u 2 一o a t j u 2 u 3 _ - t j u 2 u n _ u 2 1 l 3 “n + l = u 其中w i o ，1 ，d 一1 ) 一 n ) 且1 0 1 ，叫2 ，叫d 一1 各不相同，白 0 ，1 ，d 一 1 ) 一 毋且t l ，t 2 ，妇一1 各不相同现在证明上面选取的( 2 d 一2 ) 条从 z ，) 到 f u ，口，的有向途径是弧不重的 假若存在i 和j 使得眠和有重弧，设z 为眠和”，第一条重弧的尾设 慨( 。，z ) 的部分长为k ，( z ，z ) 的部分长为t ，0 k ，tsn ，即z 可由z 沿m 通过 k 步，沿毗通过t 步到达由t o i w j 知k t ，不妨设k t 情形10 冬 tsn 一1 若k ，t 奇偶性相同，不妨设，t 同为偶数，此时 z = a b a b w i u l u 一l = 0 6 a b w j u l u ，则有w j = o ，矛盾若k ，t 奇偶性不 同，不妨设k 为偶数，此时z = n 6 t l j i u l u 女一l = b a w j u l “，则有o = b ， 矛盾 情形20 七 t = 礼若k 为偶数，此时z = 0 6 圳。札l u k 一1 = 叫，扎l 2 u 。一1 ， 则训，= a ，矛盾若k 为奇数且k n - - 1 ，此时z = b a 训i u l 札女一l = w j u l u 2 。_ 1 则有“2 = 6 ，矛盾若k = 礼一1 ，此时z = b w | f u l u n 一2 = 1 u 2 “舢1 则有u 2 = u 3 一= u n l 】但( b w i u l - u ，l 一2 ，w i u l u 2 - t - u 一1 ) ( 7 j i “l u 2 u n l ，札1 “2 u n ) ， 否则u 2 = u 3 一= u 。，矛盾 同理可证正和乃，0 i ，j 扎也无重弧 假若存在i 和j 使得眦和乃有重弧，且设z 为暇和码第一条重弧的尾设 眦( 。，z ) 的部分长为k , t ，( z ，z ) 的部分长为t ，0 ，t 茎礼，即z 可由z 沿暇通过 步，沿乃通过t 步到达易见，k t 情形10 k t 墨礼一1 若k ，t 奇偶性相同，不妨设，t 同为偶数，此时 z = a b b w i u l u 女一l = b a a t j u 2 u ，则有o = b ，矛盾若女，t 奇偶性不同，不 妨设为偶数，t 为奇数，此时z = a b a b w u 1 一l = a b b a t j u 2 u t ，则有 t ，= b ，矛盾同理t 为偶数，k 为奇数时也有t j = b ，矛盾 情形20 t = n 若为奇数，此时。= 6 。6 叫。u 1 珏k l = t j u 2 u 3 u 。， 则有t j = b ，矛盾若k 为偶数，此时z = 0 6 b w | f u l u k l = t j u 2 u 3 u n ，则有 “2 = b ，矛盾 情形30 t 2 d 一2 ，所以d l 或d 2 中至少有一对对称弧不妨设( z ，y ) 是d l 的一条对称弧，且存在d z 的一条弧( “，”) ， 使得点札= u l u 2 札口= u 2 u 3 札。其中乱2 ，3 ，“。不全相等，否则d 2 中的 点只有以下三种形式a a a ，? z l a a ，a o 。+ l ，其中a 0 ，1 ，d 一1 ；让1 ，n + 1 o ，1 ，d 一1 ) 一 血) 易见此时d 2 不强连通，矛盾故由引理2 1 2 知存在( 2 d 一2 ) 条弧不重的从 z ，) 到 “， ) 的有向路，且每条有向路至少有一弧在b 中，所以 l b l 2 d 一2 情形1 2d = 3 ，扎3 若d 1 或d 2 包含至少一条对称弧，则可按情形1 1 的方法类 似讨论得l b l 2 d 一2 若d 1 和d 2 都不包含对称弧，由于d 中有锑= 3 对对称弧，考 在2祷舭 ，、 1 i 哪似 日 j 22 理定 1 0d eb i u j j n 图的限制边连通度 虑n 为偶数的情形( 奇数情形可类似讨论) ，不妨设弧( 1 0 1 0 ，0 1 0 1 ) ，( 2 0 2 0 ，0 2 0 2 ) ，( 1 2 1 2 ，2 1 2 1 ) b 并设点1 0 1 0 1 0 ，点0 1 0 1 0 1 v 2 则从点 1 0 1 0 1 0 到点0 1 0 1 0 1 的另一条有向路p 如下： 1 0 1 0 1 0 - 0 1 0 1 0 w _ 1 0 1 0 w 0 _ 0 1 0 w 0 1 _ - - _ w 0 1 0 1 0 _ 0 1 0 0 1 其中圳= 0 故p 中必有一弧属于b ，另外有弧( 1 0 1 0 ，0 1 0 1 ) ，( 2 0 2 0 ，0 2 0 2 ) ( 1 2 1 2 ，2 l 2 1 ) 岳a ( p ) ，故l b l 4 = 2 d 一2 情形1 3d = 4 ，讥3 若d 1 或d 2 包含至少一条对称弧，则可按情形1 1 的方 法类似讨论得i b i 2 d 一2 若d l 和仍都不包含对称弧，由于d 中有四= 6 对对 称弧，则j b i 6 = 2 d 一2 情形2d 3 ，n = 2 。 情形2 1d 4 ，似= 2 由于d 中有四对对称弧，且四 2 d 一2 ，所以d l 或d 2 中至少有一对对称弧不妨设( o ，g ) 是d 。的一条对称弧，使得z = a b ，y = b a 并且 存在d 2 的一条弧( u ，u ) ，使得点u = 1 u 2 其中u l a 且u l b 且u l u 2 否则d 2 中的点全是形如点。“。，7 a 1 b ，u l u - 的点，则此时d 2 不强连通故我们可选取从扛，) 到 u ，u 的( 2 d 一2 ) 条弧不重的有向途径啊，w j ，w j “孔，疋，乃一1 如下： 其中毗f 0 ，1 ，d 一1 一 o ) 且w l ，w 2 ，”d 一1 各不相同，t ， o ，1 ，一，d 一 1 ) 一 6 ) 且t l ，2 ，t d 一1 各不相同容易证明上面选取的( 2 d 一2 ) 条有向途径m ，w ，2 ， ，“丑，乃，乃是弧不重的由命题1 1 1 知每条有向途径必包含一条从 z ， 到 让，” 的有向路，且每条有向路至少有一弧在口中，故i b i 2 d 一2 情形2 2d = 3 ，n = 2 若d l 或d 2 包含至少一条对称弧，则可按情形21 的方 法类似讨论得i b i 2 d 一2 若d l 和d 2 都不包含对称弧，由于d 中有q = 3 对 对称弧，不妨设弧( 0 1 ，1 0 ) ，( 0 2 ，2 0 ) ，( 1 2 ，2 1 ) b ，并设点0 2 h ，点2 0 k 此时 p ：0 2 _ 2 2 叶2 0 是点0 2 到点2 0 的另一条有向路，故尸中必有一弧属于b ，且有 弧( 0 1 ，l o ) ，( 0 2 ，2 0 ) ，( 1 2 ，2 1 ) 隹a ( 尸) ，所以i b l 4 = 2 d 一2 情形2 3d = 4 ，礼= 2 若d 1 或d 2 包含至少一条对称弧，则可按情形21 的方 法类似讨论得l b l 2 d 一2 若d l 和d 2 都不包含对称弧，由于d 中有q = 3 对对 称弧，则i b l 6 = 2 d 2 情形3d = 2 ，n23 若d 1 或d 2 包含至少一条对称弧，则可按情形l ，1 的方法 类似讨论得l b f 兰2 d 一2 若d 和d z 都不包含对称弧，考虑礼为偶数的情形( 奇数 情形可类似讨论) ，不妨设弧( 1 0 1 0 1 0 ，0 1 0 1 0 1 ) b ，并设点1 0 1 0 1 0ek ，点 0 1 0 0 l 则从点1 0 1 0 1 0 h 到点0 1 0 1 0 1 的另一条有向路p 如下： 第二章有向d eb r o i j n 图的限制边连通度 1 1 其中w = 0 故p 中必有一弧属于b ，且有弧( 1 0 1 0 1 0 ，0 1 0 1 0 1 ) 岳a ( p ) 所以 i b i 兰2 = 2 d 一2 综上有l b l 2 d 2 ，故= i b i 2 d 一2 定理得证口 下面这个结果是定理的直接推论： 推论 7 1 有向d eb r u i j n 图b ( d ，几) ( d 3 ，n 2 或d = 2 ，n 三3 ) 是超级边连通的 第三章无向d eb r u i j n 图的超级限制边连通性 1 相关结论 在 9 】中m i nl u ，j u n m i n gx u 和y i n g m e if a n 指出： 命题3 1 1 9 1 当d 2 ，n 1 时，无向d eb r u i j n 图u b ( d ，n ) 有如下结果 l