（应用数学专业论文）图和有向图的测地数.pdf

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本文不 包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名：皇陴日期：盈虹二_ 厶坦 学位论文使用授权声 本人完全了解华东师范大学有关保留、使用学位论文的规定， 学校有权保留学位论文并向国家主管部门或其指定机构送交论文的 电子版和纸质版有权将学位论文用于非盈利目的的少量复制并允许 论文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据 库进行检索有权将学位论文的标题和摘要汇编出版。保密的学位论 文在解密后适用本规定。 学位论文作者签名：辑导师签名 彤儿 日 期：趔趣坦日期：竺丛笙! 论文摘要 图的测地数是揭示图的结构特性的一个重要参数。图的测地数源于几何 学、拓扑学和函数分析中的凸集理论，是凸集理论在图论中的应用和推广， 也与图论中“路覆盖”和“路分解”等问题相关联。 本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工 作，主要的工作包括以下四个部分：( 1 ) 给出完全r 一部图的测地数；( 2 ) 研究了 g 。+ h v 的测地数及其上测地数和下测地数；( 3 ) 研究了g 。o 凰的测地数及其上 测地数和下测地数；( 4 ) 讨论了g k 3 的测地数。 在第二章中，介绍了无向图的测地数，我们主要做了以下二方面的工作： 在文献【l o j ，g 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 ( k r , 。) ：r a i n r ，s ，4 1 ( s 2 ) ，我们类似地给出完全r - 部图的测地数， 层9 ：g ( 丘。，。”，。，) = m i n n i ，4 】，其中n 。2 ，i = 1 ，2 ，r 且n 】r 1 2 - n ， 在文献【4 ，吕长虹考察了图的两种运算g 。+ h 。和g 。日。得出当u ，v 分别属 于g 和抒最小测地集时，有g ( g 。+ 日。) = g ( g ) + g ( h ) 一2 和g ( g 。o h ，) = g ( g ) + p ( h ) 一2 。 我们推广上面的结论，证明了对于“和v 分别是g 和日中的任意点，都有 g ( g ) + 亭( 日) 一2 g ( g 。+ ) g ( g ) 十g ( h ) ， g ( g ) + g ( h ) 一2 g ( g 。0 0 ) g ( g ) + g ( 日) 在第三章中，讨论了有向图的测地数，我们主要研究了g 。+ 凰和g 。巩 的上( 下) 测地数，证明了下列结果： 设g 和日是非平凡图，对于“v ( g ) ，v y ( h ) ，则 g + ( g ) + g + ( 爿) 一2 g + ( g 。+ 凰) g + ( g ) + g + ( 日) ， g 一( g ) + g 一( 日) 一2 g - ( g 。+ 风) g ( g ) + g - ( 日) ； g + ( g ) + g + ( ) 一2 g + ( g 。o 巩) g + ( g ) + g + ( 月) ， g 一( g ) + g - ( h ) 一2 g - ( g 。o h 。) g - ( g ) + g - ( h ) 设g 和h 是两个非平凡图，当“和v 分别是g 和日的悬挂点时，有 g + ( g 。+ h v ) = g + ( g ) + g + ( 爿) ， g 一( g “+ h ，) = g - ( g ) + g 一( h ) 一2 ； 叶永升：图和有向图的测地数 g + ( g 。凰) = g + ( g ) 十g + ( h ) 一1 ， g 一( g 。o h u ) = g 一( g ) + g 一( 日) 一2 在第四章，我们研究了图的笛卡儿积g k 3 的测地数，得出了下列结论： 设g 是非平凡连通图，如果g 包含某个最小测地集s ，在s 中存在一点 x 使得g 中的任意点都位于x w 测地线上，其中w es ，那么 g ( g ) g ( g k 3 ) g ( g ) + 1 设g 是阶数至少为3 的连通图，那么g ( c ) = g ( g k 3 ) 当且仅当存在最小测 地集s 和基于s 的测地族f 使得s 相对于f 分成( s 。，s2 ，s 3 ) 设树l 有z ( 3 ) 个树叶，则 g ( t n k 3 ) = g ( 瓦) = 1 关键词： 凸集，测地集，测地数，完全r 一部图，笛卡儿积 2 a b s t r a c t t h eg e o d e t i cn u m b e ro fg 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 c t e ro fg r a p h t h eg e o d e t i cn u m b e ro fg r a p ho r i g i n a t e df r o mt h ec o n v e xs e tt h e o r yo fg 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 fc o n v e xs e t t 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 ro fg r a p h a n dt h ep r o b l e m so fp a t hc o v e r e da n dp a t hd e c o m p o s e d i nt h i st h e s i s ，w ew i l lc o n s i d e rt h eg e o d e t i cn u m b e ro fg r a p h sa n dd i g r a p h s ，a n dr e s e a r c h r e s u l t so fm 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 ft 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 ev a l u eo fg e o d e t i cn u m b e rf o rc o m p l e t er - p a r t i t eg r a p h si sg i v e n ；( 2 ) s t u d y i n gt 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 。十h v ； ( 3 ) s t u d y i n g t h e g e o d e t i cn u m b e ra n d t h e u p p e r ( 1 0 w e r ) g e o d e t i cn u m b e r o f t h e g r a p h g 。o h v ； ( 4 1t h eg e o d e t i cn u m b e ro ft h eg r a p hg k 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 gt w or e s u l t s i n 1 0 ，g 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 gg i v et h eg e o d e t i cn u m b e ro n c o m p l e t eb i p a r t i t eg r a p h ：烈砭，) = m i n l r , 5 ，4 ( r s 2 ) s i m i l a r l y ，w eg i v et h eg e o d e t i c n u m b e ro nc o m p l e t er - p a r t i t eg r a p h ：g ( 蜀1 m m ) = m i n n l ，4 1 ，w h e r en f 2 ，i = 1 ，2 ，r a n d ”l 2 n ， g “+ h ”a n dg “o 日ra r et w og r a p h i co p e r a t i o n s i n 4 1 ，c h a n g h o n gl up r o v e dt h a t g ( g 。+ h v ) = g ( g ) + g ( h ) 一2a n dg ( g 。0 风) = g ( g ) + g ( h ) 一2 ，w h e r e “a n dvb e l o n g t o t h em i n i m u mg e o d e t i cs e to fga n dh ，r e s p e c t i v e l y w eo b t a i nt h ef o l l o w i n gr e s u l t sw h i c h g e n e r a l i z e t h ea b o v er e s u l t s ：g ( g ) + g ( 日) 一2 g ( g 。+ 日，) g ( g ) + 占( h ) a n d p ( g ) + g ( h ) 一2 g ( g “0 ) g ( g ) + g ( f o ru y ( g ) ，v y ( h ) 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 ro 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 ng * + h va n dg 4oh vi ss t u d i e d w ep r o v et h ef o l l o w i n gr e s u l t s i f ga n dha r et w on o n t r i v i a lg r a p h s ，u v ( g ) ，v y ( h ) ，w eh a v e s + ( g ) + g + ( h ) 一2 g + ( g 。+ 风) 占+ ( g ) + g + ( h ) g ( g ) + g - ( 日) 一2 g ( g 。+ 1 4 v ) g ( g ) + g - ( 片) g + ( g ) + g + ( 日) 一2 g + ( g 。h v ) g + ( g ) + g + ( h ) g ( g ) + g - ( 丑) 一2 g - ( g 。o h ，) g ( g ) + g - ( h ) 3 ! 查苎! 望塑宣鱼里塑型些塑 一一 l fga n dha r et w on o n t r i v i a lg r a p h s ，a n d a n dva r et h ep e n d a n tp o i n to fg a n dh ， r e s p e c t i v e l y ，w eh a v e g + ( g 。+ h ，) ；g + ( g ) + g 十( h ) ， g 一( g 。+ 且，) = g - ( g ) + g - ( h ) 一2 ； g + ( g 。日。) = g + ( g ) + g + ( h ) 一1 ， 旷( g 。o h 。) = g - ( g ) + g | ( 日) 一2 i nc h a p t e r4 ，w es t u d yt h eg e o d e t i cn u m b e ro fg ( 3 ，a n do b t a i nt h ef o l l o w i n gr e s u l t s l e tgb ean o n t r i v i a lc o n n e c t e dg r a p h i fgc o n t a i n sam i n i m a lg e o d e t i cs e tsw i t ha v e r t e xzs u c ht h a te v e r yv e r t e xo fgl i e so nx wg e o d e s i cl i n e ，w h e r ew s ， g ( g ) g ( g 9 3 ) g ( g ) 十 l e tgb eac o n n e c t e dg r a p ho fo r d e ra tl e a s t3 ，t h e ng ( g ) = g ( g k 3 ) i fa n do n l yi f t h e r ee x i s t sam i n i m a lg e o d e t i cs e tsa n daf a m i l yfb a s e do nss u c ht h a tsc a nb ep a r t i t i o n i n t o ( s i ，s2 ，s3 ) w i t hr e s p e c t t o f 7 i f t h e r ee x i s t f 险3 ) l e a v e so n t h e t r e e l ，w e h a v e g ( 咒k 3 ) = g ( l ) = 1 k e y w o r d s ：c o n v e xs e t ；g e o d e s i cs e t ；g e o d e t i cn u m b e r ；c o m p l e t er p a r t i t eg r a p h c a r t e s i a np r o d u c t 4 第一章引言 1 7 3 6 年是图论的元年，在这一年，e u l e r 解决了一个当日寸还没有解决的著 名问题- - k 6 n i g s b e r g 七桥问题，从而使他成为图论和拓扑学创始人。当时的数 学界并没有对e u l e r 解决七桥问题的意义有足够的认识，甚至仅仅视其为一个 数学游戏而已。图论诞生后没有及时获得足够的发展，直到1 9 3 6 年，匈牙利 数学家k 6 n i g 出版有限图与无限图理论 2 1 1 ，这是图论的第一部专著，它总 结了图论2 0 0 年来的成果。从此，图论进入发展与突破的快车道。经过半个 多世纪的发展，现已成为数学科学的一个独立的重要学科，它的分支很多， 如算法图论，极值图论，网络图论，代数图论，随机图论，拓扑圈论，超图 等。不论那一支都是以图的结构特性为研究基础，因此对反映图的本质属性 的参数的研究是十分活跃的研究方向，如图的着色数、控制数、覆盖数和匹 配数等。本文主要介绍关于图和有向图的测地数的研究进展及其本人在这方 面所做的工作。 1 1 图和有向图的测地数的由来 凸集是几何学、拓扑学和函数分析的基本概念。对于任意x ，y a ，a 为度 量空间 ，d ) 中的点集，每条连接x 和y 的最短路( 曲线或弧) 完全位于a 中， 则称点集a 为度量空间的凸集；点集a ( x ) 的凸包陋 是在x 中包含a 的最 小凸集或包含a 所有凸集的交。 图论中的度量空间( y ( g ) ，d ) ，这里v ( g ) 是连通图g 的点集，d ( x ，y ) ( 或简记为 d ) 是指两点工和y 之间的距离( 被定义为最短路工一y 的长度) ，我们把长度为 d ( x ，y ) 的x y 路也称为z y 测地线如果对于a 中的任意两点x 和y ，每条工一y 测地线上的点完全含于a 中，那么连通图g 的点集a 就是凸集。显然，v ( g ) 是一个凸集。点集a y ( g ) 的凸包【a 】是包含a 的最小的凸集。在b o r m e s e n 和 f e n c h e l 所著的书 2 4 】前页初始段指出：凸图形在几何学已经起了重要作用 ；而m i n k o w s k i 创建一个恰当的工具被借用来处理凸区域和几何的问题，并 且也得到广泛地应用。在b u c k l e y 和h a r a r y 所著的书 6 中讨论了图的凸 性，并在文献 7 】被h a r a r y 和n i e m i n e n 所研究；而图的凸数在文献 2 3 被e v e r e t t 和s e i d m a n 引入，并在文献( 【8 】，【9 】，【】7 】) 中作了进一步研究。在此研究的基础 上，人们提出了反映图的结构特性的参数一图的测地数。 设g 是一个连通图，a 是v ( g ) 的凸子集，由凸集的定义，若x ，y a ，对于 g 中一点z 且z 是z y 测地线上的点，则z 必属于a 。设t ( x ，y ) 表示位于g 中上一v 6 第一章引言 测地线上的所有点的集合，则，( 工，y ) a 。一般地，对于s y ( g ) ( 注意这里s 不一定是凸集) ，我们定义：z ( s ) = u 。哪l ( u ，v ) 。当然，s i ( s ) ；而i ( s ) = s 当 且仅当s 是凸集，当，( s ) = y ( g ) 时，s 被称为图g 的测地集。因此g 的测地集 s 有如下的性质：对于任意z y ( g ) ，都存在z ，y s 使得z 位于x y 测地线上。 图g 的最小测地集的基数被称为g 的测地数，记为g ( g ) 。图的测地数在文献 6 】6 中被引入，在文献( u 0 ，【1 1 ，【】2 ) 和【1 3 中作了深入地研究。在文献【1 4 】中 又被g c h a r t r a n da n dp z h a n g 推广到有向图。 1 2 基本概念 一个图g ( 也称无向图) 通常用g = ( v e ) 表示，其中v = v ( g ) 是图的顶点 集( v e r t e xs e t ) ，e = e ( g ) 是图g 的边集( e d g es e t ) i 如果每条边都是有向边的图 称为有向图d ( d i r e c t e dg r a p h ) 。如果e = “vf s _ e ( g ) ，则称e 关联“和v ，称“和v 是边e 的端点( e n dv e r t e x ) ，并称u 和v 是邻接的( a d j a c e n t ) ，关联于同一顶点的 两条边也称为邻接的边( a d j a c e n te d g e ) 。端点重合为一点的边称为环( 1 0 0 p ) ， 端点相同的边称为平行边( p a r a l l e le d g e ) 或重边( m u l t i p l ee d g e ) 。不与任何边相 关联的顶点称为孤立点( i s o l a t e dv e r t e x ) ，只有一个顶点的图称为平凡图( t r i v i a l g r a p h ) ，无环并且无重边的图称为简单图( s i m p l eg r a p h ) ，任何不同两顶点都有 边相连的简单图称为完全图( c o m p l e t eg r a p h ) 。 对于有向图d ，去掉边上的方向得到的无向图g 称为d 的基础图( u n d e r l y i n g g r a p h ) 。反之，任何一个无向图g ，将它的每条边赋予一个方向得到一个有向 图d ，称d 为g 的一个定向图( o r i e n t e dg r a p h ) 。 图g 中与顶点v 关联的边数( 一条环要计算两次) 称为1 一的度( d e g r e e ) ，记 作d e g ( v ) 或d ( v ) ；用( g ) 和6 ( g ) 分别表示g 的最大度( m a x i m u m d e g r e e ) 和最小度 ( m i n i m a ld e g r e e ) 即： z x ( g ) = m a x l d ( v ) ：v y ( g ) ， 烈g ) = m i n d ( v ) ：v 矿( g ) 对于有向图d ，进入顶点v 的边数称为v 的入度( i n d e g r e e ) ，记作i d ( v ) ；离 开顶点v 的边数称为v 的出度( o u t d e g r e e ) ，记作o d ( v ) 。显然，在有向图d 中， 任意顶点v 的度数d ( v ) = i d ( v ) + o d ( v ) 。显然有下列结论； 1 每个图g 中，顶点度数总和等于边数的二倍。即 d ( v ) = 2 1 e ( g ) v e v ( g ) 7 第一章引言 测地线上的所有点的集合，则l ( x ，y ) a 。一般地，对于s v ( g ) ( 注意这里s 不- 定是凸集) ，我们定义：i ( s ) = u 。s l ( u ，v ) 。当然，s g ( s ) ；而i ( s ) = s 当 且仅当s 是凸集，当l ( s ) = v ( g ) 时，s 被称为圈g 的测地集。因此g 的测地集 s 有如下的性质：对于任意z y ( g ) ，都存在x ，y s 使得z 位于z y 测地线上。 图g 的最小测地集的基数被称为g 的测地数，记为g ( g ) ，图的测地数在文献 【6 】6 中被引入，在文献( 1 0 ，【】1 ， 1 2 】) 和 1 3 中作了深入地研究。在文献【1 4 】中 又赦g c h a r t r a n da n d e z h a n g 推广到有向图。 1 2 基本概念 一个图g ( 也称无向图) 通常用g = ( v e ) 表示，其中v = v ( g ) 是图的顶点 集( v e r t e xs e t ) ，e = e ( g ) 是图g 的边集( e d g es e t ) ；如果每条边都是有向边的图 称为有向图d ( d i r e c t e dg r a p h ) 。如果e = u f e ( g ) ，则称e 关联“和v ，称“和v 是边e 的端点( e n dv e a e x ) ，并称“和v 是邻接的( a d j a c e n t ) ，关联于同一顶点的 两条边也称为邻接的边( a d j a c e n te d g e ) 。端点重合为一点的边称为环( 1 0 0 p ) ， 端点相同的边称为平行边( p a r a l l e le d g e ) 或重边( m u l t i p l ee d g e ) 。不与任何边相 关联的顶点称为孤立点( i s o l a t e dv e n e x ) ，只有一个顶点的图称为平凡图( t r i v i a l g r a p h ) ，无环并且无重边的图称为简单图( s i m p l eg r a p h ) ，任何不同两顶点都有 边相连的简单图称为完全图( c o m p l e t eg r a p h ) 。 对于有向图d ，去掉边上的方向得到的无向图g 称为d 的基础图( u n d e r l y i n g g r a p h ) ，反之，任何一个无向图g ，将它的每条边赋予一个方向得到一个有向 图d ，称d 为g 的一个定向图( o r i e n t e dg r a p h ) 。 图g 中与顶点v 关联的边数( 一条环要计算两次) 称为p 的度( d e g r e e ) ，记 作d e g ( v ) 或d ( v ) ；用( 6 ) 和d ( g ) 分别表示g 的最大度( m a x i m u md e g r e e ) 和最小度 ( m i n i m a ld e g r e e ) 即： a ( g ) = m a x l d ( v ) ：v 以g ) ， 6 ( g ) = m i n d ( v ) ：v y ( g ) 】 对于有向图d ，进入顶点v 的边数称为v 的入度( i n d e g r e e ) ，记作i d ( v ) ；离 开顶点v 的边数称为v 的出度( o u t - d e g r e e ) ，记作o d ( v ) 。显然，在有向图d 中， 任意顶点v 的度数以v ) = i d ( v ) + o d ( v ) ，显然有下列结论； 1 每个图g 中，顶点度数总和等于边数的二估。即 1 ，每个图g 中，顶点度数总和等于边数的二倍即 d ( v ) = 2 1 e ( g ) i v v ( g 、 7 ! 查茎! 堕翌宣鱼里堕型些茎一 2 每个图中，度数为奇数的顶点必定是偶数个； 3 在任何有向图中，所有顶点的入度之和等于所有顶点的出度之和 在研究和描述图的性质以及图的局部结构中，子图的概念占有重要地位。 设两个图胃和g ，若v ( t t ) y ( g ) ，e ( h 1 e ( g ) 且丑中边的重数不能超过g 中对 应边的重数，则称h 是g 的子图( s u b g r a p h ) ，记作日g ；若h g 且h g ，则 称h 是g 的真子图( p r o p e rs u b g r a p h ) ；若h g 且y ( h ) = y ( g ) ，则称h 是g 的生成 子图( s p a n n i n gs u b g r a p h ) 或支撑子图。设v ( g ) 且v o o ，以为顶点集，以 两个端点均在中的全体边为边集的g 的子图，称为的导出子图( i n d u c e d s u b g r a p h ) ，记作g 【；设岛e ( g ) 且e o 0 ，以e o 为边集，以e o 中的边关联 的全部的顶点为顶点集的g 的子图，称为e o 的导出子图，记作g e o 特别， 若v ocv ( g ) 且v o 0 ，则以g 一表示从g 中删去内所有点以及与这些顶 点相关联的边所得的子图，若v o = i v ，常把g 一简记为g v 。类似地，设 o e ( g ) 且e o 0 ，g e o 表示在g 中删去岛中所有边所得的子图，同样把 g 一e 简记为g e 。 ，路和连通图是图论中两个最基本的概念。如果图g 中有有限个顶点和边交替 序列w = v o e l v l e 2 v 2 e k v k ，其中e i e ( g ) ，i = 1 ，2 ，k ，v ，y ( g ) = 0 ，1 ，2 ，k 且e f _ v l _ lv j ，则称w 是图g 的一条道路( w a l k ) 或链( c h a i n ) ，顶点v o 和称为w 的 端点，顶点v d i = 1 ，2 ，k 一1 ) 称为的内点，k 为w 的长；各边相异的道路称为 迹( t r a i l ) ；内部顶点相异的迹称为路( p a t h ) ，记作p ( v o ，v k ) ；两个端点重合的迹 ( 即闭迹) 称为回路( c i r c u i t ) ；两个端点重合的路( 即闭路) 称为圈( c y c l e ) ，长 为k 的圈称为缸圈( k c y c l e ) ，3 - 圈常称为三角形( t r i a n g l e ) 设w = h i e l v l e 2 ”2 e k v 是有向图d 中u v 链( 迹、路) ，指定w 的方向从“到v ，若w 中所有边的方向 与此方向一致，则称w 为d 中从u 到v 的有向链( 迹、路) ，其中“为起点，v 为终点有向闭路称为有向圈关于圈有下列基本定理： 定理1 2 1 【2 7 若简单图g 中每个顶点的度数至少是k ( k 2 ) ，则g 中必然 含有一个长度为k + 1 的圈 定理1 2 2 2 7 1 设简单图g 中每个顶点的度数至少是3 ，则g 含有偶圈 设“和v 是图g 的两个顶点，若在g 中存在一条“一v 路，则称u 和v 是连通 的( c o n n e c t e d ) 。若图g 中任何两个不同的顶点均是连通的，则称图g 为连通图 ( c o n n e c t e dg r a p h ) ，否则称图g 为非连通图或分离图( d i s c o n n e c t e d g r a p h ) 。易验 证，顶点集矿( g ) 上顶点间的连通关系是y ( g ) 上的等价关系，该等价关系确定 了v ( g ) 的一个划分f y l ， ，使得当且仅当两个顶点“和v 属于同一个子 8 第一章引言 集时，“和v 才是连通的，k 在g 中的导出子图g i ve ，g u 】，g 称为g 的 连通分支或分支( c o m p o n e n t ) ，m 称为g 的连通分支数( n u m b e r o fc o m p o n e n t s ) ， 记作c o ( g ) = m 在图g 中顶点“和v 是连通的，“和v 的距离是指u 和v 两点间最短路的长， 记作如( “，v ) 或d ( u ，v ) ，若“和v 不连通，规定d ( u ，v ) = + o o 图g 的两个顶点之间 的最大距离称为图g 的直径( d i a m e t e r ) ，记作d i a m ( g ) ，即 d i a m ( g ) = m a x d ( u ，v ) ：“，v v ( g ) l 树是简单连通图连通的无圈图称为树( t r e e ) ，树中度数为】的顶点称为树 叶( 1 e a f ) ，度数大于1 的顶点称为分支点( b r a n c hp o i n t ) 或内点( i n n e r p o i n t ) 一个 无圈图称为森林( f o r e s t ) ，它的每个连通分支都是树我们有下列已知定理： 定理1 2 3 每棵非平凡树至少有两个树叶 设e 是g 的一条边，若g e 的连通分支数比g 多，即叫( g p ) c o ( g ) ，则e 屉g 的一条割边( c u te d g e ) 或桥 定理1 2 4e 是图g 的割边当且仅当e 不包含在图g 中任一圈中 定理1 2 5 一个连通图是树当且仅当它的每条边都是割边 设丁是有向圈，若丁的基础图是树，则称r 是有向树( d i r e c t e d t r e e ) ；仅一 个顶点的入度为0 ，其余所有顶点的入度为】的有向树称为根树( r o o t e d t r e e ) 。 入度为0 的顶点称为根( r o o t ) 。出度为0 的顶点( 即度数为1 的顶点) 仍称为 树叶，出度不为0 的顶点称为分枝点或内点。由根到某一顶点v 的有向路的长 度，称为顶点v 的层数( 1 e v e l ) ；根树的高度就是顶点层数的最大值。如果在 根树中规定了每一层上的出度的次序，这样的根树称为有序树( o r d e r e dt r e e ) ； 每个顶点的出度不大于m 的有序根树称为, q z 叉树；所有树叶层数相同的完全 卅叉树称为正则m 叉树 设v 是图g 的顶点，如果g v 的连通分支数比g 多，即c o ( g v ) ( g ) 。则 v 是g 的割点( c u tv e r t e x ) ；没有割点的非平凡连通图称为块( b l o c k ) ，g 中不含 割点的极大连通子图称为图g 的块 如果图g 的顶点集的一个真子集丁满足g t 不连通或是平凡图，则称r 是g 的点割( v e r t e xc u t ) ；如果g 的边集的真子集s 满足g s 不连通或是平凡 图，则称s 是g 的一个边割( e d g ec u t ) 。设g 是连通图，则称“g ) = m i n “r i ：7 是 g 的点割 为g 的点连通度( v e r t e xc o n n e c t i v i t y ) 或连通度；显然，当g 是平凡图 9 叶永升：图和有向图的测地数 或不连通时，k ( g ) = 0 。若k ( g ) k ，则称g 是k 一连通的( k - c o n n e c t e d ) ；于是所 有非平凡连通图都是1 连通的。类似地，称 ( g ) = m i n i s l ：s 是g 的边割 为g 的边连通度( e d g ec o n n e c t i v i t y ) 。显然，当图g 是平凡图或不连通时， ( g ) = 0 。 若 ( g ) k ，则称g 是k 一边连通的( k e d g e c o n n e c t e d ) ；于是所有非平凡连通图 都是1 边连通的。一个图的连通度，边连通度和最小度之间有下列关系： 定理1 2 6 5 】对于图g ，有f ( g ) ( g ) 6 ( g ) 设g = ( v e ) 是简单图，s v ，s 0 ，若s 中任意两点在g 中均不相邻，则称 s 是g 的一个独立集( i n d e p e n d e n ts e t ) 如果g 不包含使i s i l s i 的独立集s ，则 称s 为g 的最大独立集( m a x i m u m i n d e p e n d e n ts e t ) 图g 的最大独立集的顶点数 称为g 的独立数( i n d e p e n d e n tn u m b e r ) ，记为d ( g ) 为了揭示图的结构性质，人们引入了许多参数，如匹配数，覆盖数 和控制数等。下面我们介绍其中一个重要的参数一图的测地数( g e o d e t i c n u m b e r ) 。对于图g 中的两点u 和v ，u v 测地线( g e o d e s i c ) 是路长为d ( u ，v ) 的 “一v 路；集合l ( u ，v ) 表示位于g 中w v 测地线上所有点的集合；对于非空子集 s y ( g ) ，l ( s ) = u 。舀l ( u ，v ) ；如果i ( s ) = y ( g ) ，则称s 是g 测地集；并把测地集 的最小基数称为g 的测地数，记为g ( g ) 类似可以定义有向图d 的测地线，测 地集和测地数，不过应该注意的是：在有向图中，“一v 测地线和v 一“测地线 是两条不同的有向路( 或弧) ；l ( u ，v ) 表示所有位于“一v 测地线和v 一“测地线 上的点集。对于图g ，g 的下测地数( 1 0 w e rg e o d e t i cn u m b e r ) ，记为g 一( g ) ，被定 义为g 的所有定向图中测地数最小值；g 的上测地数( u p p e r g e o d e t i cn u m b e r ) ， 记为旷( g ) ，被定义为g 的所有定向图中测地数的最大值即： g - ( g ) = m i n g ( d ) ：d 是g 的定向图1 ： 矿( g ) = m a x g ( d ) ：d 是g 的定向图l 在图论中，图的运算也是人们研究的重要内容。通过图的某种运算，我 们可以用两个或两个以上较小和较简单的图生成一个较大和较复杂的图，由 于较小和较简单的图的结构特性容易把握，从而把握住较大和较复杂的图的 结构特性，因此对图的运算的研究是很有价值的。 设g 1 = ( u ，i ) 和g 2 = ( ，e 2 ) 是两个图，若g 】和g 2 没有公共顶点，则 称它们是不相交的( d i s j o i n t ) ；若g l 和g 2 没有公共边，则称它们是边不重 的( e d g e d i s j o i n t ) ；g 】和g 2 的并( u n i o n ) 被定义为g i 和g 2 中所有边组成的 图，记为gjug 2 ，即g lug 2 = ( v iuk ，e lue 2 ) ；g l 和g 2 的交( i n t e r s e c t i o n ) 1 0 第一章引言 记为g 1ng 2 ，即g 1ng 2 = ( v inv 2 ，e 1n 易) ；设g 】和g 2 是两个不相交的简单 图，g l 和g 2 的联( j o i n ) 为图g = g ivg 2 ，其中图g 满足v ( g ) = v ( g 1 ) uv ( g 2 ) ， e ( g ) = e ( g i ) u e ( g 2 ) u “v ：“v ( g o ，v y ( g 2 ) l ；g l 和g 2 的笛卡儿积( c a r t e s i a n p r o d u c t s ) 为图g = g 【g 2 ，其中图g 满足v ( g ) = v ( g i ) v ( g 2 ) ，g 中的两个顶 点( a ，b ) 和( c ，d ) 是邻接的当且仅当a = c 且b d e ( g 2 ) 或b = d 且a c e ( g 1 ) 设m ， v 是g 中两点，若u v 譬e ( g ) ，在“，v 之问加一条边所得的图，记为g + u p ，即 g + h v = ( k e u u v l ) ；若h v e ( g ) ，将边u v 收缩为一点所得的图，记为g 。龇类似 我们定义如下运算：对于任意两个不相交的图g 和h ，“，v 分别是g ，h 中的点， 在点“和v 之间加一条边的运算，记为g 。+ h l ，：使g 和仅在“，v 重合的运算，记 为g 。关于图的运算测地数是本文研究的重点。 1 3 主要研究结果 本节定理的编号采用它们在各自章节中出现的编号，其中未介绍的符号 和概念请对照它们相应的章节下面是本人所做的一些结果 定理2 1 ，2 对于n f 2 ，i = 1 ，2 ，r 且nj “2 怫，则 g ( k ”m ) = m i n n t ，4 定理2 2 2 设g ，h 是两个非平凡图，对于u y ( g ) ，v y ( h ) ，有 g ( g ) + g ( h ) 一2 g ( g 。+ h 。) g ( g ) + g ( 日) ； g ( g ) + g ( 1 4 ) 一2 g ( g 。o h v ) g ( g ) + 譬( 月) 定理3 3 1 假设g 和h 是非平凡图；那么对于“y ( g ) ，p y ( 日) ，有 g + ( g ) + 占+ ( 一2 g + ( g 。+ 凰) 占+ ( g ) + g + ( h ) ； g + ( g ) + g + ( h ) 一2 g + ( g 。o 峨) g + ( g ) + g + ( 1 - 1 ) 那么 定理3 3 2 设g 和h 是两个非平凡图，若“和v 分别是g 和疗的悬挂点 g + ( g 。+ 风) = g + ( g ) 十g + ( 日) g + ( g 。o h ，) = g + ( g ) + 矿( i t ) 一】 定理3 3 3 设g 和h 是两个非平凡图，那么对于“y ( g ) ，v 矿( h ) 有 g - ( g ) + g - ( 何) 一2 g - ( g 。+ 风) g - ( g ) + g ( 日) ； 叶永升：图和有向图的测地数 g 一( g ) + g 一( h ) 一2 g - ( g 。o h 。) g - ( g ) + g - ( h ) 定理3 3 4 设g 和日是两个非平凡图，且u 和v 分别为g 和日的悬挂点，那 么 g ( g 。+ 也) = g 一( g ) + g 一( t j ) 一2 ； 9 1 g 。o 巩) = g 一( g ) + g 弋) 一2 定理3 4 9 对于2 ，i = 1 ，2 ，且n 1 n 2 脚，则 g + ( 如1 n 2 ，m ) g ( k o ：。，) - 定理3 4 ，1 0 设g 和日是两个非平凡图，并且“和v 分别是g 和圩的悬挂点 若g + ( g ) g ( g ) 和g + ( ) g ( ，贝4 g + ( g 。+ 矾) g ( g 。+ h 。) g + ( g 。o h 、) g ( g 。0 1 l ) 定理4 2 1 设g 是非平凡连通图，如果g 包含某个最小测地集s ，在s 中存 在一点工使得g 中的任意点都位于x w 测地线上，其中w s ，那么 g ( g ) g ( g k 3 ) g ( g ) + 1 。定理4 2 2 设g 是阶数至少为3 的连通图，那么g ( g ) = g ( g k 3 ) 当且仅当存 在最小测地集s 和基于s 的测地族f 使得s 相对于f