（应用数学专业论文）图的超级限制边连通性.pdf

摘要 多处理机系统的互连网络拓扑通常以( 有向或无向) 图为数学模型设 g 是无向简单连通图，f 是g 的一个边割，如果g f 不含孤立点，则称 f 是g 的一个限制边割最小限制边割所含的边数称为g 的限制边连通 度限制边连通度作为边连通度的推广，是计算机互连网络可靠性的一个 重要度量超级限制边连通性是比限制边连通度更精确的一个网络可靠性 指标一个图是超级限制边连通的，如果它的任一极小限制边割都孤立一 条有最小边度的边本文主要研究了几类图的超级限制边连通性 在第一章第一节我们给出本文将用到的图论方面的主要的术语、记号 在第二节我们介绍了限制边连通度方面的基本概念和基本结论 本文第二章主要研究几类直径为2 的图的超级限制边连通性在第一 节我们给出后文将要用到的几个简单事实，并简略总结了直径为2 的图连 通性方面的已有结论在第二节，直径为2 的图为超级限制边连通的几个 充分条件被给出，具体是： ( 1 ) 设g 是阶至少为4 的一个图且对g 中的任意两个不相邻顶点u 和。，若 u 都不在三角形中，有i n ( u ) n ( ) i23 ，否则，有 n ( ) l 4 ，若g 不属于一类特殊图，则g 是超级限制边连通的 ( 2 ) 设g 是一个阶至少为9 的图若它满足最小度5 3 ，直径d = 2 且不包 含三角形，那么g 是超级限制边连通的 ( 3 ) 设g 是v ( 1 0 ) 阶图，若对它的任意两个相邻顶点z 和，有l ( 茁) n ( g ) l 1 ；对它的任意两个不相邻顶点u 和v ，有d ( u ) + d ( v ) ”一1 ，则g 是超级限 制边连通的 在第三节我们指出这些结论从不同的角度改进了一些已有的结果，并用例 子说明这些结论是相互独立的 k a u t z 图是重要的k a u t z 网络的拓扑结构，曾受到广泛的关注。在本文 第三章我们先给出k a u t z 图的定义和无向k a u t z 图连通性方面已有的一些 结果在第二节我们引进正常外途径的概念，得到一些有用的结果在第 三节我们证明当d 3 ，n 2 时，无向k a u t z 图u k ( d ，佗) 是超级限制边连通 的利用该结果和其它一些结论，最后我们对所有无向k a u t z 图的超级限 制边连通性的情况作一个总结 关键词：网络；限制边连通度；超级限制边连通性；直径；无向k a u t z 图 中图分类号：0 1 5 7 5 a bs t r a c t g r a p h sa r eo f t e l 2a sm o d e i 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 t i o nn e t w o r k s l e t gb 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 n e d g ec u ts u c ht h a tg fh a si i 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 gi t y i st h em i n i m u i ac a r d i n a s 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 、，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 , i sa ni m p o r t a n tm e a s u r eo f f a u l t t o l e r a n c ef o ri n t e r c o n n e c t i o nn e t w o r k st h a nt 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 y t h e 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 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 l 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 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 yf o rs e v e r a ig r a p h c l a s s e 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 y o n 口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 dr e s u l t so nt h es u p e rr e s t r i c t e d e d g ec o n n e c t i v i t y c h a p t e r2d e a l sw i t ht h es 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 yf o rg r a p h so fd i a m e t e r 2 i ns e c t i o n2 1w ep r o v i d es e v e r 越s i m p l e b u tv e r yu s e f u lf a c t sa n ds u m m a r i z et h e o b t a l n e dr e s u l t so nc o n n e c t i v i t yo fg r a p h so fd i a m e t e r2i ns e c t i o n2 2 s o m es u 伍c l e n t c o n d i t i o n sf o rs 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 yi ng r a p h so fd i a m e t e r2a r e 舀y e na s f 0 1 l o w s ( 1 ) l e tgb eag r a p hw i t hi y ( g ) i 4 ，i fl g ( i s ) n ) l 3f o ra l lp a i r s 乱，7 3 o f n o n a d j a c e n tv e r t i c e ss u c ht h a tn e i t h e r 钍n o rvl i eo nat r i a n g l e ，a n di ( 乱) nn ( v ) i 4 f o ra l lp a i r su ，uo fn o n a d j a c e n tv e r t i c e sw i t ht h ep r o p e r t yt h a t 乱o rva r eo nat r i a n g l e ， t h e ngi sas 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 hu n l e s sgb e l o n g st oa ne s p i a i g r a p h c l a s s ( 2 ) l e tag r a p hg c o n t a i nn oc y c l eo fl e n g t h3a n ds a t i s f yl y ( g ) l 9 ，a ( c ) 3 ，d ( c ) = 2 t h e ngi sas 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 h ( 3 ) l e tgb eag r a p hw i t hi y ( g ) 1 1 0 i fi n ( x ) n ( 可) l 茎1f o ra n ye d g ex y ，a n d d ( i s ) + d ( v ) l y ( g ) l 一1f o ra up a i r s “，uo fn o n a d j a c e n tv e r t i c e s ，t h e ng i sas u p e r r e s t r i c t e de d 眢ec o n n e c t e dg r a p h i ns e c t i o n2 3 w ef i r s tp o i n to u tt h a tt h ea b o v er e s u l t si m p r o v es o m er e s u l t sw h i c h h a v eb e e ng i v e nb yo t h e r s ，a n dt h e np r e s e n te x a m p l e sw h i c hs h o wt h a tt h ea b o v e r e s u l t sa r ei n d e p e n d e n te a c ho t h e r k a u t zg r a p h ，t h et o p o l o g yo fk a u t z n e t w o r k ，i sac l a s so fi m p o r t a n t 铲a p h s ，w h i c h h a sb e e nw i d e l yu s e di nt h ed e s i g na 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 s i nc h a p - t e r3w es t u d yt h es 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 yo fk a u t zu n d i r e c t e dg r a p h s i n s e c t i o n3 1w ei n t r o d u c et h ed e f i n i t i o no fk a u t zu n d i r e c t e dg r a p h sa n dr e s u l t sc o n c e r n - i n gt 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 fk a u t zu n d i r e c t e dg r a p h ss o m eu s e f u lr e s u l t s a r eo b t a i n e db yi n t r o d u c i n gt h ec o n c e p to fn o m a r lo u tw a l k si ns e c t i o n3 2 f i n a l l y , w e c o n c l u d et h a tk a u t zu n d i r e c t e dg r a p h su k ( d ，n ) i sas u p e rr e s t r i c t e de d g ec o n n e c t e d g r a p hf o rd 3 ，扎2 c o m b i n i n gt h i sw i t ho t h e rr e s u l t s ，t 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 yo fa l lk a u t zu n d i r e c t e dg r a p h sa r ea s c e r t 面n e d k e y w 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 e dg r a p h s ；d i a m e t e r ；k a u t zu n d i r e c t e dg r a p h s 引言 多处理机系统的互连网络通常以( 无向或有向) 图为数学模型，这时图的顶点代 表处理机，而一对处理机之间的直接通信联系则用连接这对顶点的边来表示，因此网 络拓扑的性能可以通过图的性质和参数来度量对互连网络性能的一个关键要求是希 望网络的可靠( 容错) 性好，这个要求用图论的术语来说，就是希望图的连通度和边连 通度大不过用连通度和边连通度这两个参数考究系统的可靠性有两个缺陷：其一， 这两个参数不能区别按不同方式移去一个点( 或a 边) 后所产生的不同的连通分支的 情况这说明连通度或边连通度不能反映由于处理机或信关的损坏而造成的系统损坏 程度其二，这两个参数都假定了系统的任何部分都可能损坏这两个参数在处理某 些部分不会同时损坏的网络时不准确在此背景下，图的极大( 边) 连通性、超级( 边) 连通隆、限制( 边) 连通度、极大限制( 边) 连通性和超级限和( 边) 连通性的概念先后 被提出 2 - 4 1 直径为1 的图就是完全图，有最好的连通性由此人们猜测直径为2 的图也有较 好的连通性，并在这方面作了许多工作特别是自p l e s n i k 9 】证明直径为2 的图是极 大边连通的之后，直径为2 的图的超级边连通性、极大限制边连通性和超级限制边连 通性被广泛研究保证图具有极大或超级边连通性的o r e 型充分条件由l e s n i a k i s l 给 出1 9 9 2 年，f i o l l 6 l 给出直径为2 的图为超级边连通的另一个充分条件，王应前和 李乔【7 在1 9 9 9 年证明这个条件是还是必要的。自此之后，人们把注意力转移到( 1 ) 给出直径为2 的图是极大限制边连通的特征刻画( 2 ) 给出直径为2 的极大限制边连 通图是超级限制边连通的特征刻画这两个问题目前都还没被解决，这其间文献【7 给出了图是极大限制边连通的一个o r e 型充分条件，文献1 10 给出直径为2 的图为 极大限制边连通的几个充分条件文献f 1 1 1 给出直径为2 的图为超级限制边连通的 一个充分条件，文献【8 1 给出了图是超级限制边连通的一个o r e 型充分条件， 互连网络拓扑的选择是多计算机系统结构设计的一个关键问题在设计互连网络 时，一般要考虑通信延迟、路由算法、顶点的度、容皆陛、可扩展性、其它拓扑的可 嵌入性以及v l s i 布线等方面的要求这些要求本身蕴涵着矛盾，能在这些矛盾的要 求之间取得较好的平衡并适用于顶点数目超过几千的真正大型下一代多计算机系统 的互连网络之一是k a u t z 网络i t 2 , 1 3 1 其数学模型k a u t z 图的性质，尤其是一些连通 性，由于它对应网络的容错性而被广泛研究 在文f 1 8 中无向k a u t z 图的超级边连通性被讨论文 2 0 - 2 1 确定一类特殊的无 向k a u t z 图的极大限制边连通性，并给出无向k a u t z 图的限制边连通度的一个取值 区间文f 1 9 确定了一类非常特殊的无向k a u t z 图的超级限制边连通性目前，我 们需要进一步确定无向k a u t z 图的限制边连通度，全面解决无向k a u t z 图的超级限 制边连通性， 第一章预备知识 1 1 图论的有关术语、符号 本节只考虑有限无向简单图设g = ( v e ) 是一个无向简单图，其中v = y ( g ) ，e = e ( c ) 分别表示图g 的顶点集和边集若边e 的端点为u ，v ，我们用 ( u ，口) ( 或u ”) 表示边e 专用”= v ( g ) 表示g 的顶点数，e = ( g ) 表示g 的 边数即v ( g ) = i v ( c ) 1 ，( g ) = l e ( g ) l 若珏，v v ，e = i t v e ，则说札和口0 芷g 中) 相邻，又说e 与“相关联，也说e 饱和u ，或“为e 所饱和设f 是图g 的一个边子集，a 是图g 的一个顶点子集 我们用f ( u ) 表示在f 中与顶点u 相关联的边所成的边子集，当 f ( u ) i = 1 时，称“ 是f 单饱和的如果对每一个茁a v ，都有l f ( z ) j 1 ，则称f 饱和a 顶点t ，的度d ( v ) = d a ( ) 是指g 中与口关联的边的数目定义g 中边e = u 的度为d ( e ) = d ( u ) + d ( v ) 一2 分别用5 = j ( g ) 和f = ( g ) 表示图g 的最小( 顶点) 度和最小边度 若在g 中顶点u 和”是连通的，则“和v 之间的距离d ( u ，v ) 是g 中最短( u ，v ) 路的长g 的直径d = d ( g ) 是指g 的所有两个顶点之间的最大距离g 的围长 g = 9 ( g ) 是指g 中最短圈的长；若g 没有圈，则定义g 的围长为无穷大g 中所 有与钍相邻的点所成的集合n ( u ) = 舀( 珏) 叫做的邻域设日是g 的一个子图， 我们也记n h ( u ) = g ( u ) ny ( 丑) ，d h ( u ) = i n h ( 钍) 对g 的两个不相交顶点非空子集a ，b ，我们用陋，矧表示g 中一端点在a 中 另一端点在b 中的所有边所成的集合所谓g 的边割是指形为盼s 】的e 的子集， 其中s 是矿的非空真子集，可= v s 一个k 边割是指有k 个元素的边割g 的 边连通度a 定义为g 的所有k 边割中最小的k 称两个图g 和丑是同构的( 记作g 竺矗) ，如果存在一个一一映射9 ：v ( c ) 一 y ( 日) ，使得z v e ( g ) 当且仅当日( u ) 日( o ) e ( 日) 为方便，本文有时也把同构的两 个图看成是同一个图我们也称图g 的长为3 的圈为g 的一个三角形每一对不同 的顶点都有一条边相连的简单图称为完全图，在同构意义下，v 个顶点的完全图只 有一个，用匮，表示所谓偶图( 或二部图) 是指一个图，它的顶点集可以分解为两个 ( 非空) 子集x 和y ，使得每条边都有一个端点在x 中，另- j 个端点在y 中；这样一 种二分类( x ，y ) 称为图的一个二分类完全偶图是具有二分类( x ，y ) 的简单偶图， 其中x 的每个顶点都与l ，的每个顶点相连；若i x i = m 而i y i = n ，则这样的图记 作。 设尼是g 的一个生成子图，如果对每个z v 都有d f 2 ( o ) = 2 ，则称f 2 为g 的一个2 因子2 蜀。表示m 阶完全图墨。的两个顶点不交的拷贝设图日，的顶 点集都是矿但e ( h ) n e ( k ) = 0 ，则h u k 表示点集为y ，边集为e ( h ) u e ( k ) 的 图 简单图g 和日的笛卡儿积图g h 是指具有顶点集v ( c ) xv ( h ) 的简单 预备知识 3 图，它的顶点( “， ) 和另一个顶点( 让，u 7 ) 相邻当且仅当u = 7 ，”u z ( n ) 或者 = u ，】u u 7 e ( g ) 对于文中其它未加定义而被使用的图论术语和记号可参阅文献【1 1 2 连通性方面的基本概念和基本结论 多处理机系统的互连网络通常以图为数学模型在研究网络的可靠性时，人们常 考虑m o o r - s h a n n a n 模型【3 】：它假定节点不发生故障，而边以相同概率独立地发生故 障设g 是一个m o o r s h a n n a n 模型，它的边数为e ，边发生故障的概率为p ，用弛 表示阶为i 的边割的数目那么，g 的可靠多项式可以表示为 s r e l ( c ；p ) = 1 一帆( 1 一p ) 6 _ i = a p r o v a n 等人在 2 2 中证明：确定所有的m i 是n p 一困难的 容易知道，当p 足够小时，”酞矿( 1 一坊。3 决定了r e l ( g ；力的大小，所以我们 希望网络设计使得“) 、尽可能大而且m a 尽可能小”为了刻画“入尽可能大”，又注 意到边连通度a 不大于最小度d ，人们提出极大边连通性的概念为了刻画“a 尽可 能大而且m 尽可能小”，人们提出超级边连通性的概念 2 , 1 r , 2 a l 定义12 1 称一个连通无向图g 是极大边连通图，如果a ( g ) = 6 ( g ) 如果图g 的任最小边割都只能分离出一个度为d 的点，即图g 的任一最小边割都是某个度 为6 的点的关联边集，则称此图是超级边连通的 显然若图g 是超级边连通的，则它必是极大边连通图，但反之不然例如图w 6 ( 见 图1 ) 是极大边连通图但不是超级边连通的 图1 ：w 6 图 r1 1 且对g 的任意一对不相邻顶点。，y ，都有 d ( x ) + d ( y ) 且g k 。, 2 k 2 ，则g 是超级边连通的 ( 3 ) f 5 j 若对g 的任意对不相邻顶点z ，y ，都有d ( x ) + d ( y ) v + 1 ，则g 是超级边连 通的 ( 4 直径为2 且最小顶点度d 1 的图g 是超级边连通的充分必要条件是：g 的 导出子图g m 没有d 阶完全子图，这里的m 是g 中顶点度为6 的顶点集 6 图的超级限制边连通性 ( 5 ) r t l 设图g 的顶点数为( 4 ) ，若对g 的任意一对不相邻顶点x ，y ，都有d ( x ) + d ( y ) y + 1 ，则g 是极大限制边连通的 ( 6 ) f 7 】设直径d = 2 ，6 3 的图g 中不含有三角形，则g 是极大限制边连通的 ( 7 ) c 1 0 设g 是阶至少为4 的一个图对g 中的任意两个不相邻顶点和v ，若乱，u 都 不在某个三角形中，有l n ( u ) n ( 口) i 2 ，否则，有j ( 乱) n ( ) l 3 ，则g 是极大 限制边连通的 ( 8 ) s l 若对图g 的任意对不相邻顶点，y ，都有d ( z ) + d ( y ) 2 + 2 ，则g 是超级限 制边连通的，除非p 为偶数且g = 2 k ，2l jf 2 其中f 2 是g 的一个2 因子 ( 9 ) 【1 1 设图g 的顶点数为( 8 ) ，若图g 中不含有三角形且对g 的任意一对不相邻 顶点x ，y ，都有d ( x ) + d ( y ) ”一1 ，则g 是超级限制边连通的 2 2 主要结果 本节我们将介绍几个直径为2 的图是超级限制边连通的充分条件 定理2 2 1 设g 是阶至少为4 的一个图，对g 中的任意两个不相邻顶点和v ， 若乱，v 都不在三角形中，有i 心) n ( ) 3 ，否则，有l ( “) n ( w ) l 4 ，则g 是 超级限制边连通的，除非为偶数且g = 2 k , 2uf 2 其中f 2 是g 的一个2 因子 证明由定理2 1 ，2 ( 7 ) 知图g 是极大限制边连通的，即a 。( g ) = ( g ) 假设g 满足对任意的不相邻顶点对咄u ，若地d 都不在三角形中，有l n ( u ) n ( ”) i23 ，否 则，有i ( 让) n ( ”) l 4 若g 不是超级限制边连通的，那么存在一个最小限制边割 f 使得i x i 3 ，l y i 3 断言1 ：x = x o 和y = y o 由性质2 1 2 可知g 的直径至多为2 再根据陛质2 1 ，3 ，不失股陛，可设x = x o 若y y 。，那么y 中有f 的不饱和顶点 ，任取茹x ，由题设可知l ( o ) n ) l2 3 ，因此l f ( ) i 3 对任意的点y g 。( z ) ，考虑边o v ，有 ；f ( 茁) j + l f ( 可) l + 3 ( 1 x l 一2 ) i f i = a = d ( 上) + d ( y ) 一2 = i f ( 。) l + i f ) l + i n g 。( 。) 一 可 + n c ，( 笋) 一 z i f ( 。) l + l f ( ) l + 2 ( i x l 一2 ) 所以可得i x l 2 ，矛盾该断言得证， 断言2 ：x o = 0 或砷= d 否则，存在。x o ，y r o 若。与y 不相邻，由题设，l ( z ) n ( 口) i 三= 3 与z ，y 的选取矛盾所以x 中每一点都与岬中每一点相邻此时，只能是砖i = 扛 ，砰= 订，x y e 对任意的点“v g i ( z ) ，考虑边舭，有 sd ( z ) + d ( 乱) 2 = l f ) i + l f ) l + f g 。( z ) 一( 乱 l + l g 。( 世) 一 。) 直径为2 的图的超级限制边连通性 l f ( z ) 1 + i f ( v ) l + 2 l x 一 z ，u ) l l f ( z ) i + i f ( y ) i +i f ( w ) w e x 一扣“) = i f ( x o ) i = f = 入= 7 所以x 一 置“) = 。( z ) 一( “ = n o 。( i t , ) 一扛) = n o ，( 功n n a 。( “) 由“的任意 性知g t 是一个完全图，且对任意的”x 一 z ) ，l f ( 叫) i = 2 同理可得g 2 是一 个完全图，且对任意的凹y 一 讣，i ，) j = 2 因此i x l = f yj = ；，进一步， v 一1 = l f i = sd ( 嚣) + d ( y ) 一2 = l x + i y i 一2 = v 一2 ，矛盾 根据这个断言，不失一般性，我们可设x ? = d 断言3 ：x = ，础 否则，存在z x ，使得j f ( 。) j 3 ，若存在边 e ( a z ) ，使得让，口墨我们 有， 茎d ( 札) + d ( ) 一2 = l f ( 乱) + l f ( 口) i + i g 。( u ) 一 甜) l + i n a 。( 口) 一 乱) l f ( u ) i + l f 扣) l + 2 i x 一 u ，u ) l j ，( ”) + f f ( ) i + l f ( 甜) x 一“，u ) = j f ( x o ) j = 】fj = a 。= f 矛盾因此g 1 是以。为心的星图，且对任意的“x 一 z ) ，1 f ( 乱) l = 2 显然 d ( ) = 3 ，所以有 f f ( 。) f + 2 ( i x f 1 ) = d ( z ) 十d ( 乱) 一2 = d ( 。) + 1 = f ( z ) f + ( i x l 一1 ) + 1 由此可得】x is2 ，矛盾断言得证 断言4 ：g 1 为完全图 对任意的 l , l e ( a 1 ) ，有 d ( u ) + d ( v ) 一2 = l f ( 乱) l + i f ) + i n g ，( “) 一 i + l 0 。( ) 一 钆 l f ( u ) j + l f ( ”) i + z l x 一 u ，”) j = i f ( “) i + l f 扣) 1 + f1 f ( 卸) 1 w e x - - a ，口) = l f ( x o ) l = i f l = = 所以所以x 一 u ， ) = g 。( u ) 一 ”) = g 。( v ) 一 u ) = g 。( 乱) n n a ，( ”) 由伽的任 意性，知g t 为完全图 断言5 ：砰= 0 否则，取可y o 在x 中任取与y 不相邻的顶点z 因为g 1 为完全图，所以z 在某个三角形中，由题设，i n ( x ) n ( g ) i 4 ，与z x o ：y 砰矛盾 8 图的超级限制边连通性 同理，我们有y = 聊且g 2 为完全图所以为偶数且g = 2 k , 2 uf 2 口 显然有如下推论： 推论2 21 设g 是阶至少为4 的一个图若对g 中的任意两个不相邻顶点k 和 v ，有| ( u ) n ( ) l24 ，则g 是超级限制边连通的，除非为偶数且g = 2 匾，2 u 局 在2 6 1 中王应前和李乔给出了下面的定理：如果d 3 且d g 一2 ，那么g 是 极大限制边连通的并猜测：除了w 8 图( 在图2 中给出) ，所有满足6 3 ，d 9 2 的图都是超级限制边连通的我们指出这个猜测是错的，图w j 4 ( 见图3 ) 就是一个反 例不过我们证明满足5 3 ，dsg 一2 的非w j 图g ，若还能保证它的每个最小限制 边割都饱和x 或y ，则g 是超级限制边连通的 图3 ：w h 图 定理2 2 2 设图g 满足6 ( g ) 3 ，d ( g ) g ( a ) 一2 ，且不为w 8 图，f 是g 的 任意一个最小限制边割，若x = x o ，则i x l = 2 或| y l = 2 证明根据问 2 6 的主要定理，已知g 是极大限制边连通的，即a = 根据 定理2 1 1 ，完全图g 是超级限制边连通的，因此当d = l 时本定理成立下面考虑 d 2 的情况因为d 曼g 一2 ，此时我们有g 4 ，即g 不包含长为3 的圈我们用反 证法完成证明假设g f 的两个连通分支g l ，g 2 的顶点数都至少为3 由x = x o 知对x 中的任意一个顶点茹，都有i f ( z ) l21 根据j x l 3 和g ，的连通性可知g ， 中存在边对任意的e = x y e ( g 1 ) ，有 sd ( e ) = a ( x ) + d ( y ) 一2 = 【f ( z ) l + l f ( ) i + i n g 。( z ) 一 可) + n c 。( y ) 一 z i = j f ( 。) l + i f b ) i + l n c 。( z ) u g ：( y ) 一 z ，掣) l f f ( 茁) j + f f ) j + l f ( g ，如) u g ，( ) 一 z ，) ) i = l f ( g 。( z ) u n g 。( g ) ) j j f = a = ( 1 ) 所以x = n c 。( z ) u _ ? v a 。( ) 由g 不包含三角形知n c 。( x ) n n a 。( y ) = 0 且e ( g n g 。( 。) ) = 0 ，e ( g n g 。( y ) ) ：0 由( 1 ) 式还可知，对任意的乜音，( z ) un a 。( y ) 一 z ，) = x 一忙，订，有1 f ( u ) l = 1 因为l x 3 ，不失一般性，可设g 。( 3 7 ) ) d ， 直径为2 的图的超级限制边连通性 9 任取y g 。( z ) 一 口) ，同理考虑边z 知j f ( ) j = 1 且x = n a 。( x ) u g 。( 口) ， g 。( z ) n g 。( g 。) = 0 所以g 。( y ) = g 。( 。) 如果g 。( ) = h ，缗台l r ( y ) i = l 知d ( y ) = 2 ，与6 3 矛盾所以1 n a 。( ) 1 2 ，则存在经过顶点z ，y ，y 长为4 的圈， 此时只能是g = 4 由d 9 2 知d = 2 任取z 。n c 。( ) 一 z ) ，同理考虑边x y 知| f ( 。) i = 1 所以，对任意的x ，有j f ( u ) j = 1 还可知岛( z ) = 岛( z ) 所 以g 1 是以v g 。( o ) 和g ，( ) 为二分划的完全二部图，且i g 。( z ) l 2 ，i n a ，( 可) l 2 记a l = n a 。( 9 ) ，a 2 = 舀，( z ) ，c 1 = n a 2 ( a 1 ) ，岛= d ，g 。( a 2 ) 显然g 1n 岛= 0 ，y o = a luq 此时，y = y o 否则，任取w y y o 由于d = 2 ，且对任意的 x ， 1 f ( u ) l = 1 ，考虑叫与x 中各点的距离知w 与g 中各点都相邻，i = 1 ，2 ，则 e ( c o ) = d 此时，l c l l = l ，否则，设y l ，y 2 是a 中不同的两点，则y l 到n a 。( y 2 ) 中点的距离至少为3 ，矛盾同理，i 伤i = 1 此时，因为d ( 叫) 3 ，所以i y y o l 2 且存在w y y o ，使得w w e 由甜的任意性知甜也和g ，q 中各点相邻， 那么存在经过w ， 。的长为3 的圈，矛盾所以y = y o 根据y = y o 同理知g 2 是一个完全二部图，设b l ，岛是它的二分划，则l b l l 2 ，l b 2 2 且对任意的y y ，l f ( 可) l = 1 所以l x l = 1 y i = 不失般性，设f a t f = m i n i a f ，f a 2 1 ，f b l f ，f 岛f ) ，f 毋f f 岛f 根据f a + f a 2 f = i b i i + i b 2 1 ，则有i a l i i b l l i b 2 i i a 2 i 若l a l l l a 2 i ，则存在“a 2 ，v b 2 ，使得 u e 则sd ( u v ) = d ( “) + d ( u ) 一2 = i a i i + i b l i = i a i + i a 2 i ，所以l b l l = i 4 2 ， 所以i b i = l b 2 卜= i a 。| ，与i a - 1 l a 2 l 矛盾，所以l a l l = b 1 i = l b 2 l = l a 2 i 若 i a l f 3 ，则如图4 ，不失一般睦，设。1 1 f ，由d ( 0 2 ，y 1 ) 2 ，知0 2 与岛中一点 相邻，不妨设x 2 玑f 此时设y = g 2 ( 0 3 ) ，若y b 1 ，则d ( x 3 ，y 1 ) 3 ，矛盾 若”b 2 ，则d ( z 3 ，y 4 ) 3 ，矛盾所以只能i a l = 1 8 1 l = l b 2 l = 1 a 2 l = 2 ，为保证 d = 2 ，g 只能为w j 图，矛盾口 a 。( 菱凫名祭基写耄单l 器罐磊邻 推论2 22 设图g 满足6 3 ，d = 2 且不包含三角形，那么g 是超级限制边连 通的当且仅当g 不同构于w j 图 证明必要性显然用反证法完成充分性的证明若g 不是超级限制边连通的， 则存在最小限制边割f ，使得g f 的两个连通分支g 1 ，g 。的顶点数都至少为3 记 x = v ( c 1 ) ，y = v ( c 2 ) ，则l x l 3 ，i y l 3 如果存在。x ，f y ，使得z ，y 都不 1 0 图的超级限制边连通性 与f 中的边关联，则显然d ( x ，g ) 3 ，与d ：2 矛盾所以，不失一般性，可设x 中的顶点都与f 中的边关联，即x = x o ，由定理2 22 ，知有l x l = 2 或i y i = 2 ，矛 盾 口 显然这个推论从某个角度上看，改进了定理2 1 2 ( 6 ) ，且由这个推论可知满足6 3 ， d = 2 ，9 4 ，2 9 的图是超级限制边连通的此外，由这个推论也知6 3 ，d = 2 且不为w s 的偶图是超级限制边连通的 在第一章中我们说图w 6 是极大边连通但不是超级边连通的，那么图w 6 当然也 不是极大限制边连通图在证明下一个定理之前我们需要一个引理 引理2 2l 设g 是v ( 4 ) 阶图，如果对于g 中的任一条边叫有f n ( x ) n n ( y ) is 1 ，对于g 中的任一对不相邻点u 和w 有d ( u ) + d ( ) 一l ，则g 是极大限制边连 通的，除非g 同构于w 6 图 证明若g 不是极大限制边连通的，即入7 ( g ) ( g ) ，设f 是g 的一个最小限 制边割，有l f l = a ，若l x l = 2 或i y l = 2 ，则i f i = ( g ) ，矛盾所以i xj 3 且 i y l 3 根据性质2 1 1 ，2 1 2 ，2 13 不失一般性可设f 饱和x 此时，对g 1 中任意 的一条边茁g ，有 ( g ) sd ( x ) + d ( y )