（应用数学专业论文）强定向的最小平均距离.pdf

摘要 对个图g 的每一条边指定个方向使其成为有向图，这样所得到的有向 图d 称为图g 的定向如果有向图d 中任意两点都是可以互达的，则称d 为 强定向图g 的平均距离肛( g ) 定义为所有的点对( 若g 为有向图则为有序点 对) 之间的距离的和的平均值定义砧i 。( g ) 为取遍g 的所有强定向的平均距离 的最小值本文主要考虑砧i 。( g ) 的问题，由两部分构成：第一部分主要考虑确 定面l i 。( g ) 界的问题，给出了般图的届m i 。( g ) 的下界，完全多部图、乘积图的 面0 i 。( g ) 的上界；特别地，在前面讨论的基础上对乘积图的上界又做了进一步的 改进而且，我们还提出了个新的指标p ：j 。( g ) ，讨论了它的一些性质以及它 与面l i l i 。( g ) 的联系，从而给出了口曲( g ) 的个下界第二部分主要考虑了完全 二部图的最优定向问题，我们首先给出了s p e r n e r 定理的一种扩展形式，在此基 础之上我们确定了完全二部图西咖( j 0 ，。) 的值，并且给出了它的最优定向 关键词：定向；平均距离；s p e r n e r 定理推广 a b s t r a c t a no r i e n t e dg r a p hdo fag r a p hgi so b t a i n e df r o mgb ya s s i g n i n ga d i r e c t i o nt oe a c he d g eo fg ：s u c ha no r i e n t e dg r a p hi sa l s oc a l l e da no r i e n t a t i o n o fg a no r i e n t a t i o ndo fgi ss t r o n gi fe v e r yt w ov e r t i c e si nda r em u t u a l l y r e a c h a b l ei nd t h ea v e r a g ed i s t a n c e 芦( g ) o fgi sd e f i n e dt ob et h ea v e r a g e a m o n ga l ld i s t a n c e sb e t w e e na l lp a i r s ( o r d e r e dp a i r si fgi s ad i g r a p h ) o f v e r t i c e so fc l e t 风口i n ( g ) d e n o t et h em i n i m u ma v e r a g ed i s t a n c et a k e no v e r a l ls t r o n go r i e n t a t i o n so fag r a p hg t h i sp a p e rd e a l sw i t h 厅m i n ( g ) t h e m a i ni so r g a n i z e dt ot w op a r t s p a r to n ea i m sa tb o u n d i n gt h ei n d e x 卢m i n ( g ) w eg i v eal o w e rb o u n df o rg e n e r a lg r a p h sa n da nu p p e rb o u n df o rc o m p l e t e m u l t i p a r t i t eg r a p h sa n dc a r t e s i a np r o d u c tg r a p h s ，r e s p e c t i v e l y i np a r t i c u l a r ， w ei m p r o v et h eb o u n df o rs o m es p e c i a lc a r t e s i a np r o d u c tg r a p h s m o r e o v e r ， an e wi n d e x 肛盐n ( g ) i si n t r o d u c e dw h i c hi ss h o w nt oh a v eac l o s e dr e l a t i o n w i t h 砧i ( g ) t h e nw eg i v eal o w e rb o u n df o r 氏j n ( g ) i nt e r m so f 吒i 。( g ) p a r tt w oi st os o l v et h eo p t i m a lo r i e n t a t i o nf o rc o m p l e t eb i p a r t i t eg r a p h s t o t h i se n d ，ag e n e r a l i z a t i o no fs p e r n e r st h e o r e mi se s t a b l i s h e d b yu s i n gt h i s g e n e r a l i z e ds p e r n e r st h e o r e m ，w ed e t e r m i n et h ee x a c tv a l u eo ff 。i n ( k p ，q ) b y c o n s t r u c t i n ga no p t i m a lo r i e n t a t i o n k e y w o r d ：o r i e n t a t i o n ；a v e r a g ed i s t a n c e ；g e n e r a l i z a t i o no fs p e r n e r st h e o - r e m 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的 研究成果。本人在论文写作中参考的其他个人或集体的研 究成果，均在文中以明确方式标明。本人依法享有和承担 由此论文而产生的责任。 声明人( 签名) ：矛输采7 硼6 年f 避f o 黾 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门 大学有权保留并向国家主管部门或其指定机构送交论文的纸质版和 电子版，有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆被查阅，有权将学位论文的内容编入有关数据库进行 检索，有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书 2 、不保密。 ( 请在以上相应括号内打” ”) 作者签名：胁切彤年j 筠扫日 导师签名：年 月 日 第一章引言 第一章引言 个图g 是个有序三元组( g ) ，e ( g ) ，妒g ) ，其中v ( a ) 是非空的顶点 集，e ( a ) 是不与v ( a ) 相交的边集，而妒g 是关联函数，它是g 的无序顶点 对有向图d 是个有序三元组( y ( d ) ，a ( d ) ，砂d ) ，其中v ( d ) 是非空的顶 点集，a ( d ) 是不与v ( d 1 相交的弧集，而妒d 是关联函数，它使d 的每条弧 对应于d 的有序顶点对图g 的定向是指将g 的每一条边指定一个方向，从 而得到一个有向图，这样的有向图称为g 的定向图g 的个定向d 称为强 定向，如果d 中任意两点都是相互可达的 图的定向是图论的个重要的研究方向，具有十分重要的理论意义与现实意 义其应用面十分广泛，涉及到通讯网络、计数化学、交通控制等很多方面】 其最具代表性的个例子就是在交通当中的应用 般来说，个城市的道路都是可以双向行驶的，称之为双向道路系统；若因 城市发展的需要或者为了应对突发事件的需要，现在要求将原来的双向道路系统 设计成为单向道路系统，这其中就要涉及到很多需要考虑的问题了当然，我们首 先要保证所设计的道路系统是可以从城市中的任何地点到达其他任何地点的在此 前提之下，我们自然又会考虑到这个道路系统的一些优化方面的问题，诸如： ( 1 ) 怎样设计能够使从任意地点到另外地点的出行距离尽量最小 ( 2 ) 怎样使从任意地点到另外任意地点的出行距离之和最小 等等许多的实际问题 在 3 1 中r o b b i n s 对上述道路系统进行简化得到了图论模型：将一个双向道 路系统用个无向图表示，其中用点代表路的交叉段( 或者说是路口) ，两个顶点 相邻当且仅当两个路口之间可以互达并且中间不会经过第三个路口这样，我们 就可以将双向道路系统单向化的一个过程抽象化为对无向图进行定向的过程并 且在此文中r o b b i n s 证明了对以后图的定向研究起基础作用的单行道定理：连通 图g 有强定向当且仅当g 中没有桥也就是说，任意2 边连通图都有强定向 第一章引言 2 1 9 6 0 年，n a s h - w i l l i a m s 【4 】将这结果推广到k 弧连通定向中寻找2 边连通 图的强定向的有效算法可以参照r o b e r t s 5 1 ，b o e s c h 和t i n d e l l 6 1 以及c h u n g 等f 7 】 在强定向的基础之上，r o b e r t s 和x u s - n 】考虑了对定向进行优化的问题： 设f 是g 的强定向，怎样最小化下列三个指标 ( i ) d ( f ) = m a x d ( u ，v ) l u ， y ( f ) ) ； ( i i ) l ( f ) = 。y ( f ) m a x d ( u x ) l x y ( f ) ) ； ( i i i ) a ( f ) = e u , v e v ( f ) d ( u ) 问题( i ) 就是对前面优化方面( 1 ) 的抽象化，针对它的讨论逐渐发展成对d ( a ) 以及p ( c ) 的讨论设g = ( ke ) 是个无向简单图；任意的v v ( g ) ，v 的 离心率定义为e ( v ) = m a x d ( v ，x ) l x v ( g ) ) ，这里a ( v ，z ) 是指从顶点”到 顶点。的距离由此，g 的直径定义为d ( g ) = m a ) c e ( ) i 口v ( g ) ) 对于 有向简单图d ，v v ( g ) ，e ( v ) 和d ( d ) 可以类似定义 g 是个2 边连通图，设d ( g ) 为g 的所有的强定向所形成的一个集合 定义 p ( g ) = m i n i d ( d ) l d 口( g ) 一d ( g ) d ( g ) = m i n d ( d ) l d 口( g ) ) 这里，d ( g ) 称为图g 的定向数确定任何一个2 边连通图的定向数是非常困难 的，实际上，c h v g l t a l 和t h o m a s s e n 1 证明了确定个图是否有距离为2 的定 向是n p 困难的因此研究一些特殊的图的文g ) 和对盈g ) 进行定界就成为很 多图论工作者研究的主要方向，并且取得了很多很好的结果，这些结果不仅对此 参数的后续研究有着重要意义，对其他的优化参数的研究也具有很有价值的参考 意义以下列举了一些比较有阶段意义和对我们后来研究具有参考价值的结果 定理1 1 1 3 1 当n23 ， 嘲= 侄篓主 第一章引言 3 2 糍：；： p c p f 乙，= 0 - 若r n ，三i ：差萎j ：三彳! i 。兰i 。s ，、c 4 、4 ，； 另外，k o h 和t a y 在 1 8 - 2 1 】分别计算了关于q 。r ，k m r ，k mx j k c 2 ”l 以及k m c k 的p ( g 日) 更多关于丑k ) 和p ( c ) 的结 果也可参看1 2 2 , 2 3 j 第一章引言 4 问题( i i i ) 就是对前面讹方面( 2 ) 的抽象化，对其的研究逐渐发展成对# 。m i 。( g ) 的讨论g 的平均距离p ( g ) 定义为图g 中所有点对( 有序点对) 之间距离和 的平均值，即 p ( g ) = d ( 1 t ，v ) ( = i ) ， u v e v 一 当g 是无向图时；或者 p ( g ) = d ( ) 礼( 扎一1 ) 似，v ) e v v 当g 是有向图时记距离和一( g ) 为d ( u ，v ) 若g 为无向图，或者 d ( “， ) u ，v e v( u ，v ) v x y 若g 为有向图需要注意的是，如果存在u 口v 使得d ( ，t ，) = 0 0 ，那么我 们就认为o ( c ) 也是o o 给定个2 边连通图g ，定义 厅。j 。( g ) = m i n p ( d ) d 口( g ) ) 图g 的定向d 称为最优的，如果l l ( d ) = 。l m l n ( g ) p l e s n m 2 4 1 证明了寻找任 意给定2 边连通图的最优定向是n p 困难的因此，对厅。j 。( g ) 定界也成为了 很有意义的研究方向 d a n k e l m a n n 2 5 j 等人对一般图和一些特殊的图进行了定界其主要结果如下； 定理1 6 2 s l 假设g 是有r 1 个顶点m 条边的2 边连通图，围长至少为g ，则 ( g ) 2 耥+ f l ( g ) 定理1 7 2 s l 假设2 p q 为整数，则有 # 。m i 。( ，口) 2 ， 等号成立当且仅当qs ( 赢) 我们称整数p ，q 为c o - p a i r s ，如果1 p 曼q ( 卤2 j ) 称p ，g ，r 为 c o - t r i p l e ，如果p ，q 和q ，r 都是c o - p a i r s 则有如下结论： 第一章引言5 定理1 8 【2 目令o l ，a 2 ，一，n f 为正整数并且n = ：1 n ，则有 酬，j 2 _ 勰， 等号成立当且仅当。1 “2 ，吼可以分成c o p a i r s ( 当r 为偶数) 或者可以分成 c o p a i r s 和一个c o - t r i p l e ( 当r 为奇数) 最重要的，他们证明了无法只用p ( g ) 作为指标来给出卢。i ( g ) 的上界在 此前提下，他们讨论了某些特殊图的情况下用( g ) 给出口。i 。( g ) 的一些上界 得到了一些比较好的结论 定理1 9 瞄叫设g = ( 矿e ) 为连通图，并且g 的任意一条边都在一个3 圈中 则 风m ( g ) 茎知) 由此定理可直接得到如下推论： 推论1 1 0 矧设g = ( ve ) 为2 边连通弦图则有 ( g ) s 扣) 定理1 1 1 【2 5 】设g = ( ve ) 为极大平面图，则 比；。( g ) s 缸g ) 定理1 1 2 2 5 1 设g = ( v e ) 为欧拉极大平面图，则 风；。( g ) 缸g ) 并目证明了这个界是最好的界 推论1 1 3 【2 5 】设g = ( ve ) 为外可平面图且g 的任意一条边都在一个3 圈 中则有 风t 。( g ) ；p ( g ) 第一章引言 6 并且证明了这个界是最好的界 关于风曲( g ) 其他方面的一些结论可以参看阮2 6 ，” 图的定向虽然是图论领域的个研究方向，但是在其发展中，我们也发现许 多其他研究领域的成果也可以作为很有力的工具来解决定向问题s p e r n e r 定理 就是其中之一，s p e r n e r 定理是组合数学中非常著名的定理，是1 9 2 8 年 2 8 1 由 s p e r n e r 首先提出的，其具体表述如下： 定理1 1 4 【2 8 】若a 1 ，a 2 ，一，a 。为有限集合n ：= 1 ，2 ，n ) 满足：若i j a t 垡如，那么m ( r ； ) - 这一定理的提出极大地推动了有限集合上的极值问题特别是有限偏序集的发 展偏序集的基本概念如下： s 是一个集合，如果s 上的二元关系5 满足： ( i ) 对任意的a s ，a5a ( 自反性) ， ( i i ) 若n b 并且b n ，则n = b ( 反对称性) ， ( i i i ) 若“b 并且b f ，则口c ( 传遣f 生) ， 则称s 为一个偏序集( p o s e t ) 若有任意的n b s 都有n 墨6 或者b ! a ，则 偏序就称为全序若s 的子集足一个全序集，则称其为链反链是指个其中元 素之间是互相不可比较的集合 根据偏序集理论，s p e r n e r 定理可以表述为：有限集的子集所构成的类 p ( n ) 中反链的个数最多为( f ：1 ) 此后，s p e n e r 定理被推广到偏序集的诸多领域例如，e r d s s 2 9 l 将此定理 推广到其链最多含有r 个元素的p ( n ) 的子集( 这要比反链广泛) 上面；g r i g g s 等人用p ( n ) 中互不相交的元素所组成的特定集合来代替反链k l a i n 和 r o t a a ”，m e s h a l k i n a 2 j 以及b e c k 3 3 l 等人也对s p e r n e r 定理进行了推广本文 也对s p e r n e r 定理进行了推广，从而作为一个有力工具解决了完全二部图的定向 问题 前面提到过寻找一般图的最优定向是n p 困难的，因此数学工作者们就主要 从两个出发点来研究可。i 。( g ) 是对于一些图给出面。i 。( g ) 的界；二是对于某 第一章引言 7 些特殊图确定风i 。( g ) 的精确值以至给出其最优定向，这一方面以往得到的结果 还十分有限这两个方面同时也是本文的两个组成部分第部分中，首先，我 们利用顶点数、边数和直径对以往的结论进行改进，给出了般图卢。i 。( g ) 的下 界然后我们引入了一个新的指标芦。，其定义如下： 设d 是图g 的定向， 州卟志毛咖，矾晰 并且 ，二i 。( g ) 一m i n # + ( d ) i d 口( g ) ) 我们在讨论，c 二_ n 的性质的同时也发现瞌i 。与芦以及正二。有许多的联系；在 此基础之上，利用围长、顶点数和边数给出了对于一般图卢i 。( g ) 的个下界 此外我们还给出了乘积图的一个上界；进一步地，若g 1 g 2 中至少有个是偶 图，我们还利用，c 纛 。对上面的结论进行了改进最后一部分解决了完全二部图的 最优定向问题首先，我们将s p e r n e r 定理进行了推广，利用推广的s p e r n e r 定 理我们给出了完全二部图j 0 。的风一，。) 的确定值和其最优定向，从而将完 全二部图上的最优定向问题完全解决了 第二章定向图平均距离的界 第二章定向图平均距离的界 8 2 1 一般图的平均距离的界 下面的结果是由n g 与t e h a a l 首先发现的 定理2 1 3 4 1 若g 是2 边连通图，有n 个顶点和m 条边，则 ( g ) 2 茄与， 等号成立当且仅当g 有距离为2 的定向 如果我们利用d i g ) 作为个参数，上面定理中的下界可以进行如下改进 定理2 2 设g 为2 边连通图，有n 个顶占、 l 条边，并且承g ) = d ，则 ( g ) 2 一焉+ 锵 证明：设d 为g 的任一强定向，p i 为距离为i ( i = 1 2 k 1 的有序点对数 显然有p l + p 2 + + p k = ”( 一1 ) 并且， 口( d ) = 1 p 】+ 2 p 2 + - k m m + 2 p 2 + 3 ( p 3 + + p k l = m + 2 p 2 + 3 ( n ( n 一1 ) 一m p 2 ) = 3 7 t ( n 一1 ) 一2 m p 2 另外，因为d ( a ) = d ，那么k2d 不失般性，设如，为d 中两点满 足d d ( v o ， o k ) = k ，并且p = o o v l 为连接y o 与v k 的最短路径因 为d d ( v o v k ) = k ，故d d ( v o ，v k 一1 ) = d d ( v 1 ，) = k 一1 ，d d ( v o ，v 3 ) = 如( 口l ，v 4 ) 一= d o ( v k 一3 ，v k ) = 3 ，因此我们有p d21 ，p a 一1 2 ，p d 一2 3 ， 第二章定向图平均距离的界 9 p a2d 一2 这样， p 2 = n ( 他一1 ) m 一喃+ - - - + p k ) sn ( 札一1 ) m 一( p a - i - - + p d ) sn ( n 一1 ) 一 l 一( d 一1 ) ( d 一2 ) 2 将上述结果带入固，则有 o - ( d ) 3 n ( n 1 ) 一2 m 一( n ( n 1 ) 一m ( d 一1 ) ( d 一2 ) 2 ) = 2 n ( n 1 ) 一m + ( d 一1 ) ( d 一2 ) 2 因此， f i m i n ( a ) - - 2 一鼎+ 锵 证毕 口 考虑到对于任意2 边连通图g ，都有丑g ) 2 ，则定理2 1 显然是定理 2 2 的一个特例 2 2 定向图的新指标；i 。 这一部分中，我们主要讨论我们引入的指标p ；i 。的些性质特别是与p ，卢。j n 的关系，同时我们也会发现它也可以作为一个媒介来给出可蛐的个下界注 意：下面的讨论中我们用9 ( g ) ( 在不引起混淆的情况下我们简写作g ) 来代表图 g 的围长 定理2 3对于任意图g ，都有以下不等式成立 p ( g ) s ，f 二i 。( g ) ，( 1 ) ，c m i n ) + 糌圳g ) ( 2 ) 证明：由，z 二i 。的定义，( 1 ) 的结果是显然的 下面我们证明( 2 ) 假设d 为g 的任一定向， 如果u 口e ( g ) ，则 2 m i n d d ( u ， ) d d ( v ，札) + ( g 一2 ) = 2 + ( g 一2 ) = g d d ( u ， ) + d d ( v ，“) 第二章定向图平均距离的界 如果? v g e ( g ) ，则 因此， 2m i n d d ( “，可) ，d d ( v ，) ) 茎d d ( u ，v ) + d d ( v ，u ) 1 0 n ( n 一1 ) p + ( d ) = 2 m i n d d ( u ，”) d d ( w ，“) ) “， y ( g ) = 2m i n d d ( u , v ) ，如( 一) ，+ 2m i n d d ( u , v ) ，a l p ( 州) ) 们e ( g )删e ( g ) s ( t 删) + d 口( 洲) ) 一一2 ) m + ( d d ( u , v ) + d d ( v , u ) ) u v e e ( g )u v g e ( g ) = ( d d ( 刚) + 如( 舢) ) 一( g 一2 ) m u ，e v ( c ) = d d ( u t ) 一( 9 2 ) m ( “， ) v ( g ) v ( g ) = n ( n 一1 ) p ( d ) 一( g 一2 ) ”一 因此 f f 即) g ( d ) 一寐等 故有 ( g ) + 嘉等陆( g ) 证毕 口 定理2 4 设g 是有n 个顶点m 条边的图则 p 二；。( g ) 2 一元i ；与， 等号成立当且仅当g 有定向d 使得：若u vge ( c ) ，则有n f i n d d ( u ，v ) d d ( v ，“) ) = 2 ， 第二章定向图平均距离的界 证明：设d 为g 的任定向， 矿( d ) = 志磊州蚺咄她蝴 而2 ( 。赢，1 + 。赢删咖，似州) ) ) 志( m + 2 ( 掣_ m ) ) ! 竺。，一塑 n ( n 一1 ) n ( n 一1 ) = z 一南n 1 1 n l 因此，“g ) 2 一南 由定理2 3 和定理2 4 我们可以得到如下推论 推舱2 5 设g 为有 4 - n 点 l 条边的图，则 ( g ) 2 + 豁 口 当g = 人0 ，。( q 墨( 1 孑2 i ) ) 2 5 | 此界是可达的 口 2 3 完全多部图和乘积图的平均距离的界 注：在此对前面第一章所提到的定理1 1 做如下解释和扩展： 因为当n 3 并且n 4 时d 【k 。) = 2 ；假设能够达到d ( e 。) = 2 的定向 为d ，则d 应当具有如下形式：若u vge ( g ) 当且仅当d d ( “，v ) = 2 事 实上，若t t vge ( o ) ，则d d ( u ，口) 2 ，又d d ( u ， ) sd ( g o ) = 2 ，因此 d d ( u ，v ) = 2 另一方面，d d ( u ，v ) = 2 显然有u v 岳e ( g ) 这样，通过简单计 算得到卢( d ) = 3 2 ；并且由定理2 1 ，可知届。i 。( 西。) = 3 2 ，因此可知d 即 是最优定向 根据上述定向我们还可以得到完全多都图的个强定向从而得出完全多部 图的一个上界 第二章定向图平均距离的界 定理2 6 对任意的正整数a 1 ，a 2 ，a t ( t 3 ，t 4 ) ，有 础胍。一s3 一志 证明：设d 是使得完全图的达到d 【) 的定向由此我们可以确定甄。，。 的一个定向：将虬，。，。的每部看成是甄的个点；然后将a 。与 之间 的所有边按照的d 定向中地的方向进行定向，这里i ，j 1 ，2 ，t ) 令d 作为按照这种方式的k 。，。，。定向，并且令p i ( i = 1 ，2 ，k ) 为距离为 i 的有序点对数由上面的注，我们有 ( i ) 1 d d ( u ) 2 ，如果乱和v 不在同一划分中时； ( i i ) d d ( “，v ) = 3 ，如果“和v 在同一划分中时因此， 7 ( d 一1 ) 反。i 。( 玩。，m ) s1 p l + 2 p 2 + 3 p 3 t = m + 2 ( ”( n 1 ) 一m 一( n t i = 1 t = 2 n ( 一1 ) _ ”，+ 嘶i 一1 ) t = 1 因为盛屿掣十，。因为厶吐掣十： = 2 n c n 一- ，+ 2 c ( ：) 这样我们便得到 础一，m ) 3 _ 南 证毕 定理2 7 假设g 1 和g 2 为2 边连通图，则 u g 。g 2 ) 茎料( g 。) + 料( g 。) 这里a = i y ( g 1 ) l ，b = f y ( g 2 ) f 口 采 l no 。：l 3+1 m3 一一 nn3= 则 堋 小呐 ， 一 第二章定向图平均距离的界 1 3 证明：令 j i n ( g 1 ) n ( n 一1 ) = ，# 1 m i 。( g 2 ) 6 ( 6 1 ) = p ， 并且设d 1 与d 2 分别为g 1 和g 2 的最优定向如下定义g t g 2 的定向d ： 对于g 1 g 。中的任意点对( “，”) ，”) ( 或者( “，”) ( “，”，) ) ，其定向与d 1 ( 或 者d z ) 中u t t ( 或者? 3 v 7 ) 方向致显然，d 是g g 2 的强定向设( ，v ) 和( 札，v ) 为g l g 2 中的不同点我们需要讨论以下三种情况： ( 1 ) 若v = v ，贝0 有d ( ( “， ) ，( ， ) ) d d l ( u ，) ( 2 ) 若“= u 7 ，贝0 有d ( ( “，”) ，( “， 7 ) ) d d 2 ( v ，”) ( 3 ) 若7 1 7 并且t ，v ，则有d ( ( u ，w ) ，( “，v p ) ) 茎d o 。( i t ，) + d d 2 ( v ，? 3 1 ) 因此， o ( d ) =fd ( ( 啪) ，( 趾，口) ) ( u ， ) ，( u ，矿) e u u = d ( ( 删) ( u 7 ，”，) ) + d ( ( 叩) ，( “，) ) + d ( ( n ，”) ，( “，”，) ) = i t = u i u ， s d d ，( 一) + d d ：( 邺7 ) + ( d d ，( 札，u 7 ) + d d 。v , v t ) ) = k l + m ，+ 6 一1 ) a + a ( a 一1 ) 3 = b 2 0 + “2 j 所以( g ，g 2 ) 丽b 2 a + 而a 2 # = 料( g 1 ) + 蚓鼬。( g 2 ) 证 毕口 由定理2 7 ，若g 1 与g 2 为2 边连通图，因此有a 1 ，b 1 ，那么 豆m i 。( g 1 g 2 ) 声m i 。( g 1 ) + 声m i 。( g 2 ) 特别地，如果g 1 或者g 2 有至少有一个是偶图，利用我仃l 前面所提出的二i 。 我们可以对这个上界可以进行如下改进 定理2 8 设g 1 和g 2 为2 边连通图，并且g 1 为偶图 ( g 。x g 2 ) 冬措陆( g 。) + 暑陆( g 。) + 则 ( a 一1 ) ( 6 - a b 一1 第二章定向图平均距离的界 1 4 这里a = i v ( g 1 ) i ，b = y ( g 。) i ， 证明：令玷i ( g 1 ) a ( a 一1 ) = o l ，j i n ( g 2 ) 6 ( 6 1 ) = 卢，p 二i ( g 2 ) b ( b 一1 ) = r ， d - 和d 2 分别为g l 和g 2 的最优定向，( x ，y ) 为偶图g t 的分戈叽接下来我 们如下定义g - g 2 的定向： i ) 对于g 1xg 2 中的边( 札，计) ( 札，v ) ，定向与d 1 中u u 7 的定向方式相同； i i ) 对于g 1 g 2 中的边( “， ) ( “，v ) ，若t t x 则定向与d 2 中v v 定向方式 相同，若札y 贝4 定向与d 2 中”7 定向方式相反 这样有四种情况需要讨论： ( 1 ) 若 = t ，贝0 有d ( ( “， ) ，( u ， ) ) 兰d d 。( “，钍) ( 2 ) 若“= u 7 并且“x ，则有d ( ( u ，口) ，( , a l ，t ，) ) d d 2 ( ，秽，) ， ( 3 ) 若“= “7 并且u y ，则有d ( ( u ， ) ，( u ， ，) ) sd d ：( ，口) ( 4 ) 若“n 7 并且 口7 ，则有d ( ( ，”) ，( h 7 ， ，) ) m i n d d ：( 口， 气d d ：( ，) + d d l ( t 1 ! l ，) 因此， 一( d ) = d ( ( 刚) ，( “，”，) ) ( u ， ) ，( u ，) u v z = d ( ( m ”) ( u ”，) ) + d ( ( 刚) ，( “7 ，”，) ) + d ( ( 邺) ，( u t ，v t ) ) 侧u = 1 u u ，t 矿 茎d o 。( m 札) + d d 2 ( ”，”7 ) + ( m i n d d 2 ( ”，”，) ，d 仍( ”7 ，口) ) + d o 。( 札“) ) = b a + 。口+ n ( 一1 ) r + b ( b 一1 ) o = b 2 a + 卢+ 8 ( d 一1 ) r 这样，( g 1 xg 2 ) s 堕翥坐 s 笔并础g 。) + 刍；( g 。) + 鱼专糌刖g 。) 口 由定理2 3 和定理2 8 我们可直接得到以下推论，从而可以看出在某个图 是偶图的情况下，定理2 8 比定理2 7 的改进之处 第二章定向图平均距离的界 推论2 9 令g l 和g 2 为2 边连通图并且g 1 为偶图， ( g ，g 2 ) s 料陆( g 。) + 等( g 。) 这里a = i y ( g 1 ) i ，b = i 矿( g 2 ) l ，m = i e ( g 2 ) 1 则 1 5 b ( a b 一1 ) 7 口 笠三主墅婴竺塞墨箜二全整垄查全三童里堕墨丛鱼 1 6 第三章s p e r n e r 定理的一个推广及完全二部图的最优定向 3 1s p e r n e r 定理的推广 设有限集n = 1 ，2 ，n ) ，y 为由n 的子集所形成的族( 族中的子集 允许有重复) 定义符号 ( y ) = i ( f y ) ：y y ，y y ) i 例如，没m = 1 ，2 ) ，= 1 ，2 ，3 ) ，k = k = 2 ，3 ) 并且y = k ，k ，k ，k ) ， 这样的话( y ) = i ( h ，硷) ，( b ，b ) ，( k ，蚝) ，( 蚝，k ) ，( y 4 ，b ) i = 5 对于去毫个正整数m ，0 r 也就是说，前r 个墨每 个在从( f ) 都恰好出现k + 1 次，剩下的( r 7 1 ) 一r 个五每个在m ( f ) 正好出现七 次例如，如果 = 4 ，f = 8 则m ( 8 ) = 1 ，2 ) ， 1 ，2 ) ， 1 ，3 ) ， 1 ，3 ) ， 1 ，4 ) ， 2 ，3 ) ， 2 ，4 ) ， 3 ，4 ) ) 特别地，如果f = ( 鬲) 则虬( c ) = p r l ( n ) 对于的某个子集y ，以f 来记其补集族y 的补集如下定义： 歹= f = y ：y y ) 定理3 2 i i _ 设y 为有限集n = 1 ，2 ，扎) 的子集所形成的类( 类中的子集 可重复) ，- ) i - 且l y 可写成i v l = k ( f 知) 4 - r 的形式，这里k o ，l ，2 t - 且 0 rs ( f ；n 1 ) 一1 贝1 】 妙) 三( i y d ) = 2 k r + k ( 卜1 ) ( 秒 ( 3 ) 或者，等价地 例蚤卜n 搿美 并且当他24 等号成立当且仅当y 竺虬( 1 y 1 ) 或了竺虬( 1 y 1 ) 证明：如果礼3 ，上述结论可由观察得到这样的话，我们只须证明n 4 的情况成立即可对任意的正整数i ，记 弘= y ：y y ，l y l = ) 墨三主墅塑! 竺塞堡鱼二全塑垄墨全三整圈堕塞垡塞鱼 1 8 我f f 僧先考虑啊2y ( 或者y 【刊2y ) 相当i 阁( 或者 i 【；j ) 有弘= 口的情况对任意的子集y y ，记m y ( y ) 为y 在y 中 出现的次数由以上符号的定义，我们可以得到m y ( y ) = i y l y e p ( n ) 若存在y 7 y 使得y ( y ) 一m y ( y ) 22 ，则定义 y 7 = ( y y 7 ) ) u y ) 显然有1 3 7 i = l y i 并且( y ) z 。一对任意的非负整数h ，我们定义函数f ( y ) = yu ( y ) ) ，这里 ( y ) = x n - - $ 若s + hi0 ( m o d ( n t ) ) ；其他的则有 ( y ) = z ( 叶 ) ( 。d ( 。一t ) ) ( 1 ，) 可以用比较直观的方式来进行解释：将1 ，2 ，n ，按顺时针排成一圈，从 z ，开始逆时针数除了y l ，y 2 ，y t 以外的元素，则厶) 即是第( s + h ) 个元 素例如，假设n = 1 0 ，h = 3 ，y = 2 ，3 ，5 ，7 l ，则有t = 4 ，n f = 6 ，s = ( 2 + 3 + 5 + 7 ) = 1 7 ，z 1 = 1 0 ，z 2 = 9 ，x 3 = 8 ，x 4 = 6 ，x 5 = 4 ，x 6 = 1 并且 ( y ) = 。( 卧h ) ( m o a ( n 一) ) = x 2 0 ( m o d 6 ) = x 2 = 9 断言：对任意的y e 弘且任意的非负整数h ，如果y y ，则有 以( y ) 昂( y ，) 事实上，如果y 与y 7 有超过两个的不同元素的话，则显然有a ( y ) ( y ，) 因此我们假设y 与y 7 只有两个不同的元素，设y y = ) 并且l ，y = 可7 ) ，y y 因此，我们可以将y ，y 7 写成如下形式 y = 9 1 ，y 2 ，可，可 和y = 玑，y 2 ，y t 一1 ，9 7 ) 差三主墅竺哩塞墨塑二全整垄丝三里璺塑差! 垦墨鱼 1 9 并且，我们可以写成 可1 ，y 2 ，轨一1 ，) = z l ，巧，y ，x j + l ，- ，x n - t 一1 ) = z i ，z 2 ，z n 一 ， 可1 ，y 2 ，- - ，y t 一1 ，y l = z 1 ，- ，2 c i ，y ，i + 1 ，z 。一t 1 ) = 之i ，名；，- t - ，一t ) ， 这里 x l = z l t r x j = z j y 7 = z 3 + 1 x j + l = 勺+ 2 r x n t 一1 = z n t ， z 1 = 墨 丑= y = + l x i + l = + 2 x n t 一1 = 砭一t 要证明断言成立，只须证明如果 ( y 7 ) = y 则有a ( y ) 矿 令s y = y + e y i ，8 y ，= y 7 + y i ；并且不失般性假设y y ，即 s y ， s y 并且i 玉( 如图1 ，这里。和分别表示，i = 1 ，2 ，n t 一1 和珊，j = 1 ，2 ，t 一1 ，代表y 或者y ) 如果可( = 咯1 ) = ( y ) 则由 ，h 的定义，我们有a ( y ) = z ( i + 1 ) + 。( 。0 d 扣一母) ，这里s = y y = 8 y 一8 y ， 一r o l 2o 3 o o u x 嘲。 。 ，= 争 图1 记n 和卢分别为满足y 7 y ，i 1 ，2 1 ，2 ，t 一1 ) 的x i 和珊的数目容易得到8 因此 ，n t 一1 ) 和y n t 显然 一 o x o 砭； m 蔓三主业笪窒堡鱼二全丝垄塞全三童堕塑塞垡窒鱼 2 0 有( i + 1 ) + s 2 m 一) 因此要证明。( 件1 ) 抽( m o a ( 。一t ) ) 勺+ 1 ，我们只须证 ( j + 1 ) ( 0 + 1 ) + 8 一沁t ) ) 0 事实上，因为t 0 因此我们的断言成立 假设 扩= m ) u r ) ：y m ) 现在我们来计算西( ) 咖) 的值，来和( y ) 的值进行比较 对于两个类y m ，由我们的断言，如果y y 7 则r ( y ) 垡r ( y ) 并且f a ( y 7 ) 堡巩( y ) 即可得到( r ( y ) ，r ( y ，) ) 与( r ( y ，) jr ( y ) ) 对( 扩) 贡献为0 对于类y m 和y 7 y m ，如果ygy 则有ycr ( y ) gr ，这 意味着( r ( y ) ，y 7 ) 对( y “) 的贡献为0 如果ycy 7 ，那么将有如下三种情 况需要讨论： 情况j r ( y ) = y