（运筹学与控制论专业论文）关于图测地数的几个问题.pdf

摘要 本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工作，主要工 作包括以下三个部分：( 1 ) 确定测地数为n 一1 ，亿一2 的图g 的结构；( 2 ) 考虑测地数为 5 的图g ，证明该类图对于吕长虹在文献【4 】中提出的猜想成立；( 3 ) 讨论了tx 地的测 地数。 在第二章中，本文介绍了无向图的测地数在【1 0 l 中，g a r yc h a r t r a n d ，n a n kh 缸a r y 和p i n gz h a n g 证明了9 ( g ) = n 当且仅当g 是完全图珞，本文继续他们的工作，确定 了( 1 ) 测地数g ( g ) = n 一1 当且仅当g 竺日v 凰，其中h = 虬，u 虬。u u 。( 2 ，鼠1i = 1 ，2 ，尼) ，( 2 ) 测地数夕( g ) = 札一2 当且仅当g 有如下性质：j 存 在两个顶点。，可使得g z ，暑，) 皇冠，u 虬。u u 虬 ( 2 ，s t 1 = 1 ，2 ，) ，当图的直径威o m ( g ) = 2 时，对 可作如下划分：q = kuaum ，其中 五= lu y ( g 。) n ( z ) ，口岳 ) ) ；k = 如i 可 y ( g t ) n n ( 彩，封譬( 。) ) ；a = 川 y ( g 。) ， ( 茁) n ( 掣) ) ，若五口，则i ua i 2 ；若m 0 ，则 l k u a i 2 ，并且满足不同时存在两个以上的连通分支g i ，q 使得五，巧，玛n 山均 不为空集，或者，玛，bn 鸟均不为空集j “当西。m ( g ) = 2 ，茁，不相邻时，g 中 有一点与茁，都相邻且至多有两点与茁，可都相邻j v 当出1 ( g ) = 3 时，。，g 必相邻， 在g - 的独立集s ，则称s 为g 的最大独立集( m 凹i m 让mi n d 印e n d e 疵s e 图g 的最大独立 集的顶点数称为g 的独立数( m d 印e 竹d e m 礼啪6 e 一，记为d ( g ) 为了揭示图的结构性质，人们引入了许多参数，如匹配数，覆盖数和控制数等下 面我们介绍其中一个重要的参数一图的测地数( g e d d e 纰竹让m 6 e r ) 对于图g 中的两点 u 和u ，缸一 测地线( 9 d e s i c ) 是路长为d ( u ，u ) 的让一u 路；集合j ( u ， ) 表示位于g 中钍一廿测地线上所有点的集合；对于菲空子集s 冬y ( g ) ，i ( s ) = u 。s j ，v ) ；如 果，( s ) = y ( g ) ，则称s 是g 测地集；并把测地集的最小基数称为g 的测地数，记为 9 ( g ) 类似可以定义有向图d 的测地线，测地集和测地数，不过应该注意的是t 在有向图 中，乱一 测地线和u u 测地线是两条不同的有向路( 或弧) ；，( u ，u ) 表示所有位于一u 测地线和u u 测地线上的点集对于图g ，g 的下测地数( f o 叫盯口e d d e t i c 作帅6 e r ) ， 记为9 一( g ) ，被定义为g 的所有定向图中测地数最小值；g 的上测地数( 钍卯e r9 d e 托c 佗u m 6 e 一，记为矿( g ) ，被定义为g 的所有定向图中测地数的最大值即t 9 一( g ) = m l n b ( d ) ：d 是g 的定向国) ； 9 + ( g ) = m a x d ( d ) ：d 是g 的定向图) 在此基础上，g e r 甜dj ，c h a n g 和l i d at o n g 等人在文献【1 5 中，进一步提出了图测 地谱( 9 e d d e 抚c 印e e t m ) 的概念，用记号s ( g ) 来表示，其中 s ( g ) = 9 ( d ) ：d 是g 的定向图) 图论中，图的运算也是人们研究的重要内容通过图的某种运算，我们可以用两个或 两个以上较小和较简单的图生成一个较大和较复杂的图。由于较小和较简单的图的结构 特性容易把握，从而把握住较大和较复杂的图的结构特性，因此对图的运算的研究是很 有价值的 设g 1 = ( u ，e 1 ) 和g 2 = ( 硷，马) 是两个图，若g - 和g 2 没有公共顶点。则 称它们是不相交的( d 柳d t n t ) ；若g 1 和g 2 没有公共边，则称它们是边不重的( e 曲e d t 白d i n t ) ；g 1 和g 2 的并( 让n 凡) 被定义为g 1 和g 2 中所有边组成的图，记为g 1 u g 2 ， 即g 1ug 2 = ( uk ，晶u 岛) ；g 1 和g 2 的交( 抑e 似e c t l d 礼) ，记为g 1ng 2 ，即 g 1n g 2 = ( n ，e 1n 砀) ；设g 1 和g 2 是两个不相交的简单图，g ，和g 2 的联0 d 响 第一章：引言 华东师范大学硕士论文 5 为图g = g 1 v g 2 ，其中图g 满足y ( g ) = v ( g 1 ) u y ( g 2 ) ，e ( g ) = e ( g 1 ) u e ( g 2 ) u u ： u v ( g 1 ) ， y ( g 2 ) ) ；g i 和g 2 的笛卡儿积( 付e 3 蚴p m d u c t s ) 为图g = g 1 g 2 ， 其中图g 满足y ( g ) = y ( g 。) y ( g 2 ) ，g 中的两个顶点( o ，6 ) 和( c ，d ) 是邻接的当且仅 当n = c 且6 d 曰( g 2 ) 或6 = d 且n c e ( g 1 ) 设u ，o 是g 中两点，若u 量e ( g ) ，在 u ，口之间加一条边所得的图，记为g + u u ，即g + u 口= m e u u ) ) ；若札口e ( g ) ，将 边鲫收缩为一点所得的图，记为g 。u u 类似我们定义如下运算：对于任意两个不相交 的图g 和日，u ， 分别是g ，h 中的点，在点札和口之间加一条边的运算，记为g 。+ j 毛； 使g 和日仅在u ，u 重合的运算，记为瓯。凰 1 3 主要结论 本节定理的编号采用它们在各自章节中出现的编号，其中未介绍的符号和概念请对 照它们相应的章节下面是本文所做的一些结果 定理2 2 1 4 一个竹阶连通图g ，9 ( g ) = 礼一1 当且仅当g 望日v 甄，其中日 = 虬，u 甄：u uk 。( 2 ，岛l 对t = 1 ，2 ，) 引理2 2 2 。2 一个测地数擘( g ) = n 一| c ( 其中k 是非负整数) 的礼阶非平凡连通图 g ，对于比，可y ( g ) ，若。y 隹e ( g ) ，则i ( 。) n ( ) l 后 定理2 2 2 3 一个n 阶非平凡连通图g ，测地数g ( g ) = 礼一2 当且仅当g 有如下 性质：，存在两个顶点z ，y 使得g 一 茁，掣) 兰巩，u 瓦。u u 虬。( 忌2 ，s t 1 i = 1 ，2 ，) ，当战o m ( g ) = 2 时，对g ：可作如下划分：g i = 五ua uk ，其中 。墨= 口i y ( q ) n ) ，廿圣( ) ；m = 训u 矿( g ) n ( 可) ， 隹( z ) ；a = j 口v ( g ；) ，u ) n 白) ) ，若咒0 ，则l mua t l 2 ；若m 口，则 i 咒ua is2 ，并且满足不同时存在两个以上的连通分支g “g j 使得五，巧，玛n 如均 不为空集，或者m j 玛，kna j 均不为空集j 当出肼1 ( g ) = 2 ，z ，管不相邻时，g 中 有一点与z ，掣都相邻且至多有两点与z ，都相邻j y 当出o m ( g ) = 3 时，z ，可必相邻， 在g 一如，g ) 中至少存在两个连通分支，它们的顶点分别都是卫，掣的邻居；对其余连通 分支，若( z ) n y ( g 1 ) 自，则y ( g ) ( z ) ，对该性质同样成立 引理3 2 2g 是一个顶点数大于等于2 的连通图，s 是图的最小测地集，若g 吲是 二部图，那么9 ( g ) 9 + ( g ) 引理3 2 4g 是一个顶点数大于等于2 的n 阶连通图，s 是图的最小测地集，若 g 司连通并且口( g ) = 5 ，那么9 ( g ) 矿( g ) 定义3 2 5 两个图g ，日之间的最短距离，用记号l ( g ，日) = m 伽 此时取 s = v ( g ) ( ( z ) n ( ) ) ，可知1 s 1 2 ，可知与引理2 2 2 2 矛盾 c l a i m7 不同时存在两个以上的连通分支g i ，q 满足五，巧，x ，na 均不为空集，或者 k ，玛，mn a f 均不为空集 反证：若存在两个连通分支满足上述条件，不妨设咒，巧，n 如均不为空集，则一 叼一。一地( 其中u 氓，坝x 女n a k ) 为长为3 的路，与击o m ( g ) = 2 矛盾 下面我们主要对o ，不相邻时讨论图的结构 若g v 荜e ( g ) ，由引理2 2 2 2 可知，i ( 。) n ( g ) i 2 若 ) n ( g ) 为空集， 又因为出口m ( g ) = 2 ，所以存在至少两个连通分支g “q 满足五，k ，n a f 均不为空 第二章：无向图的测地数 华东师范大学硕士论文 1 5 集，由c l a i m6 同样可知矛盾，所以当。g 隹e ( g ) 时满足有一点与z ，掣均相邻且至多有 两点与o ，均相邻 当d t n m ( g ) = 3 时 设s 为g 的最小测地集，我们记g o = g 翻= g 1u g 2 u u g ( 其中 是g o 的连通分支，k 是正整数) 。 因为出n m ( g ) = 3 ，所以在g 中存在墨一z 一可一她，并且可知o l 可，z 2 z 隹e ( g ) 此 时g 中不存在札一t u 的长为2 的路，其中t 扛1 ，z 2 ，z ，订；t 0 ，) 或者w 忙，可) 若g o 连通，则在g o 中存在z 1 一z 2 的长为4 以上的测地线；z 1 一t 1 一t 2 “一z 2 ， 此时可知t 。一屯一t 3 为上述不应存在的长为2 的路，可知矛盾所以g o 至少有两个连 通分支g 1 ，g 2 ，不妨设茁1 y ( g 1 ) ，霉2 y ( g 2 ) c l a i mlg t 均为团( i _ 1 ，2 ，i k ) 反证：若g 1 不为团，则在g 1 中存在u 口隹e ( g ) ，即存在u 一一u c a s e1t 聋1 ，由z 1 一z 一可一z 2 ，u t u 可知g ( g ) 礼一3 ，矛盾 c a s e2 若t = z l ，因为存在 一z l z 一可一z 2 ，而d i n m ( g ) = 3 ，所以必有 z ， 掣中至 少一者存在；同理对u 也成立该性质若u ，删中至少一者存在，不妨设u 掣e ( g ) ，则 由盘1 一。一一z 2 ，0 1 一 一一z 2 可知9 ( g ) 墨n 一3 ，矛盾。若蜘，u 可都不存在，则可 得z ， z e ( g ) ，由u z 1 一u ，u z 一掣一正2 可知9 ( g ) n 一3 ，矛盾 综上所述，g ，均为团 c l a i m2 若( z ) ny ( ) 0 ，则y ( g i ) ( ) ，对可该性质同样成立。 反证：若( z ) ny ( g ) d ，但g 1 中存在u 岳( 。) 设u ( ) ny ( 国) ，此时 存在钍一u 一。一f z 2 长为4 的路因为z 2 隹y ( g 1 ) ，所以叫e ( g ) ，由测地线 u z 一一0 2 ， 一乱一掣一0 2 可知9 ( g ) n 一3 ，矛盾 由上述所有证明可知，当测地数9 ( g ) = n 一2 时，g 有如下性质t ，存在两个顶点z ， 使得g 一( z ，9 兰恐，u k j ：u u 风。( 七2 ，鼠1t = 1 ，2 ，一，南) j ，当出口m ( g ) = 2 时，对g t 可作如下划分：g t = 五u a u m ，其中五= 如i y ( ) n ( 。) ，w 簪v ( ) ) ；k = ： u i y ( g t ) n ( g ) ， 譬( z ) ) ；a = i y ( g t ) ，u ( 。) n v ( 可) ) ，若 五0 ，则i m u a i 2 ；若m 0 ，则i k u a i 2 。并且满足不同时存在两个以上的连 通分支g ，q 使得五，巧，玛n 山均不为空集，或者m ，捣，k n 山均不为空集，j 当 d i o m ( g ) = 2 ，o ，可不相邻时，g 中有一点与o ，可都相邻且至多有两点与o ，可都相邻，矿 当出l ( g ) = 3 时，茁，譬必相邻，在g 一如，讣中至少存在两个连通分支，它们的顶点分 别都是z ，的邻居；对其余连通分支，若( z ) ny ( g t ) 0 ，则y ( g ) 垦( z ) ，对可该 性质同样成立 ( # ：) 当d t 岔m ( g ) = 2 ，z ，v 不相邻时，容易可证得这类图得测地数为竹一2 对于其他 出口m ( g ) = 2 且满足上述性质的图，对u y ( g 1 ) ，t 一z 必属于g ( g 1 ) u 。) j ，所以该 第二章：无向图的测地数 华东师范大学硕士论文 1 6 测地线上没有其他连通分支的顶点，同时g 。中的点最多只有两个在u z 上，但使用。作 为测地集中的点，所以g l 中的点都属于测地集，则9 ( g ) 礼一2 ，当出n m ( g ) = 3 时，因 为对于任意点 y ( g ；) ，由瓯的结构可知 为极点应用引理2 2 13 ，则g ( g ) 2 忆一2 。 另一方面，不考虑直径，取s = y ( g ) z ，可 ，吲= n 一2 ，而且j ( s ) 一y ( g ) 因此s 为 g 的测地集，放9 ( g ) n 一2 所以当g 符合上述性质时，9 ( g ) = n 一2 第三章图的上下测地数 在上一章中，我们主要研究了无向图的测地数，自然而然大家会关心测地数在有向 图中的情况g ，c h 盯t r a n d 和p z h a n g 在文献 1 4 】中首先将图测地数推广到有向图，并 在同篇文章中提出了g 的上下测地数的概念，分别使用如下记号来表示它们 9 一( g ) = m i n 伯( d ) ：d 是g 的定向图) ； 9 + ( g ) = m a x 如( d ) ：d 是g 的定向图， 在此基础上，g e r 盯dj c h a n g 和l i - d at 0 n g 等人在文献 1 5 】中，进一步提出了图测 地谱的概念，用记号s ( g ) 来表示，其中 s ( g ) = g ( d ) ：d 是g 的定向图) 在本章中，本文将着重介绍有关图上下测地数，图测地谱的一些知识，及我们在这方 面所得到的一些结果。 3 1 预备知识 在本章中，我们将介绍一些常见图的上下测地数对于一个礼2 ) 阶连通图g ， 显然2sg 一( g ) 矿( g ) 订，首先我们给出口一( g ) = 2 的一个充分条件 引理3 、1 1 1 4 对于一个佗( 而2 ) 阶连通图g ，如果g 有一条哈密尔顿路，则 口一( g ) = 2 当然我们可以非常容易证明，上述条件并非充要的，下图是一个反例 地 u 7 定义3 1 2 一个有向图d ，如果满足条件：只要u 口e ( d ) ，口叫e ( d ) 就有删 e ( d ) ，那么称d 是传递的( 加n s i 托口e ) 引理3 。1 3 【1 4 1 d 是一个a 平凡的礼阶有向图，9 ( d ) = n d 是传递的 1 7 第三章：图的上下测地数华东师范大学硕士论塞 1 8 如果g 是一个n 阶的完全二部图，我们可以容易证明在g 上能取到一个有向图d 是传递的，即9 ( d ) = n ，所以有以下定理 引理3 1 4 1 4 】如果g 是一个几2 ) 阶的完全二部图，那么旷( g ) 一札 根据上述引理，我们在下面将给出当g 是树，圈或者完全二部图时，图g 的上下测 地数值。 定理3 1 5 1 4 ( a ) 如果t 是一棵顶点数为n 2 ) 的树，并且该树有七个叶子， 贝0g 一( g ) = 七，夕+ ( g ) = n ( 6 ) 对于顶点数不少于3 的圈c _ ，圈的下测地数9 一( c k ) = 2 i 它的上测地数 九啦 n 一：裟萋： ( c ) 对于整数r ，s ( 2 r s ) ，完全二部图的上下测地数分别为 9 一( 群，。) = 2 ，g + ( 坼，。) = r + s 因为每一个完全图中都包含一条哈密尔顿路，所以由引理3 1 ，1 可知g 一( k ，) = 2 同 时，对于完全图能取到一个有向图写是传递的，即g ( 咒) = 扎，所以旷( ) = n 非常显然，对于两个图g 和h ， s ( g u 日) = 口+ 6 ：n s ( g ) ；6 s ( 日) ) 所以在本文中，有关图测地谱的问题我们也只考虑连通图对于一个n ( n 2 ) 阶连 通图g s ( g ) 2 ，3 ，n 接下来我们就来确定几类常见图的测地谱，首先给出在确定测地谱中非常有甩的两个引 理。 引理3 1 6 【14 一个有向图d 中，源和汇都属于该图任意一个测地集 引理3 1 7 1 4 】一个顶点数不小于2 的连通图g ，如果该图的顶点集y ( g ) 可以被 分割成r 个子集 z ) = ，k ，w = 白) ，使得对于v 口y ( g ) ，口位于z 一可测 地线；工= 茁o ，。1 ，孙= 可上，其中z k ( o i r ) ，那么就有2 s ( g ) 从前面的介绍中，我们可以了解到s ( g ) 2 ，3 ，n ) ，现在来给出几类使上述 等号成立的图类，首先我们先证明使上述等号成立的图类的存在性 定理3 1 8 【1 5 任意两个整数n ，m 满足l n 一1 m 暖，则必定存在有礼个 顶点m 条边的一个连通图g 使得s ( g ) = 2 ，3 ，亿) 第三章：图的上下测地数 华东师范大学硕士论文 1 9 由上述定理我们了解了s ( g ) = 2 ，3 ，n ) 的图的存在性，事实上一些常见 图的洌地谱都有这个性质，例如完全图，完全图去掉一条边得到的图j 厶一e ，完 全r 部图等，具体证明介绍可参阅文献【1 5 。但是并不是所有图的测地谱都有s ( g ) = ( 2 ，3 ，n ) ，大多数图的测地谱只是 2 ，3 ，礼) 的真子集。 定理3 1 9 1 5 如果t 是一棵顶点数为礼( n 2 ) 的树，并且该树有七个叶子。则 s ( 丁) = k ，+ 1 ，n ) 定理3 1 1 0f 1 5 对于顶点数不少于3 的圈g ，圈的测地谱 s ( c k ) = 3 ) u 2 s ：2 2 5 n ) 3 。2 关于图上下测地数的猜想 从前面部分的介绍可知，对于一些常见图例如树，圈，完全r 部图，完全图等等，我 们都可以得到9 ( g ) 矿( g ) 这样的结果，那么是不是所有的图都有这个性质呢? 吕长虹 在文献【4 1 中就提出了这样的猜想：对于任意一个图，9 ( g ) 矿( g ) 成立在同一篇文章 中，他还就这个问题做了一部分工作，下面一一介绍 引理3 2 1 4 如果g 是一个顶点数大于等于4 的连通图，那么矿( g ) 4 具体证明请参阅i 4 由该引理可知，对一个顶点数大于等于4 的连通图，如果9 ( g ) 4 ，9 ( g ) 矿( g ) 成立。因此本文继续这方面工作时，考虑了9 ( g ) = 5 的情况。 引理3 z ，2g 是一个顶点数太于等于2 的连通图，s 是图的最小测鲍集，若g f s 3 是 二部图，那么g ( g ) 矿( g ) 证明：因为g 是二部图，所以s 可吼划分为两个集合x ，y ，并且v 。可e ( g 【s ) 都有z x ，移y ，因此可以构造g 的定向d 如下；若z 管e ( g ) 扛v ( g ) ，翟y ) ， 令茁一；若z y e ( g ) ( 。x ，y ( g ) ) ，令。一；其余边的定向任意由该定向可 知，任意g 翻的顶点不是源就是汇，应用引理3 1 6 ，则9 ( d ) 旧。即g ( d ) g ( g ) 而雪+ ( g ) = m a x ( d ) ：d 是g 的定向图) ，所以矿( g ) g ( d ) 2 夕( g ) 。 一 引理3 2 3 【1 0 】g 是一个顶点数大于等于2 的连通图，s 是图的最小测地集，若g 翻 连通，则( g 吲) l s l 一1 ；( g 司) = 一1 当且仅当g f 翻= g 型j 厶 第三章：图的上下测地数华东师范大学硕士论文 2 0 证明；首先，显然( g c s l ) = 吲一1 当且仅当g s 】一g 垒蜀。若g 不是完全 图，则g l s 】也不是完全图所以在g 嘲中存在两点u ，口使得u 簪e ( g ) ，令d g ( 。) = ( g 【s 】) 。如果( g 司) = 吲一1 ，那么z 在u u 测地线上，且任意茗一，s 的测 地线长为1 ，即该测地线上无其他点，所以j ( 趴 。) ) = ( s ) = y ( g ) ，矛盾 引理3 2 4g 是一个顶点数大于等于2 的几阶连通图，s 是图的最小测地集，若 g l s l 连通并且9 ( g ) = 5 ，那么 g ( g ) 9 + ( g ) 证明：若g 兰风，则夕( g ) 矿( g ) 我们考虑g 不是完全图由引理3 2 2 可知， 令s 是图的最小测地集，若g 旧是二部图，那么9 ( g ) 矿( g ) 成立，所以只需证明 g 【s 含有奇圈时，9 ( g ) 旷( g ) 成立因为9 ( g ) = 5 ，所以g 司中所含的奇圈只能为 岛或者g 。 如果g 【司连通，那么由引理3 2 3 可知( g 【司) 3 此时考虑g s 1 ，可得到以下 几种情况。 情况一：( g c s l ) = 3 ；6 ( g 司) = 1 由顶点度与边数的关系，可知g 吲满足上述条 件有以下三种情况 此时构造g 的定向d 如下：对边u 仇e ( g ) ( i _ 1 ，2 ，5 ) 若i _ 2 ，5 ，则令u 一饥； 若i = 3 ，4 ，则令地一u ；若i - 1 ；扎s ，则令让一 l ；其余边的定向任意 由定向可知 2 ，u 3 ，m ，口5 都是源或汇，根据引理3 1 6 可得9 ( d ) 4 假设口( d ) = 4 ， 则，( 2 ， 3 ，u 4 ，u 5 ) ) 一y ( d ) 因此 1 位于仇一的有向测地线上，其中仉为源为 汇；而且地叼隹e ( g ) 因为仉u 2 ，m ，地口2 e ( g ) ，故 1 只能位于钝一佻的有向测地 线上，由d 的构造，可知u 3 一的有向测地线必定为地一t ，1 u 2 一地因为u 3 也e ( d ) ， 所以0 3 ”2 一比一 1 ”2 一”5 更短，矛盾 情况二：( g 吲) = 3 ；6 ( g 司) = 2 由顶点度与边数的关系，可知g 【s 1 满足上述条 件有以下两种情况 第三章：图的上下测地数 华东师范大学硕士论文 2 1 此时构造g 的定向d 如下：对边u 仉e ( g ) ( i _ 1 ，2 ，5 ) 若i _ 2 ，4 ，则令u 一仇； 若i _ 3 ，5 ，则令佻一u ；其余边的定向任意 由定向可知 2 ，u 3 ， 4 ， 5 都是源或汇，这些点都包含于有向图d 的测地集中。但 j ( 口2 ，u 3 ，啦，u 5 ) ) = u 2 ，u 3 ， 4 ，u 5 ) ，所以口1 隹，( 2 ，地，m ， 5 ) ，因此9 + ( g ) 5 ，即 9 + ( g ) g ( g ) 情况三：( g 司) = 2 ；6 ( g 翻) = 2 。由顶点度与边数的关系，可知g 吲满足上述条 件时即为既，见下图。 此时构造g 的定向d 如下：对边u 饥e ( g ) ( i _ l ，2 ，5 ) 若i - 2 ，4 ，则令u 一仇；若 i _ 3 ，5 ，则令哦一u ；其余边的定向任意由定向可知也， 3 ，地，都是源或汇。这些点都包 含于有向图d 的测地集中，所以g ( d ) 4 假设9 ( d ) = 4 ，因为蛳地，啦u 5 ， 3 2 e ( g ) ， 故v z 协( i = 2 ，3 ，4 ，5 ) 只能位于一u 2 的有向测地线上而在d 中，因为存在一 l 一吨， 故 5 一u 2 有向测地线长为2 ，因此。哦e ( g ) ( i = 2 ，5 ) 在g 中，令s 1 = 趴 1 ) ，可知 ，( s 1 ) = ，( s ) = y ( g ) ，与s 为最小测地集矛盾 定义3 2 5 两个图g ，h 之间的最短距离，用记号l ( g ，日) = m 饥 d ( u ，u ) 1u y ( g ) ， y ( 日) ) 表示 引理3 2 6g 是一个顶点数大于等于2 的礼阶连通图，s 是图的最小测地集，若 g 旧兰玛u 凰，l ( 坼，甩) = ，则对于任意两点缸y ( 坼) ， y ( 兀) 均有d ( u ，u ) = 第三章：图的上下测地数 华东师范大学硕士论文 2 2 k ，女+ 1 ，+ 2 中一个。特别地，若虬垡甄，即筑只有一个点口，那么任意一点 u v ( 坼) 均有d ( ， ) = 惫 证明：因为l ( 琢，甄) = ，所以存在两点锄y ( j 0 ) ，u o y ( 甄) 使得d ( 钍o ， o ) = 南， 并且对于任意两点札y ( 坼) ， y ( 玩) 都有d ( 让， ) 如果存在两点u y ( 坼) ， v ( 尬) 使得d ( u ，u ) 凫+ 3 ，不妨设为d ( u ，u ) = 七+ 3 易知在g 【s l 中存在路u u o u o u ， 可知该路长为k + 2 ，矛盾 当甄只有一个点u 时，因为l ( k ， ) = ，所以存在点让o y ( 厨) 使得d ( u o ，u ) = ，并且对于任意点吐y ( 墨) 都有d ( ，u ) 舟如果存在点趾y ( 坼) 使得d ( u ，u ) 岛+ l ，不妨设为d ( 缸，。) 一是+ 1 此时取s 1 = s 如。) ，因为乱“o v 为乜一砧测地线，所 以j ( 岛) = v ( g ) ，矛盾 定理3 。2 。7g 是一个顶点数大于等于2 的扎阶连通图，若g ( g ) = 5 ，那么 夕( g ) g + ( g ) 证明：若g 垡，则9 ( g ) 9 + ( g ) 我们考虑g 不是完全圉出引理3 ，2 2 可知， 令s 是图的最小测地集，若g 【s 】是二部图，那么g ( g ) 旷( g ) 成立，所以只需证明 g 旧含有奇圈时，9 ( g ) 9 十( g ) 成立因为9 ( g ) = 5 ，所以g 【剐中所含的奇圈只能为 q 或者晚因为引理3 2 4 ，我们知道在g ) 连通的情况下，9 ( g ) 矿( g ) 成立因 此我们接下来考虑g ) 不连通的情况 不妨设g 吲中的连通分支分别为g 1 ，g 2 ，g 女，此时g 旧有以下三种情况 情况一 对上述三图构造g 的定向d 如下所示；若伽2 e ( g ) ，则令缸一啦；若让地 e ( g ) ( i = 3 ，4 ，5 ) ，则令一札；若伽1 e ( g ) ，乱地( i = 2 ，3 ，4 ，5 ) ，则令u 1 一乱；其余边 定向任意 第三章：图的上下测地数 华东师范大学硕士论文 2 3 在这个构造中，口2 ，口3 ，饥，佻都是源或汇，因此9 ( d ) 4 。如果9 ( d ) = 4 ，则 1 必在 呲一忱或者佻一。2 的有向测地线上，不妨设在鸲一 2 的有向测地线上。由d 的构造可 知， 3 1 e ( d ) 且是唯一以 t 为终点的有向弧，所以地u ，必在 5 一 2 的有向测地线 上，即一地口l 一优，但是 3 ，都是源，与佻一”3 u 1 一 2 为有向路矛盾 情况二：在这种情况下，g 【s 1 由甄和 构成，见下图 1他 因为g 不是连通图，所以上( 口，峨) 2 由引理3 2 6 可知， 到甄任意点的距 离均相等 当工( ”，甄) = 2 时，若存在至少一点札y ( g ) 使得伽4 和伽1 中至少一个不属于 e ( g ) ，不妨设钍啦e ( g ) ，锃讥圣e ( g ) 对g 构造定向d 如下；若。口1 e ( g ) ，财令 口1 一z ；若。饥e ( g ) ，则令卫_ 啼地( i = 4 ，5 ) ；若z e ( g ) 且z 1 ，忱u 3 ，u 4 ， 5 ，则令 $ 一吨( i = 2 ，3 ) ；若u 2 地e ( g ) ，则令 2 一地；其余边定向任意。 在上述定向下，可知u 5 ，蛳为汇， 1 ，札为源所以令岛= 5 ，u 4 ，u 1 ，u ) ，显然& 互s 但是u 2 ，奶隹f ( s ) ，即f ( 岛) v ( d ) ，所以9 ( d ) 5 若v u y ( g ) u 1 ，口2 ， 3 ，u 5 ) 都有“地e ( g ) ( i _ 1 ，2 ，3 ，4 ，5 ) 此时对g 构造定 向d 如下：若。仇e ( g ) ，则令饥一z ( 江1 ，5 ) ；若伽4 e ( g ) ，则令茁一地；若 z 饥e ( g ) 且z 1 ， 2 u 3 ，似，魄，则令o _ 他( i 一2 ，3 ) ；若讹u 3 e ( g ) ，则令魄一抛； 其余边定向任意 在该定向下， 1 ，地为源，钿4 为汇，且f ( 啦，啦，佻) ) y ( g ) ，所以9 ( d ) 4 若 9 ( d ) = 4 ，则最小测地集s 为 1 ，啦，坞，u ) ， u 1 ， 4 ，w 5 ， 2 ) 或 u 1 ，啦，地， 3 ) 当s = 1 ， 4 ，u ) 时，口1 4 ， 1 “，u 4 ，u 5 “e ( g ) ，因此地，位于铝 4 测地线 上又因为一u 一啦为u 5 一u 4 有向测地线，所以地口2 e ( g ) ，所以l ( ，甄) ；1 ，矛 盾 当s = 如l ，勘4 ，u 5 ，”2 ) 或如1 ，魄 时情况类似，我们只证s = d 1 ，暂2 ) 在 这种情况下，忱位于一口2 或一饥的有向测地线上，与前一种情况类似可得矛盾 当l ( ，峨) 3 时，不妨设工( 口，如) = 3 ，则至少存在一点“y ( g ) 使得u 仇芒e ( g ) ( i = 1 ，2 ，3 ，4 ) 此时对g 构造定向d 如下t 若。讧e ( g ) ，则令仇一岱( i = 1 ，5 ) ；若 z 4 e ( g ) ，贝0 令z 。啦；若。讪e ( g ) 且z l ， 2 饥，讪，则令o1 ( i = 2 ，3 ) ； 第三章?图的上下测地数华东师范大学硕士论文 2 4 若u 2 3 e ( g ) ，则令 3 一也；若z u e ( g ) ，则令。一“；若。可e ( g ) ，其中 。，g ( 喵) ，则令z g ；其余边定向任意 因为u 1 ，为源，u 4 ，u 为汇，所以令岛= ，口l ，u ) ，若，( 岛) = y ( g ) ，则u 2 ，协 位于u 1 一u 或一讥的有向测地线上，而由z 可e ( g ) ，其中z 札，) ，令z f 的定向构造可知口5 一 4 的有向路不存在因此吨， 3 位于饥一u 上，必为 1 2 如地一“ 形式因为，珏为汇，故矛盾。 情况三 若存在z y ( g ) 使得。钟1 莹e ( g ) ，而z 与岛，配其余点都相连那么构造定向d 如 下t 若u 仇e ( g ) ( i _ 1 ，4 ) ，则令地一札；若u 仇e ( g ) ( i - 2 ，3 ) ，则令仳一地；“e ( g ) ( u ) ，则令u 一；其余边任意定向在该定向中，因为仉一z 一 2 为长为2 的 u 一 2 测地线，同时口1 一u 3 间经过口5 的有向路不存在，所以口sgj ( 虮，忱，u 3 ，讹) ) ，故 9 ( d ) 5 若存在茁y ( g ) 使得铡1 ，。 4 隹e ( g ) ，则在上述构造的定向中添加条件：若 o g e ( g ) ，则令盘一可知此时u 1 ，m ，茁为源，啦，地为汇，所以9 ( d ) 5 现在考虑若对v o y ( g ) 都有。饥e ( g ) ( i = 1 ，2 ，3 ，4 ，5 ) 那么构造定向d 如下：若 t 工e ( g ) ( i = 1 ，4 ) ，则令一缸；若t 溉e ( g ) ( i = 2 ，3 ) ，则令乜一q ；髓e ( g ) ( u u 2 ) ，则令饥一u 5 ；其余边任意定向可知u 1 ，蛳为源， 2 ，口3 为汇在该定向中存 在长为2 的 3 一也测地线地一茹一口2 和长为2 的 1 一u 3 测地线u 1 一茹一地因为 l ( q ，) 2 ，所以口5 4 ， 3 e ( g ) ，因此 4 一 2 经过0 5 的路长不小于3 ，同理u 1 一u 3 经过 5 的路长不小于3 ，所以口5 隹j ( ”1 ，u 2 ，u 3 ，u 4 ) ，故9 ( d ) 5 。 综上所述，因为目+ ( g ) 9 ( d ) ，所以当g ( g ) 一5 时，g + ( g ) g ( g ) 证明了g ( g ) = 5 的图对于吕长虹的猜想成立后，我们接着考虑其他一些图类对该猜 想的支持在上一章节中，我们确定了口( g ) = n 一1 的图的结构，所以我们可以从图的 结构出发构造g 上的定向图d ，从而证明这类图对于猜想也成立我们用记号矗表示 k ：上传递的有向图。 定理3 2 8 若g 是一个n 阶2 ) 连通图，如果口( g ) = n l ，那么g ( g ) s ( g ) 证明：因为9 ( g ) = n 一1 ，由定理2 2 1 2 可知，g 竺日v 甄，其中甘= 风。u 托，u u 耳s 。( 2 ，s f 1 对t = 1 ，2 ，) 令y ( 硒) = t ) 第三章：图的上下测地数华东师范大学硕士论文 2 5 现在我们在g 上构造定向图d ：将g y ( 咒，) u0 ) 定向成为正，+ ，并且在疋，+ 1 中e 成为源；又将g ( k 。：) u0 1 定向成为疋抖l ，并且在正。+ l 中成为汇；同时将 g i y ( 甄；) u t ) 】定向成为疋m ( i 3 ) ，并且在正汁- 中成为源或者汇。 令s = y ( d ) 0 ) ，若y ( 虬。) ，u y ( 虬。) ，那么u 抛是一条u 一 测地线。因 此，( s ) = y ( d ) 而且9 ( d ) n 一1 假设9 ( d ) n l 并且s 是d 的最小测地集。设在y ( g ) 中存在一个顶点f 车s ， 那么t 位于一条z 一3 ，测地线上，其中工，s 不妨设t j 毛。因为对于每个疋+ l ( i 1 ，2 ，k ) ) ，t 不是源就是汇，所以茁，至少有一点在正，+ 1 中 如果x ，y v ( l ，+ 1 ) ，因为e ，+ 1 是传递的，所以z 一冒测地线长为1 ，所以t 不在 z g 测地线上，如果。y ( 瓦，+ 1 ) ，y ( 咒，) 0 1 ) ，由d 的构造可知，正，+ 1 和毛+ 1 是由t 连接起来的，所以t 位于。一可测地线上，茁一t l t 一可又因为e 。+ 1 是传递的，z t 测地线长度也只为1 ，类似的t 7 不在茁一t 测地线上，矛盾故夕( d ) = g ( g ) = n 一1 ，即 9 ( g ) s ( g ) 对完全图2 ) ，有条哈密尔顿路，因此9 一( k 。) = 2 我们用三k 表示有 一条有向哈密尔顿路的k ，的有向图，可知g ( 上k ) = 2 定理3 2 9 如果g 望日v 硒，其中日= 琏。u 瓦：u u 。( 2 ，氐三1 对 i = 1 ，2 ，- ，七) ，男口么9 + ( g ) = n ，g 一( g ) = = 女。 证明：构造g 上的定向图d 1 如下；将g ( 爆。) u ( t ) 10 = 1 ，2 ，、) 定向成为 瓦，并使t 成为源点假设存在点 位于一条。一y 测地线上，并且d d 。( z ，y ) 2 因为正l + 1 是传递的，任何以t + 1 中的测地线的长度都是1 所以，丑和不在同一个 虬m 中从d 1 的构造可知，以汁1 和咒r 1 是由t 连接的，因此t 位于某条。一测地 线：z t 一管，与t 是源矛盾由上可知，对每一个口y ( d 1 ) ，u 属于d