（计算机应用技术专业论文）圈和路径添加边后的直径问题.pdf

摘要 组合网络理论是数学和计算机科学交叉形成的一个新的研究领域，是互联网络研究的 重要工具。而作为组合网络理论重要组成部分的添加边问题，在互联网络的实际应用中更 是发挥着重大作用。添加边问题的解决是相当困难的，s c h o o n e 等人已经证明了它是一个 n p c 问题。 对给定的正整数f 和图h ，在图巾添加，条边后得到图g ( 称为变更图) ，求解所 有添边方式下产生的变更图的最小直径，这就是本文重点研究的“添加边问题”的一个变 型情况。此类变型情况的研究对“添加边问题”的最终解决具有相当重要的意义。 列r 曲类简单的基本图月个节点的尢同路彳仝e 和尢j 司i 到踞q ，令p ( n ，r ) 和c ( n ，r ) 分别表示在只和c j ，中分别添加f 条边后得到的变更图的最小直径。s c h o o n e 等人已证明： 犰s 吼m 刃斟删，可斟嘶，可字卜一赴，且蹦，c s 和g a l e y 证明了：者一l p ( 州) 鬲n + 3 当f 为偶剡，南小c 拈老+ 3 - 当f 为奇数时，三一1 g ( ”，r ) 5 , m 埘= 即s ，：爿c z ，= 降 f o r a 3a n d 5 ，c h u n ga n dg a l e yh a v ep r o v e d t h a t ：者一1 砌，咏者+ 3 ； 毫挑，小素+ 3 ，w h e n t i se v e n ；斋书蛳) 鬲n n w h e n 恤。d d t h i sp a p e rf o c u s e so nt h el e a s td i a m e t e ro ft h ea l t e r e dg r a p h sf o r m e db ya d d i n gt ( t = 3 , 4 ) e d g e st oc f 7f i r s t ，a l li n s t a n c eo fe d g e a d d i n gm e t h o d i sp r o v i d e dt ow o r ko u tt h eu p p e rb o u n d o ft h ec ( n ，f ) t h e n ，t h el o w e rb o u n do ft h ec ( n ，f ) i sp r o v e d a sar e s u l t ，t h ev a l u eo fc ( n ，) i s ：c ( n ，3 ) = i ；l ，盯9 ；c ( n ，4 ) = l ；l + l 盯3 0 t h i sp a p e ra l s os t l ) d i e st h ea l t e r e d g r a p h sf o r m e db ya d d i n g t ( t 4 ) e d g e st o p ，a n d i m p l e v e s t h e u p p e rb o u n do fp ( n ，f ) b yp r o v i d i n gas p e c i a lm e t h o do fa d d i n ge d g e s ：l e t 0 = ，z n o d2 ( 1 + 1 1 a n d w h e n 5 p ( 姐，f ) 兰_ + 1 ，f0 = f + l ，t + 2 ，t + 3 ； ，+ l 尸( ，) 一旦_ + 2 ，f0 = t + 4 ，+ 5 ，t + 6 0 r o 0 ，。 t + l k e y w o r d s ：e d g e a d d i n gp r o h l e m ；a l t e r e dg r a p h ；d i a m t e r ：p a t h ；c i r o i e 圈和路径添加边后的直径问题 0 前言 互联网络理论基于其应用的广泛性，日益受到运筹学界、计算机科学界、自动化学 界等高度重视。同时，互联网络理论涉及组合最优化、图论、计算复杂性、算法设计与 分析等多个学科的研究内容。图论是分析和研究网络拓扑结构的有力的数学工具，图的 某些参数，如直径，因为其在图论及组合数学中固有的重要性及其与通信网络的容错性 和传输延迟的关系而得到广泛发展。 给定直径为h 的图日和正整数k ( k h ) ，需要在中至少添加多少条边才能使得 到的图g 的直径d ( g ) k ? 这就是文献中和本文着重研究论述的所谓“添加边问题”。 添加边问题是在组合网络理论的研究中提出来的，具有非常重要的研究意义。例如，假 定是一个信道带宽给定的信息处理系统网络的拓扑结构，它的最大传输延迟为h 。 现有组数据需要通过此网络在一个给定的时限女内从一个点传到另一个点。如果k h ， 为使得数据能在规定的时限k 内到达，那么就必须通过添加连线对原网络进行改造，这 个问题的实质就是添加边问题。 然而，添加边问题的解决是相当困难的，s c h o o n e 等人f j 】已证明添加边问题是n p c 问题。当前，众多研究者往往研究一些特殊图的添加边问题，或者研究添加边问题的变 型情况，并已经取得了一些显著成果，期望能最终解决添加边问题：c h u n g 和g a r e y t m 率先提出了减边问题以及添加边问题的变型情况，s c h o o n e 等人川作了进一步的研究。 在一些特殊图的添加边问题研究中，a l o n 和a n d r 缸等人【3 l 研究了最大度为d 的图的添 加边问题，e l e n a 等人1 4 l 对无向圈的添加边问题进行了研究讨论，e r d o s 、g y a r f a s 和 r u s z i n k o 5 】研究了不含三角形的图的添加边问题，并给出了相关结论。 对于给定的正整数f 和图，在h 中添加f 条边后得到的变更图的最小直径是多少? 这就是添加边问题的一个变型情况，此类变型情况的研究对“添加边问题”的最终解决 具有相当重要的意义。 当前剥变型情况的研究，主要集中在对无向路只和无向圈c 。这两类最简单的图的 研究。令p ( n ，f ) 和c ( n ，t ) 分别表示在只和c ，中分别添加t 条边后得到的变更图的最小直 都c h o o n c 等人已矾当心吼心) = 阱删) = 1 孚卜啦) = i 孚l 口 对于f 3 且h 5 ，c h u n g 和g a r e y 2 1 证明了：一1 兰e ( n ，f ) + 3 ；当，为偶数时， 老_ 1 c 溉牝鬲 + 3 当f 为奇数时，斋_ 1 ) ，能从g 中最多去掉多少条边厉得到的圆 的直径不超过h ? 圈和路径添加边后的直径问题 s c h o o n e l i 等人已证明它是n p 困难问题。考虑减边问题的稍微不同的变型情况：设 g 是什l 边连通图，由m e n g e r 定理知，从g 中任意地去掉f 条边后的图h 有确定的直 径，记这个直径为d + 。( g ) 。p l e s n i k f i 7 1 首先证明了：对任何无向图g ，有d ：( g ) 2 d ( g ) ， 其中d ( g ) 表示图g 的直径。这个上界是最好的，如奇数个顶点的无向圈c 。，有： d 2 ( c 2 ) = 2 k = 2 d ( c m l ) ， c h u n g 和g a r e y 2 1 研究了更一般的情形，用厂( f ，女) 表示从直径为k 的( 什1 ) 边连通圈 中任意去掉r 条边后得到的图的最大可能的直径。显然，d ：+ ( g ) f ( t ，k ) 。人们感兴趣 的是，对于给定的t 和k ，确定f ( t ，k ) 的值。对于较小的f 或k ，f ( t ，k ) 的值已被确定。 p l e s n i s 【1 7 1 的结果表明，对任何无向图，有： f ( 1 ，k ) = 2 k 。 对于无向图和有向图，p e y r a t 擂j 得到： f ( t ，2 ) = 4 ： 如果，足够大，则： 3 4 5 7 3 f ( t ，3 ) 兰3 万+ 4 。 当k 3 时，p e y r a t 1 8 ) 还得到一个不依赖于k 的更一般的结果，即 f ( t ，女) = m a x 4 ，n 一2 t + 1 a c h u n g 和g a r e y l 2 1 给出，当f 2 1 时，有： f ( t ，k ) = u + 1 ) 女+ d ( r ) 。 s c h o o n e 和b o d l a e n d e r l l l 等给出： ( f 十1 ) 一f f ( t ，k ) o + 1 ) k ，七为偶数； ( f 十1 ) 女一2 f + 2 s f ( t ，k ) 茎( t + 1 ) k ，为奇数。 同时证明了： f ( 2 ，k ) = 3 k l ； 、 f ( 3 ，k ) = 4 k 一2 ； f ( t ，2 ) = f + 3 ，= 1 , 2 ，3 ，4 ，6 ： f ( t ，2 、= f + 2 ，t 7 。 r k e r j o u a n 1 9 1 给出： ( f + 1 ) k r f ( t ，k ) 0 + 1 ) i 一，十3 ，i 为偶数； o + 1 ) 女一2 f + 4 f ( t ，k ) ( f + 1 ) 一r + 3 ，k 为奇数。 在实际应用中，常常不必要求g 是“+ 1 ) 边连通的，仅要求从g 中任意去掉f 条 边后仍然是连通的。这个事实导致人们研究一个与上述讨论的稍微不同的问题。令 圈和路径添加边后的直径问题 g ( t ，k ) 表示从直径为k 的连通无向图中任意去掉条边后得到的连通图的最大直径。显 然有： f ( t ，k ) g ( i ，尼) 容易确定，当k 2 时，有： g o ，k ) = 2 k ； g ( 2 ，k ) = 3 k 一1 ； g ( 3 ，k ) = 4 k 一2 s c h o o n e 等人 1j 确定了； g ( t ，2 ) = r + 3 ，t = 1 ，2 ，3 ，4 ，6 ； g ( t ，2 ) = f + 2 ，t 7 。 关于f ( t ，豇) 或者g ( t ，女) 的界，c h u n g 和g a r e y l 2 1 得到： o + 1 ) ( 一3 ) f ( t ，k ) g ( t ，k ) ( t + 1 ) + f ，k 4 。 s c h o o n e 等人修改g ( t ，t ) 的界为： ”眦猁啦，嘏麓之 裟魏掀 用季( r ，k ) 表示从任何一个直径为k 的有向图中去掉，条边后得到的强连通有向图 的最大裔径。对于女3 ，容易构造一个有向图使得它的直径为g ( t ，k ) = n 一1 。s c h o o n e 等人确定了： 蜃( r ，2 ) = 2 t + 2 。 设“西( q j ，) 表示在不改变超立方体q j ，的直径的前提下可以从q ，中去掉的边的个数。 b o u a b d a l l a h l 2 0 l 给出“万( q ) 的上下界： z “姐卜呱一锄z ”叫甜 1 3 2 最大度为口的图的添加边问题 令厶( g ) 表示在图g 中添加边使得到的图g 的直径d ( g ) d 所需要添加的最少边 圈和路径添加边后的直径问题 数。显然，如果g 有n 个顶点且没有边，则有f ，( g ) = n 一1 ，d 2 ；因为只有 个顶点 的完全图丘，的直径为l ，所以有，；( g ) = j e ( k 。g ) j 。 对于没有最大度限制的图的添加边问题的研究是非常困难的。a l o n 和n o g a 3 】讨论 了最大度为d 的图的添加边问题，文中将所添加的边构成的图记为图且图h 的连通 的子图若不含回路，则称为组件树。并给出如下定理： 定理1 ，1 ：对于h 个顶点的图g ，如果它的最大度为d ，并且 足够大，则只有满足 e ( h ) d 一1 ，才能使添边后得到的图g 的直径d ( c ) 2 ，即： ( g ) 一d 一1 ，”卜雎o ( g ) 。 作者令，表示所添加的边构成的图日中包含的组件树的个数，并分( ，d + 】) 和 ( r d + 1 ) 两种情况分别讨论，证明当满足月卜n o ( = ( d 2 + d + 1 ) ( 2 d 3 十5 d 2 + 2 d 一 1 ) + 1 ) 时，为使添边后得到的图g 的直径不大于2 ，酃d ( g i ) 2 ，必有e ( h ) ”一d 一1 成立。这样就给出了胛足够大时对于最大度为d 的图g ，厶( g ) 的下界值。 对于最大度为口的图g ，厂( g ) 的上界值的证明比较简单：假设图g 中顶点x 的 度为d ，则有门一l d 个顶点没有和顶点x 邻接，连接所有这些点与顶点z ，则最多需 要添加”一1 一d 条边使得所得图g 中的顶点都与顶点x 直接相连，且v ( g ) 一x 中任意 2 个顶点可通过点x 经过2 条边相联，满足d ( o ) s2 ，e ( h ) n d 一1 。即： ( g ) 生 一d 一1 。 于是得到”卜”。( g ) 时l ( o ) 的精确值： ( g ) = h d - 1 。 作者同时给出了下面的定理： 定理1 2 ：对于h 个顶点的图g ，如果它的最大度为d ( d 2 2 ) 。则只有满足 p ( 片) 门一3 ( d + 】) 3 2 ( d + 1 ) 2 1 ，才能使添边后得到的图g 的直径j ( g 。) s 3 。即； j a g ) 月一3 ( d + 1 ) 3 2 ( d + 1 ) 2 1 ，d 2 。 1 3 3 无向圈的添加边问题 因为无向闽的最大度d 为2 ，所以结合定理1 1 和定理1 2 ，a l o n 和n o g a t m 给出如 下推论： 推论1 1 ：对于n 个节点的无向圈c ，如果h 卜0 。；2 7 4 ) ，则只有满足e ( h ) 一3 - 才能使添边后得到的图g 的直径d ( g ) s 2 。即： ( c ，。) 一3 ，n 2 7 4 。 吲和路径添新i 边后的直径问题 推论1 ，2 ：对于h 个节点的无向圈c 则只有满足g ( ) t l - 1 0 0 ，乃能使添边后得到 的图g 的直径d ( g ) 3 。即： 六( c ，) 以一1 0 0 。 并得出如下结论：对于”个节点的无向圈c 。有： 1 对任意正整数h 和 。有： l 赤j 挑麒哪l 淼j 2 对任意正整数h 和n ，有： l 志j _ 1 4 s c 哪l 南o e l e n a g r i g o r e s e u 等人【4 1 对d = 2 , 3 的情况进一步研究，给出下面结论，进一步改进了 界限： 厂2 ( c 。) 胛一3 ，挖卜1 2 ； ( c ，) n 一5 9 ； 兀( c t t ) h 一8 ，h 卜1 2 。 1 3 4 不含三角形的图的添加边问题 对于不包含三角形的图g ，令( g ) 表示在图g 中添加边使得到的图g 。仍然不包含 三角形且有直径d ( g ) d 所需要添加的最少边数。e r d s s 和p a u l 等人【1 6 1 证明得到：对 于不包含孤立点，并且最大度为d 的图g ，有： h 2 ( g ) = o ( n l o g2n ) h s ( g ) 珂一1 。 e r d 6 s 和p a u l 等人【锄提出猜想，对于满足上述条件并且连通的的图g ，有： h 4 ( g ) ( 1 一e ) n ，0 x 0 x i x 2x 3x 4x 5 么二二立) x 0拍x2x 3x 4x 5 第一种情况弗一w 博忧 图1 1 在只中添加两条边的两种情况 f i g 1 1 t w oc a s e so f a d d i n g t w oe d g e s t o 只 s c h 0 0 l l e 等人就这两种情况分别讨论证明，给出了下面引理： 弛1 1 ：凯测，p ( 啦) 料 同时，s c h 。n e 等人通过构造出一种变更图( 如图1 2 所示) ，证明p ( 行，2 ) 詈i 从而确定p ( n ，2 ) 粕x 1 娩工3 ( 满足ix 。x ，i ，ix 。x ：i ，ix 2 x ，i x ，其中x = f w 3 1 图1 2 在p ，中添加两条边的一种变更图 f i g1 2o n ea l t e r e dg r a p ho f a d d i n gt w oe d g e st o 只 作者通过相似的证明方式，得到了p ( n ，3 ) 和c ( n ，2 ) 的边界值，从而确定了： 圈和路径添加边后的直径问题 删，可孚卜啦，：孚 o 刘红英和刘三阳【2 1 1 通过构造出一种变更图( 如图1 ，3 所示) ，从而证明了下面定理 ( 满足lx o x 【i ，lx t x 2i ，ix 2 x 3i ，l z x 4 ，iz 4 工si x 一1 ，其中工= 叫5 1 ) 图1 3 在p ，中添加4 条边的种变更图 f i g ，1 。3o n e a l t e r e dg r a p h o f a d d i n g f o u re d g e st o p ， 定理1 3 ：当 捌扎p ( s 罔+ 1 。 i 5l 在满足添加边时最大度小于等于一j + 2 的条件一f ，作者分，为偶数和奇数两种情 况，通过分别构造出两种变更图( 其中t 为偶数时变更图可参考图1 3 并将其扩展，f 为奇数时变更图如图1 4 所示) ，得到了p ( n ，r ) 的上界值，于是得到定理1 4 和1 5 。 ，”t i x 2 x l 岣 ( 满足lx n - 1 x 。i , i ) ， _ ij ，。峰x ；lx i x i , i y ，y 喀2 x + 1 ，i = o ，1 ，1 1 2 ， 其中x = ( n t 一1 ) 2 ( f + 1 ) 1 ) 图1 4f 为奇数时在只，中添加f 条边的一种变更图 f i g 1 4 0 n ea l t e r e dg r a p ho f a d d i n g t e d g e s t of ：w h e n f i s o d d 定理1 4 ：在有最大度限制的条件下，当r 为偶数，h 为任意不小于h 3 的自然数时 有： 砌力 并卜 定理15 ：在有最大度限制的条件下，当r 为奇数，n 为任意不小于t + 3 的自然数时 有： 圈和路径添力边后的直径问题 尸( n ，f ) 2 ln 2 。- t + - 1 ) 1 1 l + 3 。 c h u n g 和g a r e y 2 1 研究了对于任意的r 3 且 5 ，p ( n ，) 和c ( n ，f ) 的边界值。通过 数学证明给出了p ( h ，r ) 的下界，并通过给出一种变更图( 如图1 5 所示) ，得到p ( n ，) 的 上界值，从而有下面定理成立： 定理1 6 ：对于所有的f l ，有：者一l p ( 嘎，) 雨n + 3 a 粕o l 恐 码x n 1 x n ( 满足lx o x li , ix n - i x 。i x ；lx i x i 2 x + 1 ，i = 1 ，h 一2 ， 其中x = 1 0 一r - 1 ) 2 ( t + 1 ) i o ) 图1 5 在只中添加t 条边的一种变更图 f i g 1 5o n ea l t e r e dg m p ho f a d d i n gte d g e st o 只 由于连接无向路径尸，的两个端点即可得到无向回路c 一同时考虑p ( n ，f ) 和c ( n ，f ) 的定义，从而得到了c ( h ，f ) 的下界，即： c ( n ，f ) p ( n ，t + 1 ) _ ：一1 。 f 为偶数时，通过构造出一种变更图( 如图1 6 所示) 可以得出c ( n ，f ) 的上界， 从而有下面定理： 定理1 7 ：如果r 为偶数，则有：丢一1s c ( n , t ) 丢+ 3 。 ( 其中lx ，x j + li = n l ( t + 2 ) ，对于其它的偶数t 可以得到类似变更图) 图1 6t = 6 和n = 3 2 时c ( n ，f ) 的一个变更图 f i g 1 6o n e a l t e r e dg m p ho fc ( n ，f ) w h e nt = 6a n d 2 3 2 咧和路径添加边后的直径问题 r 为奇数时，作者通过与定理1 6 类似的证明得到了c ( 月，) 更好的下界值，即 c ( 行，f ) 旦t + l 一1 。 连接图1 5 p ( n ，f ) 的变更图的两个端点可以得到c ( n ，f ) 的一种变更图。从而得到t 为奇数时c ( n ，) 的上界值，于是有下面定理： 定理1 8 ：如果f 为奇数则有：者一l c ( 州) 南+ 3 。 c h u n g 和g a r e y l 2 1 同时讨论了减边问题，并给出结论：如果从直径为k 的图g 中去 掉t 条边后得到的图的直径为h ，则k p ( h + l ，f ) 。这个结果揭示了添加边问题和减边 问题之间的密切关系，它表明如果能从一条只+ 。通过添加t 条边后得到一个直径为k 的 图，则h 就是g ( t ，k ) 的一个上界。这个事实也说明了确定p ( n ，t ) 的重要性a 以上的研究成果，对无向路和无向圈这两类最简单的图的添加边问题变型情形的研 究有非常重要的意义，同时推动了添加边问题的研究。本文在前人的研究基础上，对无 向路和无向圈的添加边问题的变型情况作了更深入的研究，并取 导了一定的成果。 1 4 本文工作 本文在前人研究工作的基础上对无向路和无向圈添加边问题的变型情况作进步 的研究，重点研究( ，= 3 ，4 ) 时c ( n ，f 1 ) 的值，和( f ：4 ) 时p ( n ，f 2 ) 的上界。主要做r 以下 几个方面的工作： 1 设计相应算法，以求得, 较小时在c ，( 或只) 中添加( 或f ：) 条边的所有 变更图中直径较小的变更图； 2 研究n 较小时在只中添加 条边的直径较小的变更图的添边规律，并将其推广， 构造出 为任意自然数时直径较小的变更图，计算变更图的直径，从而逝”一步改进 p ( ”，屯) 的上界； 3 研究门较小时在e 。中添加t 。条边的直径较小的变更图的添边规律，构一z e t t h n 为 任意自然数时直径较小的变更图，计算变更图的直径，从而求得c ( n ， ) 的上界i 4 理论上证明c ( n ，t ) 的下界。结合c ( n ，) 的上界，最终求得c ( n ， ) 的值。 5 设计相应算法，验证c ( n ，柏的下界证明中分情形证明的正确性和完整性。 嘲和路径添加边后的直径问题 2 对p ( n ，力界的改进 c h u n g 和g a r e y 在他们的文章 2 1 中构造出一种变更图，得到了p ( n ，o 的一个上界： 者一l s m 力 鬲n + 3 。 本文通过f i n d b e t t e r w a y 算法( 见第五部分) 搜索”2 0 时只0 5 ) 中添加t ( t 4 ) 条边后得到的直径最小的变更图，并研究这些变更图的添边规律，将其推广到n 为任意 的自然数的情况，构造出如图2 1 所示的一种变更图，对p ( n ，t ) 的上界作进一步的改进。 图2 1 在尸，中添加t 条边后得到的一种变更幽 f i g 2 1 o n ea l t e r e dg r a p ho f a d d i n g te d g e s t o 只， 令d ，表示在只中添加f 条边后得到的变更图g ，的直径，即：d ，= d ( g ，) 。我们对h 进行2 ( ，十1 ) 耿模，根据结果的不同分下面几种情况来讨论，在每种情况下求得变更图的 直径，从而给出p ( n ，) 的上界。 情况1 ：n = 2 m ( t + 1 ) + r ，r = 0 1 ，t 。 当r = 0 ，令i e ( d ) l = m 一1 ，i e ( h ) l = m ，其它f 段各段长度为2 m ；以后，每增加1 ， 使其中的一个长为2 州的段长度变为2 m + l 。由直径d 。的定义我们有： 叫竿h 竿卜小b 卜 雷况2 ： 2 2 m ( f + 1 ) + ，；，2 f 十1 ，t + 2 ，t + 3 ，t + 4 ，t + 5 ，t + 6 a 当r = t + 1 ，令i e ( c o l = m ，l e ( h ) l = m ，其它f 段各段长度为2 m + l 。由直径d 。的定义 我们有： 护l 竽j 十l 竽卜小引儿 当r = t + 2 ，令i e ( d ) l = m ，l e ( h ) l = m ，i e ( a ) l = 2 m + 2 ，其它f 1 段各段长度为2 m + l 。 由直径d 。的定义我们有： ! 堕坚堡! 塑! ! 望堕塑皇丝塑塑 铲l 竽j + l 竽卜小h 儿 当r = t + 3 ，4 l e ( a ) 1 2 m ，i 以 ) 户川， e ( a ) l = 2 m + 2 ， e ( e ) l = 2 m + 2 ，其它t - 2 段各段长 度为2 m + l 。由直径以的定义我们有： 以竽h 竿卜伽引“ 当r = t + 4 ，+ l e ( 4 1 = m ，l e ( h ) j = m ，i e ( a ) l = 2 m + 3 ，i e ( e ) l = 2 州十2 ，其它f 一2 段各段长 度为2 m + l 。由直径丸的定义我们有： 铲l 竽h 竽卜小引化 当r = t + 5 ，令f 耳卜= ，i e ( h ) l = m ，i e ( a ) = 2 m + 3 ，i e ( b ) f = 2 m + 2 ，i e ( e ) f = 2 m + 2 ，其 它t - 3 段各段长度为2 m + 1 。出直径以的定义我们有： 办= 肾h 竽j = 2 m + 3 = m 1 - - 竺- n ；+ 2 。 当，= t + 6 ，令以回l = i e ( h ) l = m ，i e ( a ) l = 2 m + 4 ，i e ( b ) l = 2 m + 2 ，i e ( e ) l = 2 m + 2 ，其 它 一3 段各段长度为2 m + l 。由直径屯的定义我们有： 嘭= l 莩h 竽j = 2 m + 3 = l t 斋l j + 2 。 情况3 ：n = 2 m ( t + 1 ) + r r = t + 7 ，t + 8 ，2 t + 1 。 当，= 1 + 7 ，令f 毋_ m ，f 哪) _ 所，i e ( a ) l = 2 m + 2 ，i e ( b ) l = 2 m + 2 ，i e ( c ) l = 2 ，n + 2 ， i e ( d ) l = 2 m + 2 ，i e ( e ) l = 2 m + 2 ，l e 1 = 2 m + 2 ，其它t - 6 段各段长度为2 m + l ：以后，每增 加1 r 则使其中一个长为2 m + 1 段长度变为2 m + 2 。由直径以的定义我们有： 嘟竿j + l 竽卜悱“ 综合上述讨论，我们得到p ( n ，f ) 的一个上界，如下面定理所述 定理2 1 ：当月5 ，t 4 时，有： ，( n ，f ) i t - 备l j + 1 ；r = n r o o d 2 p + x r = ，+ ，r + z ，r + ，； l 南j + 2 ；r = n m o d 2 ( h 1 ) ，一o ，1 ，2 。“，r + s ； l 斋j + 3 ；r = n m o d 2 ”耽以盈扎 一一 一一 鬯塑堕堡竖型望堕塑皇丝塑些一 3 对c ( n ，3 ) 的研究 令g 。表示在鹫c 。中添加t 条边后得到的变更图，d 。表示变更图g 。的直径，即； d c = d ( g 。) ， m p ( u ，v ) 表示顶点“，v ( e 矿( g c ) ) 之问的最短路径。 对于图g 。的段鼍和j ，的最小路径视图g ：( ，d 可能存在着很多种情况，这里我们仅 讨论本文涉及到的如图3 1 所示的4 种常见类型，其中8 、 g 是段j ，和。，的端点口、b 、 e 、d 之间的最短路径。为叙述方便，我们分别把这4 神类型称为m p v - i 、m p v - 、m p v - m m p u j v ， 娶岛基 c s j d c m p v - 1 s d c m p v ，n s s d c sd m p y i i im p 仁l y 图3 1 最小路径视图的四利，常见类型 f i g 3 1 f o u rg e n e r a lc a s e so fm p v 于是有f 而的引理3 1 成立： 引理31 ： 如果段5 和s ，的路径视图g ：( f ，) 满足a s p v - i ，则i e ( s ) f + f e ( p ) f + i e ( s 川吐 如果段s ，和s 的路径视图( f ，) 满足m p v - i ，则： l e ( s ，) l + i e ( p ) i + 2 i e ( f ) l 十2 i e ( s ，) j 茎2 d + 1 ； 如果段s ，和s ，的路径视图g ：( f ，) 满足m p v - j r i , 则： le ( s ，) 1 十j e ( # ) 1 + 1e ( f ) 1 + 1 e ( s ，) 1 2 d 。+ 1 ； 如果段s 和s ，的路径视图( ，) 满足m p v - i v , 则： f e ( s ，) f 十i e ( p ) f + 2 f e ( g ) f + f e p ，) f + f 正( ) f 2 t + 2 。 证明： 段j ，上的点到段j ，上的点的距离的最大值为： e ( s 。) i + l 昱( g ) l + i e ( s ，) i = d ( g ：( f ，j ) ) = d ( g ：( i ，j ) ) d 。： m p v - ：段s ，上的点到段s 上的点的距离的最大值为 刚和路径添加边后的直衽问题 i l 兰垒上掣f + i e ( f ) l + l e ( 。) 峰d 。， 所以： i e ( j ，) i + f e ( p ) i + 2 i e ( f ) i + 2 f e ( s ，) i 2 d 。+ 1 ； m p v - j 蕊：段j ，上的点到段s ，上的点的距离的最大值为： 燮兰竖趔b ， 所以： i e ( 5 ，) i + e 0 ) i + l e ( 厂) i + l e ( j ) 喀2 d 。十1 ； m p v - i v ：段5 ，上的点到段s ，上的点的距离的最大使为； i 掣j + ig ( g ) i + l 半卜 所以： i e ( s ，) i + 点( p ) i + 2 i e ( g ) + | e ( s ) f + j e ( ，) i 2 d 。+ 2 。 根摄定理3 ，l ，显然可以得到下面的推论： 推论3 1 ：若图g 。l m 3 ts 。和s ，的最小路径视图g ：( f ，- ，) 满足m p v - 1 、脚胙，、m p v - i l l m p v - i v c 任意一种。则有：甄