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

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本文不 包含其他个人已经发表或撰写过的研究成果对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名： 学位论文使用授权声明 日期：够丝丛 l 本人完全了解华东师范大学有关保留，使用学位论文的规定， 学校有权保留学位论文并向国家主管部门或其指定机构送交论文的 电子版和纸质版有权将学位论文用于非盈利目的的少量复制并允许 论文进入学校图书馆被查阅有权将学位论文的内容编入有关数据 库进行检索有权将学位论文的标题和摘要汇编出版保密的学位论 文在解密后适用本规定 学位论文作者签名，墓壁l 兰导师签名，逊 日 期：掣日 论文摘要 图的测地数是揭示图的结构特性的一个重要参数图的测地数源于几何 学，拓扑学和函数分析中的凸集理论，是凸集理论在图论中的应用和推广。 也与图论中“路覆盖”和“路分解”等问题相关联 本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工 作，主要的工作包括以下四个部分，( 1 ) 给出图的最小测地集与割点之间的关 系；( 2 ) 讨论了图死( 杨) 和l ( a ) 的测地数；( 3 ) 研究了g v 目的测地数及其上测 地数和下测地数；( 4 ) 讨论了g p 3 的测地数 在第二章中，介绍了无向图的测地数，我们主要做了以下的工作： 我们研究了含有割点的图的测地集，并得到相关结论；图的最小测地集 都不包含它的割点，这个结论是对文献 8 】中有关树兀测地数这一内容的推 广；在【8 】中，c , r a r y c h a r t r a n d ，f r a n k h a r a r y 和p i n g z h a n g 证明了g ( 蜀) = n ，我们推 广了这个结论得到，如果图g 有h 3 个顶点和k 个割点，并且g 的每个块都 是完全图，那么罟( g ) = n k 我们定义了一个新图n ( 忉若l 表示顶点为n 2 的树，日为一个图， 则乃表示如下构造得到的图，用图来替代乃中所有的顶点，若版，凰 分别表示代替乃中相邻顶点“，v 的图h ，则用边拶来代替死的边u v ，其中 x e 矿( 风) ，y v ( u o 并且证明了以下结论t 如果乃是有”2 个顶点，片叶子的树，那么g ( 乃( 杨) ) = i d ； f2 ，d = 4 如果死是星图，那么“l ( o ) ) = 3 ，d = 5 ，6 ； i4 ，d 7 如果霸不是星图，且n 有，片树叶，d 24 ，n 3 ，那么g ( l ( c 0 ) ) 埘州9 1 ，2 伽一 d 1 在第三章中，讨论了有向图的测地数，我们主要研究了g v 日的上m 测 地数及和测地数之间的关系，证明了下列结果， 对于任意图g 和h ，有g 一( g v 加= 2 如果g 和是两个非平凡图，那么g + ( g v 功g + ( g ) + g + ( 邱 在文献【1 】中，吕长虹提出了一个关于图的测地数的猜想，对于任意图 g ，都有g + ( g ) g ( g ) ，并且证明了当d 是n 阶连通图的直径且d ( n 一1 ) 2 或 甙g ) 4 时，这个猜想是正确的，我们主要研究了g v h 的上测地数和测地数 之间的关系，并且证明了： 莫艳红；有关图的测地数若干问题的研究 如果g 和片都不是完全图，那么g + ( g v 烈g v 肋； 如果胃是完全图，g 是弦图或u ( 回 3 ，那么g + ( g v i d g ( g v 邡； 假设s 是g 的最小2 一控制集，如果日是完全图，s 中每一点在g s 中 至多只有一个邻居，那么g + ( g v 册芝烈g v 脚 在第四章中，讨论了图的笛卡儿积的测地数在文献【l 】中，吕长虹给出 了g ( 6 3 = g ( g 恐) 的充要条件，我们考察了当g ( 日) = 2 时g h 的测地数，得 出了下列结论： 如果存在最小测地集8 和基于s 的测地族，使得s 相对于f 分成岱l ，s 2 ) ， 那么对任意测地数为2 的图日有颤g ) = 烈g x 册 设g 是不平凡的连通图，那么g ( g ) = 烈g p 3 ) 当且仅当存在最小测地集s 和基于8 的测地族，使得s 相对于，分成岱l ，s 2 ，s 3 ) 或岱l ，s 2 ) 关键词：凸集，测地集，测地数，割点，笛卡儿积 2 a b s t r a c t t h eg e o d e t i cn u m b e ro f ag r a p hi sa ni m p o r t a n tp a r a m e t e rr e v e a l i n gt h es t r u c t u r a lc h a r - a e t e ro fg r a p h s t h eg e o d e t i cn u m b e ro fag r a p ho r i g i n a t e df r o mt h ec o u v o s e tt h e o r yo f g e o m e t r y , t o p o l o g ya n df u n c t i o n a la n a l y s i s ，a n di st h eg e n e r a l i z a t i o na n da p p l i c a t i o no f c o n - v e xs e tt h e o r yi ng r a p ht h e o r y ；t h e r ei sa ni m p o r t a n tr e l a t i o nb e t w e e nt h eg e o d e t i cn u m b e r o f a g r a p ha n d t h ep r o b l e m so f p a t hc o v e r e da n dp a t hd e c o m p o s e d i n t h i s t h e s i s ，w e w i l l c o n s i d e r t h e g e o d e t i c n u m b e r o f g r a p h s a n d d i g r a p h s ，a n d r e s e a r c h r e s u l t so f m i n ea r em a i n l yp r e s e n t e d t h ec o n t e n to f t h et h e s i sm a i n l yi n v o l v et h ef o l l o w i n g f o u rp a r t s ：( 1 ) t h er e l a t i o nb e t w e e nt h em i n i m u m g e o d e t i cs e ta n dc u t v e r t i c e so f ag r a p hi s g i v e n ；( 2 ) t h eg e o d e t i cn u m b e r so f t h eg r a p h 死( k a ) a n d 瓦( o ) a r ed i s c u s s e d ；( 3 ) s t u d y i n g t h eg e o d e t i cn u m b e ra n dt h eu p p e r ( 1 0 w e r ) g e o d e t i cn u m b e ro ft h eg r a p hg v 风( 4 ) t h e g e o d e t i cn u m b e ro f t h eg r a p hg p 3i sd i s c u s s e d i nc h a p t e r2 ，w ei n v e s t i g a t et h eg e o d e t i cn u m b e ro fu n d i r e c t e dg r a p h w eo b t a i nt h e f o l l o w i n gr e s u l t s w ed i s c u s st h eg e o d e t i cs e to fg r a p h sc o n t a i n i n gc u t v e r t i c e s ，w eo b t a i nt h ef o l l o w i n g r e s u l t s ：e v e r ym i n i m u mg e o d e t i cs e to f ag r a p hd o e sn o tc o n t a i ni t sc u t v e r t i c e s ，t h i sr e s u l ti s t h eg e n e r a l i z a t i o no f t h er e s u l to nt h eg e o d e t i cn u m b e r o f 霸i n 【8 】；i n 8 】，g - r a r yc h a r t r a n d ， f r a n kh a r a r ya n dp i n gz h a n gp r o v et h a t 鲥疋) = h ，w es h o wt h a ti fgi sa g r a p hw i t hn 3 v e r t i c e sa n dkc u t v e r t i c e s ，a n de v e r yb l o c ko f gi sac o m p l e t eg r a p h ，t h e n 烈g ) = n t w ed e f i n eag r a p h 死( 印：ag r a p h 死( 日) i sag r a p ho b t a i n e df r o mat r e e 死w i t hn 2 v e r t i c e sb yr e p l a c i n ga l lt h ev e r t i c e sv h l ) a n dt h ee d g e s “vee ( l ) b ye ( 风v 风) ， w h e r eh ui sa g r a p hhr e p l a c i n gua n dh v i sag r a p hh r e p l a c i n gv a n dp r o v et h ef o l l o w i n g r e s u l t s i f 霸i san o n t r i v i a lg r a p hw i t h ，l e a v e s ，t h e ng ( 死( 杨) ) = d ； i f 死i sa s t a rg r a p h ，t h e ng ( 矗( o ) ) = d = 4 d = 5 6 ； d 7 i fli sn o tas t a rg r a p ha n d 已h a s ，l e a v e s ，d 4a n dn 3 ，t h e n 烈瓦( c 0 ) ) s m i n l r j l i , 2 ( n j ) i nc h a p t e r3 ，w ed i s c u s st h eg e o d e t i cn u m b e r o f d i g r a p h s t h el o w e ra n du p p e rg e o d e t i c n u m b e ro f g v ha n dt h er e l a t i o nb e t w e e nt h eg e o d e t i cn u m b e ra n dt h eu p p e r g e o d e t i cn u m b e r o f gvha r es t u d i e d w eo b t a i nt h ef o l l o w i n gr e s u l t s 3 莫艳红；有关图的测地数若干问题的研究 f o r a n y t w o g r a p h s g a n d 见w e h a v e g - ( g v 忉= 2 i f ga n dha r et w on o n t r i v i a lg r a p h s ，t h e n 矿( gv 忉矿( g ) + g + ( 印 i n 【l 】，l ur a i s e dac o n j e c t u r et h a tg + ( g ) g ( g ) f o ra n yg r a p h so f o r d e rhw i t hg ( g ) 4 o r i t s d i a m e t e r n o l e s s t h a n o i ) 2 w es t u d y t h er e l a t i o n b e t w e e n g + ( g v 印a n d 烈g v h ) ， a n dp r o v et h ef o l l o w i n gr e s u l t s i f n e i t h e r g n o r h i sac o m p l e t e g r a p h t h e n g + ( g v 甙g v 肋 i f h i sac o m p l e t eg r a p ha n d g i sac h o r d a l g r a p h o r g i sa g r a p hw i m “g ) 是任两个图，若v l v ，e l e ，且籼是 妒在e l 上的限制，则称g l 是g 的子图( s u b g r a p h ) 设s 是图g 的顶点集h g ) 的 非空子集，曰是图g 的边集e ( g ) 的非空子集，由s 和s 中顶点之间的所有边所 形成的图称为s 的导出子图( i n d u c e d g r a p h ) ，记为g 眵】；由b 和占中边所有端点 所形成的图称为b 导出子图，记为g 嘲g s ( 也记为g s ) 表示子图g 【玎s 】即 从g 中去掉s 和与s 关联的所有边，若s = “叶，常把g 一“叶简记为g v g b 表示从g 中去掉b 中所有边( 但保留每条边的端点) 后得到的子图，同样g 一 e l 简记为g e 包含g 中所有顶点的子图称为g 的支撑子图或生成子图( s p a n n i n g s u b g r a p h ) 图论中，圈的运算也是人们研究的重要内容通过图的某种运算，我们 可以用两个或两个以上较小和较简单的图生成一个较大和较复杂的图，由于 较小和较简单的图的结构特性容易把握，从而对较小和较简单的图的结构特 性的研究，能较容易地把握住较大和较复杂的图的结构特性，因此对图的运 算的研究是很有价值的 设g i = 和g 2 = ，若g l 和g 2 没有公共顶点，则称它们是不 相交的( d i s j o i n t ) ；若g i 和岛没有公共边，则称它们是边不重的( e d g e d i s j o i n t ) g l 和g 2 的并( u n i o n ) 被定义为g l 和g 2 中所有边组成的图，记为g ug 2 ；g 1 和 g 2 的交( i n t e r s e c t i o n ) ，记为g ing 2 ，指仅由g l 和g 2 公共边组成的图；设g l 和 g 2 是两个不相交的简单图，g l 和g 2 的联( j o i n ) 为图g = g iv g 2 ，其中图g 满足 以g ) = v ( g t ) uh g 2 ) ，e ( g ) = e ( g i ) u e ( g 2 ) u i u v ：“v ( g j ) ，v e 以g 2 ) g i 和g 2 的 笛卡儿积( c a r t e s i a n p r o d u c t ) 为图g = g t g 2 ，其中图g 满足以6 3 = 以g 1 ) h g 2 ) ， g 中的两个顶点( a ，6 ) 和( c ，力是邻接的当且仅当a = c 且b d e ( g 2 ) 或b = d 且 a ce e ( g 1 ) 四路与连通图 设“和v 是任意图的顶点，图的一条“一v 链( c h a i n 或w a l k ) 是有限的顶点和边 交替序列u o e l u l e 2 u n i e n u 。0 = u 0 ，v = ) ，其中与边e j ( 1 i s ”) 相邻的两个顶 点u l - i 和u i 正好是e l 的两个端点，u ( u o ) 和“) 称为链的端点( e n d v e r t i c e s ) ，其余 的顶点称为链的内部点( i n t e r v a l v e r t i c e s ) ，一条“一v 链，当“v 时，称它为开的， 8 第一章绪论 否则称为闭的边互不同的链称为迹( t r a i l ) ；内部点不同的链称为路( p a t h ) ，阶 数为h 的路记为只；闭路称为圈( c y c l e ) ，阶数n 为的圈记为g 包含图中所有 顶点的圈称为h a m l i t o n 圈；包含图中所有顶点的路称h a m l i t o n 路；包含图中所 有边刚好一次的闭迹称为e u l e r 回路链，迹，路，圈等的长度( 1 e n g t h ) 是指它 们所包含的边数 设w 是有向图d 中u v 链，指定m ，的方向从“到v ，若w 中所有边的方向与 此方向一致，则称w 为d 中从“到v 的有向链类似定义有向迹，有向路，有 向圈，有向回，h a m l i t o n 有向圈和e u l e r 有向回等概念 设u 和v 为无向图g 的任两个顶点，g 中所有从u 到v 的路的最小长度称为 顶点“与v 的距离( d i s t a n c e ) ，记作d ( u ，v ) 或d ( v ，“) ，若g 中不存在u 到v 的路，则约 定d ( u ，d = o o 有关距离的概念同样适用于有向图，设d 为有向图，y 以d ) ， d 中所有从“到v 的有向路的最小长度称为从“到v 的距离，记作d ( u ，v ) ，若u 不可达v 。则d ( u ，= o o 另外，我们把 d i a m ( g ) = m a x d ( u ，力：“，v “g ) r a d ( 6 3 = n f l n l d ( u ，：u ，v h g ) 1 分别称为图的直径( d i a m e t e r ) 和图的半径( r a d i u s ) 若图中任何两顶点“和v 之间存在u - v 路，则称该图是连通的( c o n n e c t e d ) ， 否则称g 不连通( d i s c o n n e c t e d ) 图g 的极大的连通子图称为g 的连通分支 ( c o m p o n e n t ) 五，连通度和二分图 如果在图g 中删去一个顶点v 后，图g 的连通分支数增加，则称顶点v 为g 的割点( c u t v e r t e x ) 如果在图g 中删去一条边e 后，图的连通分支数增加，则称 e 为g 的割边( c u te d g e ) 没有割点的非平凡连通图称为块( b l o c k ) ，g 中不含割点 的极大连通子图称为图g 的块如果图g 的顶点集的一个真子集s 满足g s 不连通或是平凡图，则称s 为g 的一个点剖( v e r t e xc u t ) ，如果图g 的边集的一 个真子集f 满足g 一，不连通或是平凡图，则称f 为g 的一个边割( e d g e c u 0 设g 是连通图，称“g ) = m i n l l s i ：s 是g 的点割 为g 的点连通度( v e r t e x c o n n e c t i v i t y ) 或连通度，如果图的连通度至少为k ，则称g 是“连通的( k - c o n n e c t e d ) 对于阶数大于1 的图，d 6 3 = 1 当且仅当g 是含有割点的连通图；而g 是不连 通图时，显然有娟g ) = 0 同理定义边连通度( e d g e - c o n n e c t i v i t y ) ( g ) = m i n l l f i ：f 是g 的一个边割1 9 莫艳红；有关图的测地数若干问题的研究 定理1 2 2 【3 】3 对于图g ，有d g ) ( g ) 烈g ) 设g 是简单无向图，sc 以g ) ，s 0 ，若s 中任何两个顶点都不相邻，则 称这个顶点集合s 为图的独立集；若图g 的顶点集能分成两个不相交的非空 的独立集n 和吩，则称g 是二分图( b i p a r t i t e g r a p h ) ，记作g = ，其中 h 和圪叫做g 的二划分对于二分图g = ，若i n i = m ，i v 2 | _ n ，且n 中任一顶点与圪中任一顶点有边关联，则称该图为顶点m 和n 的完全二分图 ( c o m p l e t e b i p a r t i t e ) ，记作砀。二分图具有以下重要的定理。 定理1 2 3 非平凡图g 是二分图当且仅当g 中不含有奇圈。 六树的基本概念 树( t r e e ) 是无圈连通无向图，树中度数为l 的顶点称为树的叶( 1 e a f ) ，树 中度数大于1 的顶点称为树的内点( i n t e r n a l v e r t e x ) 不相交的若干树称为森林 ( f o r e s 0 ，即森林的每个连通分支是树存在一点和其他所有点相邻的树称为 星图( s t a r g r a p h ) 如果r 是g 的一个生成子图而且又是一棵树，则称r 是图g 的一棵生成树( s p a n n i n g t r e e ) 或支撑树 叶 定理1 2 4 设r 是月阶非平凡树( 平凡图称为平凡树) ，则r 中至少有2 片树 定理1 2 5 一个连通图是树当且仅当它的每条边是割边 定理1 2 6 图g 有生成树当且仅当g 为连通图 1 3 问题的引人 。g e o d e t i c ”原来是测量学中的一个专业术语，表示两点之间的最短路程 ( 平面上为直线，曲面上为一弯嗌的弧线) 在被引入图论之后，“g e o d e t i c ”仍表 示两点之间的最短路，但此时的最短路已经演变成为图论中的最短路了，下 面我们介绍一下“g e o d e t i c ”在数学中的发展及与其他数学问题的联系 凸集是几何学，拓扑学和函数分析的基本概念对于任意x , y 爿，彳为度 量空间回中的点集，每条连接x 和y 的最短路( 曲线或弧) 完全位于彳中， 则称点集一为度量空间的凸集；点集一( e x ) 的凸包口】是在x 中包含a 的最 小凸集或包含一所有凸集的交 1 0 第一章绪论 图论中的度量空间( h g ) ，回，这里h g ) 是连通图g 的点集，烈力( 或简记为 田是指两点x 和y 之间的距离( 被定义为最短路x y 的长度) ，我们把长度为 班力的x y 路也称为x y 测地线如果对于彳中的任意两点x 和y ，每条x y 测地线上的点完全含于z 中，那么连通图g 的点集彳就是凸集显然，以g ) 是一个凸集点集彳eh g ) 的凸包】是包含彳的最小的凸集在b o n n e s e n 和 f e n c h e l 所著的书 1 8 】前页初始段指出。凸图形在几何学已经起了重要作用 ；而m i n k o w s k i 创建一个恰当的工具被借用来处理凸区域和几何的问题，并 且也得到广泛地应用在b u c k l e y 和h a r a r y 所著的书【4 】中讨论了图的凸 性，并在文献 5 】被h a r a r y 和n i e m i n e n 所研究；而图的凸数在文献【1 6 】被e v e r e t t 和s e i d m a n 引入并在文献【6 】，【7 】，【1 4 】中作了进一步研究在此研究的基础上， 人们提出了反映图的结构特性的参数一图的测地数 设g 是一个连通图，一是h g ) 的凸子集，由凸集的定义，若x , y 爿，对于 g 中一点z 且z 是j y 测地线上的点，则z 必属于彳设l ( x ，力表示位于g 中x y 测地线上的所有点的集合，则如，力( 一一般地，对于seh g ) ( 注意这里s 不一定是凸集) ，我们定义，i ( s ) = u 。时i ( u ，d 当然，sc 1 ( s ) ；而“s ) = s 当 且仅当s 是凸集，当邶) = h g ) 时，s 被称为图g 的测地集因此g 的测地集 s 有如下的性质，对于任意z 以g ) ，都存在x , y s 使得z 位于x y 测地线上 图g 的最小测地集的基数被称为g 的测地数，记为g ( g ) 图的测地数在文献 【4 】中被引入，在文献 8 】， 9 】， 1 0 】和【1 l 】中作了深入地研究在文献【1 2 】中又被 g c h a r t r a n da n dp z h a n g 推广到有向图 在有向图d 中，从点“到点v 的距离d ( u ，是指最短“一v 有向路的长度我 们类似定义有向图d 的测地线，测地集和测地数长度为d ( u ，v ) 的一条“v 有向路又称为“一v 测地线，定义i ( u ，d 为所有位于图d 的“v 测地线和v - u 测地 线上的点的集合对于h d ) 的非空子集s ，同样定义郴) = u 。心，( “，v ) 如果 耶) = h d ) 则称s 为有向图d 的测地集，基数最小的测地集称为最小测地集。 并把这个最小基数称为有向图d 的测地数，记作甙d ) 对于阶数n 2 的连通图g ，定义g 的所有定向图中测地数的最小值为g 的下测地数( 1 0 w e r g e o d e t i c n u m b e r ) ，记为g - ( g ) ，定义g 的所有定向图中测地数 的最大值为g 的上测地数( u p p e r g e o d e t i c n u m b e 0 g - ( g ) = m i n l g ( d ) ：d 是g 的定向图 ； g + ( g ) = m a x g ( d ) ：d 是g 的定向图 在此基础上，g e r a r dj c h a n g 和l i d a t o n g 等人在文献 1 3 】中，进一步提出 了图测地谱( g e o d e t i cs p e c t r u m ) 的概念，用记号s ( g ) 来表示，其中 莫艳红；有关图的测地数若干问题的研究 s ( g = i s ( d ) ：d 是g 的定向图 本文主要研究含有割点的图的测地集，图l ( 忉的测地集及图的联，笛卡 尔积的测地集，相关概念将在以后的章节中陆续介绍 1 4 主要研究结果 本节定理的编号采用它们在各自章节中出现的编号，其中未介绍的符号 和概念请对照它们相应的章节下面是本人所做的一些结果 定理2 1 5 图的每个最小测地集都不包含它的割点 定理2 1 6 设图g 有n23 个顶点和个割点，如果图g 的每个块都是完全 图，那么g ( g ) = 一k 若l 表示顶点为月2 的树，日为一个图，则l ( - ) 表示如下构造得到的 图t 用图h 来替代l 中所有的顶点，若风，风分别表示代替矗中相邻顶点 虬v 的图，则用边砂来代替死的边“v ，其中x e 以凰) ，y 风) 定理2 2 4 如果树兀有h 之2 个顶点，有，片叶子，那么g ( 死( 局) ) = l d 定理2 2 5 ( 1 ) 如果是星图，那么 f2 ，扛4 甙l ( c a ) ) = 3 ，d = 5 ，6 i4 ，d 7 ( 2 ) 如果瓦不是星图，且n 有z 片树叶，d 4 ，n 3 ，那么 g ( l ( c j ) ) sm i n i a l l ，2 ( n o 定理3 2 2 对于任意两个图g 和日，我们有g - ( g v t t ) = 2 定理3 2 3 如果g 和日是两个非平凡图，那么g + ( g v 印矿( 6 3 + g + 定理3 3 7 如果“6 3 3 ，那么旷( g ) g ( 6 3 定理3 3 8 ( 1 ) 如果g 和都不是完全图，那么g + ( g v 印g ( o v ； ( 2 ) 如果日是完全图，g 是弦图或“g ) 2 ，又l ( u 2 ，u 4 ，u 1 ) = “g ) ，因此鲥g ) = 3 2 1 无向图测地数的性质 显然，不连通图的测地数等于各个连通分支的测地数之和，因而我们只 需考虑连通图的测地数对于连通图的测地数，有以下几个巴知性质； 定理2 1 1 【8 】如果图g 是阶数为月，直径为d 的非平凡连通图，那么 g ( 6 3sn d + 1 如果图g 中，顶点v 的邻点导出的子图是完全图，则称v 是一个单纯点 ( s i m p l i c a l v e r t e x ) 显然，度数为1 的顶点就是一个单纯点，度数为1 的顶点又 称悬挂点 引理2 1 1 图g 是完全图的充分必要条件是g 是连通图，且g 的每一点都 是单纯点 证明：必要性是显然的，下面证充分性 1 4 第二章无向图的测地数 假设g 不是完全图，则存在x ，yeh g ，使得x , y 不相邻令，为x 一) 之间的 一条最短路x = 蜘一蝴一地一一i 一= y ，此时咖，“2e ) ，但是u o u 2g e ( 回， 即蝴不是单纯点，这与g 的每一点都是单纯点矛盾，因而g 是完全图 定理2 1 2 8 】图g 的每个测地集必包含图g 的单纯点 定理2 1 3 8 】对于整数，d 和k 2 ，且满足，s d 2 r ，则存在一个连通图 g ，使得t e a ( g ) = ，d i a m ( g ) = d 和g ( g ) = k 定理2 1 4 【8 】如果n ，d 和k 都是整数，且满足2 d h ，2s n 和 n d k + l 0 ，那么存在n 阶连通图g ，使得d i a m ( 0 - 3 = d ，烈6 3 = t 我们研究了含有割点的图的测地集，并得到一些新的结果，相关结果发 表在文献 1 7 中 图g 的块- 割点图( b l o c k - e u t p o i n 0 是一个二分图h ，在口中其中一个划分是 g 的所有割点，另一个划分是用点b 。来替代g 的每个块厮我们定义喝是胃 的边当且仅当y b “见图2 6f h g 图2 ：图是图6 的块割点图 引理2 1 2 对于连通图g ，它的块割点图h 是树 1 5 莫艳红：有关圈的测地数若干问题的研究 证明：首先，易知日是连通的假设日有圈c ，既然日是二分图，根据 定理1 2 3c 是一个偶圈，用岛和割点”依次给圈c 的顶点进行标号，假 设h c ) = i b l ，”1 b 2 ，v 2 ，b m ， 沏2 ) 当我们从c 中删去任何一个割点蜥 o = 1 ，2 ，小) ，它剩下的部分也是连通的，那么u 墨。b r 删去任一个顶点后还是 连通的，因而u 2 ，噩是g 的一个没有割点的连通子图这与b l ，占2 ，如都是 g 的极大连通子图相矛盾故块割点图是一个不含圈的连通图，即图h 是 树 - 如果既是的叶子，那么我们称岛是g 的树叶块( 1 e a f b l o c k ) ，每个树叶块 都只含图g 的一个割点，且根据定理1 2 4 可知一个本身不是块的连通图g 至 少有两个树叶块；如果b f 是h 的内点，则称b f 是g 的内部块( i n t e m a l b l o c k ) 定理2 1 5 图的每个最小测地集都不包含它的割点 证明，因为g ( g lu g 2 ) = 甙g 1 ) + 反g 2 ) ，这里g lug 2 是g l 和g 2 的并，所以我 们只需研究连通图设r 是g 的割点集，日是它的块割点图假设g 有m 2 个树叶块b l ，b 2 ，巩，在日中用点b ，来替代树叶块毋因为每个树叶块只含 g 的一个割点，所以岛中至少存在一点“gt 根据引理2 1 2 h 是树，而日中 的每片树叶b r 是包含b ，的测地线的端点，所以当x ，) ，g b i 时，“不可能位于x - y 测地线上；当x e b ，n t ，_ ) ，b f 时，“也不可能位于x - y 测地线上，只有当x 或y 至少有一点属于毋一r 时，球才有可能位于x - y 测地线上这意味着g 的每一个 最小测地集一定包含x 1 ，娩，