（运筹学与控制论专业论文）关于图测地数界的研究.pdf

m a s t e rd i s s e r t a t i o no f 2 01 1 | f i l f l i i f l i | f | i | i | i | i i i f i i f i | f f i i i f f f j j i f y 19 0 3 0 6 6 s c h o o lc o d e ：1 0 2 6 9 a c a d e m i cn u m b e r ：510 8 0 6 010 8 2 e a s tc h i n an o r m a lu n i v e r s i t y o nt h eb o u n d so fg e o d e t i cn u m b e r so f d e p a m n e n t ： m 旬o r ： s u b j e c t ： s u p e i s o r ： g r a p h s d e p a r t i n e n to fm a t h e m a t i c s o p e r a t i o n a lr e s e a r c ha n dc y b e m e t i c s g r a p ht 1 1 e o 巧a n di t sa l g o r i t h m s p r o f e s s o rc h a n g h o n gl u m a s t e rc a n d i d a t e ： g u a n g l i a n gs h i 2 0 1 1 5 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文关于测地数界的研究，是在华东师范大学攻 读硕劫博士( 请勾选) 学位期间，在导师的指导下进行的研究工作及取得的研究成 果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研 究成果。对本文的研究做出重要贡献的个人和集体，均己在文中作了明确说明并表 示谢意。 作者签名：盈刍塑。日期么必翊2 园 华东师范大学学位论文著作权使用声明 为于测地数界的研究系本人在华东师范大学攻读学位期问在导师指导下完 成的硕博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学所有。本人 同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相关机构 如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学位论文 进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国博 士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版， 采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部 或“涉密”学位论文幸，于 年 月 日解密，解密后适用上述授权。 2 不保密，适用上述授权。 学位做作者虢殖聊鼢坦乙 审定过的学位 效) ，未经上 位论文，均适 厄丁既硕士学位论文答辩委员会成员名单 姓名职称单位备注 任韩 教授华东师范大学数学系 主席 郭军伟副教授华东师范大学数学系 杜若霞副教授华东师范大学数学系 华东师范大学 关于测地数界的研究 摘要 连通图g 中的任意两点甜和u 一条甜一，测地线是指“，v 两点问的最短路令 厶，表示位于“一v 测地线上所有点的集合对于子集s ，令耶) = u 玑瞄“，力，如果 巩9 ) = h g ) ，则我们称s 是g 的测地集把图g 测地集的最小基数叫做g 的测地数 同样我们可以相对应的定义有向图d 的相关概念对图g 的所有边给定一个方向后的 图称为图g 的定向图，我们称s ( g ) = 反d ) ：d 是图g 的定向图 为图g 测地数的谱 旷( g ) = m a ) 【s ( g ) 为图g 的上测地数本文讨论了无向图以及有向图的测地数，主要内 容如下： 在第一章中，我们简单介绍了图测地集研究的背景与已有的一些结果 在第二章中，我们研究上测地数下界的一个猜想：如果图g 是一个直径为d 最小 度为艿的非平凡的连通图，则有矿( g ) d + 艿证明了这个猜想对无三圈图，( g ) 3 的图以及单位区间图是正确的 在第三章中，我们先给出了二部图与完全图笛卡尔积上测地数的下界并且研究 树与 的笛 华东师范大学关于测地数界的研究 a b s t r a c t f o r 咖v e r t i c e sz ，a n dvo f a g m p hg ，a 甜一，g e o d e s i ci sas h o r t e s tp a t hb e t w e e n 甜a n d v l e t 厶vd e n o t et h es e to fa 1 1v e r t i c e s1 y i n go na 甜一1 ，g e o d e s i c f o ras i l b s e ts ，1 e tj ( s ) d e n o t et h el l n i o no f a l l 厶，f o r “，1 ，s t h eg e o d e t i cs e ti sss u c h 也a t 几s ) = h g ) t h e g e o d e t i cn u m b e r 反g ) o fa 伊a p hg i st h em i i l i m u mc a r d i l l a l i 妙o fas e tsw i t h ， ) = 以g ) f o rad i g r a p hd ，也e r ei sa n a l o g o u st e m l i n 0 1 0 9 yf o rt h eg e o d e t i cm l i n b e r 反d ) t h eg e o d e t i c s p e c t m mo f gi st h es e ts ( g ) = 甙d ) ：d i sa no r i e n t i o no f g t h eu p p e rg e o d e t i cn u m b e r i s 矿( g ) = m a xs ( g ) t l l ep u r l ) o s eo f t h i st h e s i si st 0s t u d yt h eb o l m do f 旷( g ) a i l d 甙g ) f o r c o 皿e c t e dg r a p h sg t h ef o l l o w i n ga r et h em a i nr e s u l t s ： i i lc h 印t e i l ，t h eb a c k g r o u i l da n dr e s e a r c hp r o g r e s so f g e o d e t i cs e ta r es 曲p l yi l l u s 仃a t e d i nc h 印t e r2 ，、张s t u d yac o n j e c t u r eo nt h el o w e rb o u n do ft h eu p p e rg e o d e t i cn u m b e r ：i f gi san o n t r i v i a lc o n n e c t e dg r a p ho f d i 锄e t e rda nm i n i m _ i 】瑚d e 黟e e 占，t h e ng + ( g ) d + 占a n d w ep r o v et h a ti ti s 仃u ef o rt r i a n 9 1 e - 丘e e 鲫h s ，筝a p h sw i t h 3a n du n i ti n t e r v a l 鲈a p h s i nc h a p t e r3 ，w ef i r s to b t a i nt h el o w e rb o u n do ft h eu p p e rg e o d e t i c 肌m b e ro ft h ec a r t e - s i a np r o i l u c t so fc o m p l e t eg r a p ha n db i p a r t i t eg r a p h t h e nw ei n v e s t i g a t eac o n j e c t u r eo n t h er e l a t i o nb e t 、) l ，e e nt 1 1 eu p p e rg e o d e t i cn u m b e ra l l dg e o d e t i cn u m b e r ： f o ra n y 鲫hg ， 矿( g ) 甙g ) w ep r o v et h a tb o t h 矿( g ) 甙g ) a n d 矿( g ) d + i s 仃u e f o rt h ec 绷e s i 觚 p r o d u c t so fc o m p l e t eg r a p ha n d 仃e ：e w ea l s oi 1 1 v e s t i g a t et h er e l a t i o nb e 锕e e n 甙g ) a n dd + f o rt h ec 硼e s i a np r o d u c t so fc o m p l e t eg r a p ha n dt r e e i nc h 印t e r4 ，w eo b t a j nt h eg e o d e t i cn u m b e ro fb l o c kg r a p h sa n dt h e n 血v e s t i g a t et 1 1 e b o u n do f 矿( g ) f o rb l o c kg r a p h s k e y w o r d s ：g e o d e t i cs e t ；g e o d e t i cn 啪b e r ；u _ p p e rg e o d e t i cn u m b e r ；d i s t a n c e i i 华东师范大学 关于测地数界的研究 目录 第一章概述1 1 1 图论的一些基本概念1 1 2 图测地数的相关概念与研究进展2 1 3 本文的主要结果简述5 第二章上测地数下界的研究7 2 1 对无三圈图的上测地数下界的讨沦7 2 2 最大度不超过3 的图上测地数的下界1 0 2 3 单位区间图上测地数的下界1 3 第三章图的笛卡尔积的测地数1 5 3 1 预备知识1 5 3 2 图与完全图的笛卡尔积的测地数1 7 第四章对块图测地数集测地数的讨论2 2 第五章总结2 7 参考文献3 0 致 射3 3 第一章概述弟一早慨途 图论是现代数学中的一个重要分支，当然图论作为一门数学学科的重要作用，不仅 是理论上的，更是体现在我们生活之中现实世界中的许多事例用图来描述都是很方 便的，比如说点表示人，连线表示两个人之间为朋友关系，则我们整个世界就成了一个 图而且图论的起源就是源于现实生活中的实际问题：1 7 3 6 年欧拉( e u l e r ) 解决了著名 的格尼斯堡七桥问题但是真正推动图论发展的是电子计算机的产生，使得图论在短时 间内有了比较完整的理论体系随着深入研究以及许多实际问题的需要，图论已经有了 很多分支总体来说以研究图论的工具来看，可以分为：代数图论，结构图论，极值图论， 图论算法，随机图论等不论借助什么工具来研究图论，我们基本都是建立在图的结构 特征的基础之上，从而对图的一些结构性性质的研究尤为重要，本文主要介绍了图的测 地数方面的研究以及本人在这方面所做的一点相关工作 1 1 图论的一些基本概念 对于一个图g ( 我们也称其为无向图g ) 我们通常用g = ( k 日来表示，其 中y = 以g ) 是图g 的顶点集( v e r t e xs e t ) ，e = e ( g ) 为图g 的边集( e 电es e t ) ， 图g 顶点的个数i 以g ) i 称为图g 的阶( o r d e r ) 如果边p = 洲e ( g ) ，则我们称p 关 联甜和称“和v 是边p 的端点( e n dv e r t e x ) ，并称“和v 是邻接的( a d j a c e n t ) ，我们 还称“是，的邻居( n e i 曲b o r ) 或者v 是甜的邻居( n e i 曲b o r ) ，图g 中与顶点v 相关连的 边数称为v 的度( d e g r e e ) ，记作趣( v ) 或吠v ) ；( g ) = m a 】【 烈v ) ：v 联g ) l 和6 ( g ) = m i n 吠力：v 以g ) 1 分别表示图g 的最大度( m 觚i m 哪) 和最小度( m i n i n l a ld e g r e e ) 关联于同一点的两条边也称为邻接的边( a d j a c e n te d g e ) 并称图g 中与任一顶点 集s 相邻接的顶点的集合为顶点集s 的邻集，记作g ( s ) ，端点重合为一点的边称 为环( 1 0 0 p ) ，端点相同的边称为平行边0 a r a l l e le d g e ) 或者重边( m u l t i p l ee d g e ) 无环并 且无重边的图称为简单图( s i m p l eg r a p h ) 图g 中有限个顶点和边得交替序列形= v o e l ，l e 2 屹钰v 七，其中白e ( g ) ，f = 华东师范大学关于测地数界的研究 1 ，2 ，后，v ，h g ) ，= 0 ，1 ，2 ，七且白= 睢l ，则称形是图g 的一条道 路( w a l k ) 顶点和垤称为形的端点，顶点m 称为形的内点，后为形的长；各边 相异的道路称为迹( 仃a i l ) ；内部点相异的迹称为路( p a t h ) ；连接甜，v 两点之间边数最少 的路成为”，v 两点之间的距离( d i s t a l l c e ) ，我们称图g 中所有点之间距离的最大值为g 的直径( d i a n l e t e r ) 当我们为图g 的每条边都设定一个方向时，我们称此图为有向图d ( d i 伊a p h ) ，此 时有向边“，的方向为从“指向v ，我们称其为弧茄对于有向图d ，进入顶点1 ，的边数 称为v 的入度( i 1 1 d e g r e e ) ，记作矿( 力；离开顶点1 ，的边数称为1 ，的出度( o u t d e g r e e ) ，记 作矿( d 称d 中所有出度为0 的点为汇( 顶) 点( s 址) ，而称d 中所有入度为o 的点 为源( 顶) 点( s o u r c e ) 如果对于d 中每一对弧黟，都有弧乏e ( d ) ，则我们称有向 图d 是传递( 咖s i t i v e ) 的 设两个图g 和鼠若坎明以g ) ，e ( 印e ( g ) 且日中边得重数不超过g 中 对应边的重数，则称h 是g 的子图( s u b g r a p h ) ，记作日g ；若日g 且坎印g 以g ) ，则称日是g 的生成子图( s p 猢i n gs u b g r a p h ) 设u 以g ) 且u o ，以u 为 顶点集，以两个端点均在u 中的全体边为边集的g 的子图，称为u 的诱导子 图( i n d u c e ds u b g r a p h ) ，记作g 明如果h g ) 的一个子集s ，使得g 陋】是一个完全图， 则称s 为g 的一个团( c l i q u e ) 如果顶点v 的邻集( 1 ，) 的诱导子图g ( v ) 】是一个 团，则称v 为极点( e x t r e m ev e r t i c e s ) ，记图g 中所有极点组成的顶点集为e 坎g ) 图g 中相互之间没有边相连的点我们称为图g 的独立集 设甜和，是图g 的两个顶点，若在g 中存在一条“一v 路，则称z ，和v 是连 通的( c o 衄e c t e d ) 若图g 中任何两个不同的顶点均是连通的，则称图g 为连通 图( c o 彻e c t e d 鲫h ) 本文中讨论的都是简单图，现在我们先介绍几个简单图的概念 如果图g 的每一对不同的顶点之间都有一条边相关联，我们称图g 为完全 图( c o m p l e t eg r a p h ) ，记作我们称顶点集是有两部分不相交的独立集组成的图为二 部图( b i p a n i t eg r a p h ) 连通的无圈图称为树( t r e e ) 树中顶点度数为l 的点称为树的叶 子( 1 e a f ) 只有两个叶子点的树，我们也称其为路( p a t h ) 1 2 图测地数的相关概念与研究进展 对于任意的两点x ，y s ，s 为度量空间力的点集，每条连接五y 的最短路( 曲 线或弧) 都完全位于s 中，则称点集s 为度量空间的凸集点集s ( c 的凸包阻】是在 2 华东师范大学关于测地数界的研究 z 中包含么的最小凸集或者包含彳的所有凸集的交凸集是几何学，拓扑学以及函数 分析等的基本概念b o i u l e s e n 和f e n c h e l 的书中指出：凸图形在几何学中已经起到了十 分重要的作用，参见文献 3 】由m i i 岫w s k e 创建的一个恰当的工具被借用来处理凸区 域和几何问题，已经得到了广泛的应用 在图论中的度量空间就是( 坎g ) ，力，其中以g ) 是指连通图g 的所有顶点的集 合，m ，力( 或者简记为d ) 是指两点之间的距离( 在图论中指的是x y 之间的最短路 的长度) ，我们也称这种长度为m ，力的x y 路也称为工一y 测地集在图论中，如果 对于彳中的任意两点，每一条x y 测地线上的点都完全位于彳中，那么连通图的点 集彳就是凸集显然，以g ) 是一个凸集点集彳坎g ) 的凸包阻 是最小的凸集 b u c k l e y 和h a r a 巧的书 4 中讨论了图的凸性，在 2 2 中h a r a 巧和n i e m i i l e n 对图 的凸性也有所研究而图的凸数是由e v e r e t t 和s e i d m a n 引入的并在 8 和 1 3 中有 了比较深入的研究在此研究的基础上，在文献 1 中，引入了反应图的结构性特征 的参数一测地数在文献 6 ，9 - 1 1 】中有了更深入的研充g c h a 咖l d 和p - z h a n g 在文 献 1 3 】中把这个概念又推广到了有向图当然这些研究基本上都是在探究图的结构性 质的基础之上得出了一些比较好的结果，最近在参考文献【1 7 】中运用了概率方法，给 出了很好的结果，这充分说明了概率方法在图论中是一个很好的方法 连通图g ( 有向图否) 中，一条“一v 测地线( g e o d e s i c ) 是指点，v 间的最短路( 从“到， 的最短有向路) 令“，表示材一，所有测地线上点的集合对于以g ) ( 石) 的非空 子集s ，令尼 ) ( 岛) = u 。，v e s ，( z ，v ) ，如果如 ) ( s ) ) = h g ) ，则称s 是g ( 西) 的测 地集( g e o d e t i cs e t ) ，并把测地集的最小基数称为g ( 否) 的测地数( g e o d e t i cn u m b e r ) ，记 为甙g ) 羽) ) 起初这些概念只是对于无向图而言的，后来c h 抛d 和z h 趾g 在 1 3 】中把这些 概念由无向图推广到了有向图我们前面已经指出，有向图是在无向图的基础上，为每 一条边定后得到的，定向后的有向图称为原无向图的一个定向图( o r i e n t e dg r a p h ) 对于 有向图，我们在上面已经类似的给出了其测地线，测地集和测地数等概念，但是需要指 出的是在有向图中，z ，一v 测地线是指由点甜指向点1 ，的一条有向通路，而v 一甜是指 由点v 指向点”的有向通路，从而甜一v 测地线和，一z ，测地线是两条完全不同的有向 路最( “，v 1 ) 表示所有位于甜一v 测地线和v 一甜测地线上的顶点的集合我们定义： s ( g ) = 烈功：d 是图g 的一个定向图l 为g 的测地谱( g e o d e t i cs p e c t n 蛐) 而图g 的上测地数( u p p e rg e o d e t i cn u n l b e r ) 我们 3 华东师范大学 关于测地数界的研究 定义为矿( g ) = m a ) 【s ( g ) ；同样图g 的下测地数( 1 0 w e rg e o d e t i cn u m b e r ) 我们定义 为g - ( g ) = m i n s ( g ) 如果甙否) = g - ( g ) ，则我们称图否为g 的最小谱定向( m 蛐m s p e c 仃u mo r i e n t a t i o n ) 如果双否) = 矿( g ) ，则我们称图否为g 的最大谱定向( m a x i i l l u m s p e c 仃l l mo r i e n t a t i o n ) 下文中出现的概念以及符号要是还没有介绍的，请参加相关章节内容的介绍，那里 都已经一并给出本部分相关概念参考自文献 10 ，1 3 ，2 4 ，3 0 ，3 2 和 1 9 等 下面我们介绍下测地集测地数等相关研究的进展，前面已经指出，测地集和测地数 等概念源于经典数学中凸集等概念向图论学科的推广，先是被引入了无向图，接着又 被从无向图推广到了有向图现在关于这些内容的研究已经有了很大的进展，特别是 是g c h 栅d ，f h 锄叮和p z h a n g 等做了许多基础性的工作，得到了一些很好的结 果，下面我们作相关介绍 定理1 1 ( 1 0 ) g 中任意一个测地集均包含g 中的所有极点 定理1 2 ( 1 0 ) 对于甩阶完全图瓦，树丁，以及完全二部图巨。s 2 ) ，分别有甙如) = 胛；反丁) = 必d ；氧如) = 所切 j ，4 定理1 3 ( 1 3 ) 令d 是一个阶数至少大于3 的有向图，则d 的每对顶点都是d 的测 地集的充要条件是d 是一个有向圈 定理1 4 ( 1 3 】) 对于任意的两个正整数七和聆都存在一个测地数为七的，l 阶有向图 定理1 5 ( 【1 0 ) 对于每一个阶数至少为3 的连通图g ，都有矿( g ) 矿( g ) 定理1 6 ( 1 3 】) 对于任意的两个正整数胛和所，当1 刀一1 历( ；) 都存在一个阶数 为栉和边数为m 的连通图g 使得g ( g ) = 2 定理1 7 ( 1 3 ) 对于任意的两个正整数刀和所，当l 刀一l m ( ：) 都存在一个阶数 为玎和边数为m 的连通图g 使得矿( g ) = 当然上面这些结果都是特殊性质图的测地数的大小，我们可能无法确定一般的测 地数的准确的表达式或者测地谱的准确范围，我们可以研究一般图的测地数的界，从而 得出一些新的结论还有当我们可以求出一个测地谱的范围，但是是不是这个上下界范 围之内的所有值都可以由这个图进行定向得到呢? 如果不是都可以取到，具体有哪些 值可以取到，哪些值取不到呢? 这些尚未解决的问题都需要也值得我们去探讨下面的 两个定理是有关有向图的测地谱的结果 定理1 8 ( 6 ) 对于任意的两个正整数栉和m 当1 肛一1 所( ：) 都存在一个阶数 为”和边数为所的连通图g 使得s ( g ) = 2 ，3 ，玎1 4 华东师范大学关于测地数界的研究 定理1 9 ( 6 ) 对于刀阶完全图为，圈g ，树丁以及完全，部图h ，蜥( ，z l ，z 2 ，佛 2 ) ，分另i j 有s ( ) = s ( 局e ) = s ( 局k 。脚) = 2 ，3 ，刀 ，s ( g ) = 3 u 2 占：2 2 s 门) ，s ( r ) = r ) ，刀l ；甙墨。) = m 加 s ，4 上面这些结果基本上都是完全从图的结构性质方面研究得到的，在文献 1 7 中把 概率方法用到了图的测地数界的确定之中，得到了如下的定理： 定理1 1 0 ( 1 7 】) 如果图g 是一个围长大于等于4 厅的图，最小度至少为6 的刀图，则我 们有以下结论成立： ( i ) 甙g ) 疗d + 6 ( 1 一p ) ) 哮+ - 一 一1 ) ( 1 一p ) 6 哮+ 1 1 p 为任意实数且p ( o ，1 ) ( i i ) 娜刀等箬 一1 ) 竖拦；+ l 1 3 本文的主要结果简述 本文主要是关于华东师范大学数学系吕长虹教授 2 4 】的两个关于上测地数下界的 猜想的研究情况，并且还探讨了块图与图的笛卡尔积的测地集方面的相关内容首先文 献 2 4 】提出了如下猜想( 注：本文中我们均称此猜想为猜想一) ，即 ； 猜想一：如果图g 是一个直径为d 最小度为6 的非平凡的连通图，则有矿( g ) d + 6 这个猜想是在 2 4 】中一个定理的基础上提出来的，定理如下： 定理1 1 1 如果图g 是一个直径为d 的连通图，则有 矿( g ) d + 1 ， 并且当且仅当g 是一条路r 时，矿( g ) = d + 1 由我们前面介绍的一些定理可知，这个猜想对完全图，二部图，完全r 部图等都是 正确的在本文中我研究了无三圈图，块图，单位区问图等的上测地数的下界，证明了 该猜想对于这些图是正确的下面介绍证明中需要用到的引理以及结论 5 范大学关于测地数暴的研究 1 7 ( 1 3 】) 任何有向图d 的测地集都包含d 的所有源点和汇点 用反证法，假设d 中存在源点或者汇点不包含在d 的一个测地集s 中，不妨设 不失一般性，我们假设甜为源点 由于z ，不在s 中，从而存在一条点1 ，一w 测地线，包含点“，也就是存在一条有向 路r 。上面的点依次为： 1 ，= ，l ，嵋l ，甜，v h l ，= w 显然点甜的入度最少为l ，这与“为源点矛盾，假设不成立，原结论成立 口 现在介绍本文部分证明中经常要用到的一个算法：广度优先搜索( b r e a d t h f i r s t s e a r c h ) 广度优先搜索是一个重要的算法，它先选定图g 中的一个顶点”为根点，然后 以到点甜的距离为依据，找出图g 的每一个顶点 这个算法，无论是在图论中还是计算机等科学中都有着广泛的应用设连通 图g 的直径为d 且政d = 么z ，v 以g ) ，则我们以z ，点为起点对图g 进行广度 优先搜索，可以得到g 的一棵生成树丁我们可以按照生成树中点到甜的最短路长 度把g 中的点分成d + l 部分记到点甜的最短路长为f 的所有g 中的顶点的集合 为巧，o f 么则= ” ，1 ，乃同时存在一条以z ，v 为端点的路上面的点一次 记为：“= v o ，v 1 砌= 1 ，同时有n 所= v f ，其中0 f z 此外，在 2 4 中还提出了关于矿( 回与反回之间大小关系的猜想( 注：本文中我们 均称此猜想为猜想二) ，即 猜想二：对于任何的图g 都有矿( g ) 烈g ) 董琳、吕长虹和王晓等人对这个猜想做了些探讨，得出了对于部分特殊图是正确 的，本文在第三部分介绍了这方的工作以及本人所得到的一些结论在第三章，我们首 先给出了二部图与完全图的笛卡尔积的上测地数的界并证明了猜想二对于r ( 完 全图与树的笛卡尔积) 是正确的，还验证了完全图与树的笛卡尔积对与猜想一也是正 确的，并且讨论了图的笛卡尔积的测地数与其直径和最大度的和之间的关系 在第四部分给出了块图的测地集测地数，并且证明了块图时满足猜想一的，给出了 块图的上测地数的范围 显然，图的测地数满足奴g u 印= 甙g ) + 甙，从而我们以下面所讨论的内容都限 于连通图 6 第二章上测地数下界的研究 由前面部分的介绍可知，对于完全图，圈，树以及完全r 部图的测地数，测地谱都 得到了确切的数值，从而甙g ) ，矿( g ) ，矿( g ) 等都完全的确定下来了，但是对于一般的 图，这些参数都还没有确定下来，或者说还没有一个确切的表达式可以表示或者得到一 个确切的数值，所以研究它们的界还是有必要的本部分主要介绍了矿( g ) 的下界的相 关情况，在前两节给出了矿( g ) 对于无三圈图与最大度不超过3 的图关于参数d + 的 下界，进而说明了猜想一对这两类图是正确的，第三节证明了单位区间图也是满足猜想 一的 2 1 对无三圈图上测地数下界的讨论 首先介绍一个概念：若图g 的任何导出子图中都不含c 3 ，则我们称图g 为无三圈 图( t r i a n g l e 1 j r e e 舭p h ) 对于无三圈图的上测地数，我们有以下定理 定理2 1 如果图g 是最大度为和直径为j 的连通图，并且不舍三圈，那么 矿c 回 ；：会一。霎裳蔫窘，点不在其中一条直径上； 证跚( 1 ) 证明存在最大度点不在其中一条直径上的情况 不失一般性，不妨设最大度点w 不在直径这条路上，由于图g 的直径为z 从 而存在两点z ，以g ) ，使得以z ，v ) = z 以甜点为起点，对图g 进行广度优先搜 索，得到g 的一棵以“为根节点的生成树r ，令为在丁中第f 层的所有点的 集合，f = 0 ，1 ，吐其中根节点“为唯一一个位于第o 层的点，v 位于第j 层显 然有以下事实成立：点z ，和，之间存在一条长为d 的路( 记为厶) ，其上的点依次 为“= v o ，v l ，切= v ，则有nk = u ，o f z 我们按以下的顺序与规则对图g 进行定向： 一、对所有与只。中点相连接的边进行定向首先，对于上下标为偶数的点u ， 将其相邻的边的方向标为由u 指向其邻居，从而定向后为源点；对于上下标为奇数 的点v ，若其邻边还未定向的，将其定向为由v ，的邻居指向v ，0 f ，z 7 华东师范大学关于测地数界的研究 二、与点w 的所有邻居相邻的边还没有定向的边按照以下规则定向： 不失一般性，我们假设w 圪中，且尼为偶数，从而定向之后为源点下面分情 况讨论： 情况一：价k e ( g ) ，令w ，( w ) ，且w ，魄 如果w ，雌l e ( g ) 或者w ，w “l e ( g ) ，由于g 为无三圈图，所以w ，2 岳 e ( g ) 或者y 扣2 e ( g ) 从而我们将w j 还未定向的邻接边定向为从w f 指向其所有邻 居点 如果w f 愀一l 仨e ( g ) 且w f 愀+ 1 隹e ( g ) 则将嘶还未定向的邻接边定向为从其邻 居指向w f ，( 如图2 1 所示) 图2 1 情况一定向后的图 情况二：眦岳e ( g ) 由于g 为无三圈图，我们可以通过对w 所有邻居的邻接边定 向后，使得w 的所有邻居为汇点，并且此时w 为源点( 如图2 2 所示) 三、对g 中还未定向的边进行任意方式的定向至此，图g 的定向全部完成，定向 后的图记为d 我们断言：g ) d + 讨论如下： 对于情况一，如果，愀一l e ( g ) 或者愀+ l e ( g ) ，则w ，为源点；如果w f 愀一l 垡 e ( g ) 且愀+ l 岳e ( g ) ，则w ，为汇点 从而由引理1 1 可知w 的邻居全部在d 的测地集s 中，且( w ) n = 收 ，所以 有以下式子成立： 8 华东师范大学关于测地数界的研究 图2 2 情况二定向后的图 旷( g ) = i | + l ( 们i - 1 n ( w ) l = j + 1 + 一l ( 2 1 ) = d + 对于情况二，w 的所有邻居都为汇点，l ( w ) u l 2 ，且点w 自身也为源点，从而 由引理1 1 知： 矿( g ) 1 i + i ( w ) l i n ( w ) l + l d + 1 十一2 + l( 2 2 ) = d + ( 2 ) 当所有最大度点都位于唯一的一条路上，且就是图g 的直径时经 过以点为起始点广度优先搜索后，得到g 中点的划分k ，o f j + 1 ，不妨 设如( w ) = ，且w 厶n 圪，尼为偶数在对上所有点的连接边按照以上方式进 行定向之后，由于图g 为无三圈图，从而我们可以通过一种定向将w 的全部邻居都变 为汇点而由于点w 是在上的，从而i g ( w ) n 心is2 由定理1 1 知： 矿( g ) 1 l + l ( w ) | - l g ( w ) n i =d+1+一2(23) = d + 一l 9 华东师范大学 关于测地数界的研究 存在最大度点不在其中一条直径上； 其他情形 口 显然，所有的图都有之6 ，而且当且仅当g 为正则图时，= 6 所以上面的这个界 是比原猜想中的界有所改进 2 2 最大度不超过3 的图上测地数的下界 当我们把图g 的最大度限定为不大于3 时，我们也得到了图g 的上测地数的关 于的下界，定理如下： 定理2 2 如果图g 是最大度为3 和直径为d 的连通图，那么 矿c g ， 量：会一。霎羞喜嘉，点不在其中一条直径上； 证明j 采取分类讨论，按照图g 的最大度分别进行论证 情况一：= 1 ，则有g 为完全图恐，结论是平凡成立的，即矿( g ) j + 情况二：= 2 若6 = l ，则图g 为一条路，由定理i 1 l ，矿( g ) = d + 1 ，即矿( g ) d + 一1 ，结论 是成立的； 若6 = 2 ，则图g 为圈，由定理1 1 1 可知，矿( g ) d + l ，也就是旷( g ) j + ，结论 成立： 情况三：= 3 若6 = l ，由定理1 1 l 可得：矿( g ) d + 2 = 一1 若6 = 2 ，此时图g 不是路，从而由定理1 1 1 得：矿( g ) 2j + 2 = d + 一l ，从而结 论成立 若占= 3 ，则g 为三正则图设吠甜，v ) = 吐甜，v y ( g ) 以“为起始点，对图g 进行 广度优先搜索，得到一条，上面的点依次记为：甜= ，1 ，l 一，均= v 以及g 中点的 一个划分以，其中p wn 所= m ，o f z 而且n = 甜 ，由于g 为3 正则图，从 而z ，恰好有三个邻居，也就是巧中的所有点 以下证明存在g 的一个定向图d ，使得以及啊上的点全部都在d 的测地 集s 中 记巧= ，地，z ，3 l ，其中“l = 按照以下的方式与顺序，构作图g 的定向图d 1 0 一 + + d d ，i，、l 一 、， g ，l + ： g 得丁 一口 e 综 华东师范大学关于测地数界的研究 首先，对与上点相连接的边进行定向，使得定向之后，r ，上下标为偶数的点全 部为源点，下标为奇数的点全部为汇点从而上的点全部都在g 的定向图d 的测 地集s 中 其次，为中点和中点相连接的边定向，使其全部由圪中的点指向n 的点 下面我们对出现的各种情况进行讨论，证明对于定向后的图d 有矿( d ) d + 3 如果z ，1 ，z ，2 ，的之间没有边，则在定向之后的图d 中，z ，l ，地，z ，3 均为汇点( 如 图2 3 ) 由引理1 1 可得 图2 3 “l ，地，“3 之间没有边 如果“l ，地，甜3 之间只有一条边时，不妨设地z ，2 e ( g ) ，且( 甜1 ) n ( 屹) = 嵋， ( 地) n ( “2 ) = “j ，则”3 为汇点( 如图2 4 ) 图2 4 甜l ，甜2 ，甜3 之间有一条甜l 地 此时，若呸= “；显然甜；必须在s 中；若“：“j 由于呸不在z ，；和材l 的测地线 上，也不在”，z ，1 的测地线上，从而圪一“) 中存在其它的点( 不妨记为功属于s ，使 qq h n v巳 一 1 ii 一巧3 h 睇n 扎 一 = = 够 妒 华东师范大学关于测地数界的研究 得地在工，“l 测地线上，所以有 g 十( g ) l p 。i + l 玢 i + l = d + l + l + l ( 2 5 ) = d + 同理当材2 “3 e ( g ) 结论也是成立的 如果甜l ，屹，“3 ，之间有两条边，则地，“3 ，中必有一点在圪中没有邻居，不失 一般性，设此点为地，记( “1 ) n = 嵋，( 甜3 ) n = ；现在将边“2 “1 ，地“3 分别定 向为从“2 指向“1 ，“3 ，则有z ，3 为汇点，由引理1 1 可得“3 在测地集s 中，而z ，蚴测地 线，蜊l 均不包含点屹，从而“2 s ( 如图2 5 所示) 所以 矿( g ) l p 。l + l z ，2 ) i + i 材； l = d + 1 + 1 + l ( 2 6 ) = d + 图2 5 甜l ，z ，2 ，z ，3 之间有两条边 如果”l ，“2 ，“3 ，之间有三条边，则图g 为肠( 如图2 6 ) 珏l 订 图2 6z ，1 ，材2 ，“3 之间有三条边，即g 为完全图缸 由前面的内容可知，矿( 拖) = 4 而局的直径为l ，最小度为3 ，所以有 g + ( g ) d + 1 2 华东师范大学关于测地数界的研究 综上可得，当g 的最大度小于等于3 时有 矿c g ， 量：会一。翼毳薏嘉，点不在其中一条直径上； 2 3 单位区间图上测地数的下界 口 首先我们给出单位区间图的定义如果图g 的每一个顶点对应于实数轴上的单位 长度，并且任意两个点z ，在图g 中有甜v e ( g ) 当且仅当“，所对应的区间相交，则 我们称图g 为单位区间图( u n i ti n t e r v a lg r a p h ) 单位区间图有很多很好的性质，我们现 在利用单位区间图的顶点的一个特殊排列方式，给出当图g 为单位区间图时，旷( g ) 上 测地数也满足猜想一的定理叙述与证明如下： 定理2 3 如果图g 是单位区间图，直径为d 的连通图，最小度为6 ，则有旷( g ) d + 6 证明? 由于单位区间图其点存在一个规范顺序( c a n o n i c “o r d e 血g 2 ，3 2 】) ，也就是 说如果设v 1 ，v 2 ，是图g 的一个规范顺序( c a n o n i c a lo f d e 血g ) ，则有对于每条 边v f v f ，1 f ，打都有，v “l ，v f 形成一个团 当o f d 时，令厶= y h g ) l 如( v 1 ，d = f 且如( v ，) = d f 显然可以找到一条长为d 的路p ：，1 = 勒，x l ，娩，勘= ，且有p n 五= 而，0s f d 现在我们先按照下列规则与顺序为图g 定向，然后证明定向之后的图d 的测地数 大于等于d + 6 便可 第一，首先将与尸中的点相连接的所有边定向，使其定向后有：当f 为偶数时，麓为 源点；当f 为奇数时，而为汇点； 第二，设j j = m a x f | ( ，1 ) l 则由单位区间图的性质可知点集1 ，l ，v 2 ，在 图g 中的导出子图为团，从而将v l ，v 2 ，的导出子图中还未定向的边按照这样的 方式定向：若， ， 则将边v i v ，定向为从u 到v ，； 第三，将与点，l ，v 2 ，v 七相连接的所有还未定向的边定向，方向由其邻点指 向v l ，v 2 ，垓中的点； 第四，为其余还未定向的边定向，定向之后的图记为d 以下证明p 与1 ，l ，v 2 ，中的点全部位于有向图d 的测地集中 首先我们知道p 上的点全部都是汇点或者源点，从而全部位于d 的测地集中现 在我们证明点v 1 ，屹，垤也都位于测地集s 中 用反证法，假设存在点，l f 七不在s 中，则v f 在其它另外两点的测地线上， 不妨设这通过 的测地线也通过点和v f 2 其中h 和v f 2 都为的邻居，且v f l 经 1 3 华东师范大学关于测地数界的研究 过v j 到v 2 的有向通路方向为由到u 再到由此可知f 露或 者f l 后时，从v j 。到v j 2 有一条有向边，从而过h 和的最短有向通路不会过u ， 当f l f 时，从v f l 到有一条有向边，从而过h 和v f 2 的最短有向通路不会过v f 由以上的分析可知，不会有异于点耽的两点间的测地线经过，假设不成立，所以 功，屹，全部都在有向图d 的测地集中 综上可得： 矿( g ) l 尸i + l v - ，v 2 ， i + l