（应用数学专业论文）h局部连通图的路圈性质.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名：五l 矧奄辱及 翩箨癖 学位论文版权使用授权书 本学位论文作者完全了解兰撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权越可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：三i 明颍 导师签字： 签字日期：2 0 0g 年舌月7 日签字日期：2 0 09 年多月7 日 山东师范，：学硕士学位论文 日一局部连通图的路圈性质 刘明颖 ( 山东师范大学数学科学学院济南。山东2 5 0 0 1 4 ) 中文摘要 路和圈是图的两种基本结构? 是分析和刻画图的有力工具有大量的实际问 题可以归结为图的路和圈问题所以这方面一直是图论中的热点研究领域关 于路和幽的进展已经取得了长足的发展这方而的研究成果和进展可参见文 献1 3 1 - f 1 6 事实上图论中三大著名难题之一的日。仇m d 佗问题本质上也是幽的 路和圈问题经过几十年的发展图的路圈性质所涉及的内容日益丰富和具体 路的方面包括图的n m i ，z o ”一路f 可迹性) 最长路o 仇m o n 连通泛连通路可 扩等等：圈的方面包括图的日n m m o n 圈最k 圈( 点) 泛圈完全圈可扩点不交 的圈圈覆盖等等 由于直接研究一般图的日n ”z 砒d 扎问题往往比较困难于是人们转而研究不 含有某些禁用子图的图类，继b e i i l e k e l 9 6 8 1 9 7 0 年发表的关于线图性质的两篇 文章f 1 7 j f 1 8 1 之后人们开始关注包含着线图的无爪图7 ( j 年代未8 0 年代初是 研究无爪图的一个非常活跃的时期关于无爪图方面的部分优秀成果可参考f 2 1 - f 4 1 f 1 9 h 3 3 1 f 3 4 i 是关于无爪图的综述性的文章另外无爪图的概念也被从不同角 度推光到了更大的图类如半无爪图几乎无爪图( 凡1 4 ：2 ) 图d c 丁图等1 9 9 8 年a a i 伽让c e 在f 7 1 中定义了一种包含无爪图的更大图类一半无爪图且给出了关于半无 爪图的路和圈方面的一些结果之后，很多专家学者相继做了大量的工作来研究 这类图的日n m 班d 凡问题且将无爪图中的许多非常好的结果推广到了半无爪图其 中某些进展可参考f 3 5 一f 3 7 1 1 9 9 4 年，z r 矿? 五o e 天定义了一种包含无爪图的更大 的图类几乎无爪图之后亦出现了不少研究这类图的日8 m 砒。扎问题的学术论文 如【3 9 卜 4 1 对f y ( g ) 若g f v ( u ) 1 是连通的则称t 是g 的一个局部连通的点若g 的任一 点都是局部连通的点则称g 是局部连通的在局部连通的定义提出之后张存全 在1 9 8 9 年提出了半局部连通的定义，研究了无爪图在半局部连通条件下的一些 性质滕延燕和尤海燕在2 ( ) u 2 年定义了几乎局部连通而赖宏建在2 0 0 4 年提出了 三角连通的概念，证明了无爪图在三角连通下的一些结果曲晓英又把这些结果 推广到了半无爪图和拟无爪图我们是在他们的启发下提出的日一局部连通的概 1 山东师范大学硕士学位论文 2 念初步讨论了k 2 一局部连通下无爪图的一些性质人们相继又提出了许多不同 的相关定义如：几乎局部连通、半局部连通、三角连通、2 阶邻域连通等日一局 部连通图是我们在研究不同图类结构的基础上所提出的一种新的图类。 z 如扎汝兄矿硒沈舟在1 9 9 7 年提出了闭包的概念并解决了无爪图中的一系列日n m m d 佗问题z d e n 芭七r 功五沈膏所定义的闭包着眼于对局部连通的点的邻域增加 边l ，b 7 d e r s 仇f 和丁r d m 仇e 7 先后又提出了虬一闭包和圪一闭包。r d m n n c n f z n 在 2 0 0 1 年提出了a 一闭包和g 一闭包本文在他们的启发下定义了两种闭包虬一闭 包和 一闭包并且初步讨论了无爪图和半无爪图在这两种闭包下的一些性质 本篇论文主要研究了k 2 一局部连通下无爪图和半无爪图的路和圈问题以及 无爪图和半无爪图在我们定义的两种新闭包下的一些性质 在第一章中我们主要介绍了本文的研究背景以及已有的一些结果以及文 章中所涉及的一些概念和术语符号 在第二章中我们具体讨论了日局部连通图的一些性质得出了下面的几个 结果： 定理2 1 设g 是连通、尬局部连通图则g 是2 连通的或者g 竺r ( k 1 2 ) 推论2 2 阶2 m ( 研2 ) 的连通一局部连通无爪图是2 连通的 定理2 3 设g 是a 2 一局部连通无爪图，v z y e ( g ) 尸= z l z 2 z * 是g n ( z y ) 中任意两点问的最短路则七6 定理2 4 设g 是人- 3 一局部连通无爪图g e z 是g 的任一三角形则g 人r ( z 可： ：) 1 中任意两点间最短路的长不超过7 在第三章中我们研究了尬一局部连通图的圈可扩性：证明了下面的结果： 定理3 1 6 设g 是阶不小于4 的连通a ，2 局部连通的无爪图则g 是 n m i 2 d 佗的 完成人，2 局部连通的无爪图日o m 砒d n 性的证明之后我们开始考虑它的圈可 扩性我们发现这一类图如果满足条件6 3 ，那么完全圈可扩性就成立于是得到 下面的定理 定理3 2 3 设g 是6 3 的连通、鲍局部连通的无爪图则g 是完全圈可扩的 在第四章中，我们定义了两种闭包：憋一闭包和k ：一闭包并证明了下面的结 果： 定理4 2 3 设g 是无爪图z 可是无爪图g 中任一条适宜边g 。，是对g 在z y 作 k 2 局部完备后所得的图，则g 2 ，仍为无爪图 山东师范人学硕十学位论文 推论4 2 4 无爪图的k 2 一闭包仍是无爪图 定理4 2 5 设g 是半无爪图z y 是图g 中任。条适宜边g 7 是对g 在z y 作 a ，2 一局部完备后所得的图，则g 仍为半无爪图 推论4 2 6 半无爪图的凡2 闭包仍是半无爪图 定理4 3 1 设z 可是无爪图g 中任一条适宜边g 是对g 在z y 作一局部完备 后所得的图，则g7 仍为无爪图 推论4 3 2 无爪图的“一闭包仍是无爪图 定理4 3 3 任一图的形一闭包存在且唯一 定理4 ，3 。4 设g 是半无爪图z 秒是图g 中任一条适宜边g 7 是对g 在z 彭作 “一局部完备后所得的图，则g 仍为半无爪图 推论4 3 5 半无爪图的凡：一闭包仍是半无爪图 在第五章中我们研究了k 1 4 一受限图的圈可扩性证明了下面的结果： 定理5 5 连通几乎局部连通爪心独立的k 1 4 一受限图是完全圈可扩的 关键词：完全圈可扩：盘m 班d 咒：闭包：一闭包： ，：一闭包。 分类号：0 1 5 7 5 3 4 p a t h sa n dc y c l e si n 日一l o c a u yc o n n e c t e dg r a p h s m i n g y i n gl i u s c h o o lo fm a t h e m a t i c a ls c i e n c e s ，s h a n d o n gn o r m a lu n i v e r s i t y j i n a n ，s h a n d o n g ，2 5 0 01 4 ，p r c h i n a a b s t r a c t r a t n sa n dc y c j e sa r et 弋v ob a s i cs t r u c t u r e so fg r a p h s 工nf a c t m a n vd r a c t i c a i p r o b i e m sc a nb ea t t r i b u t e dt ot h ep r o b l e mo fp a t h sa n dc y c l e s ， t h e r e f 6 r e t h e r e s e a r c 上1 a b o u tt h c i 上li s v e r ) a c t i v e 7 l l a ti sm o r c t 1 1 ef a n l o u sh a m i l t o i lu r o b l e m l sa b o u tp a t h sa n dc y c l e so fg r a p hi ne s s e n e e a f c e rt h ed e v e l o p m e mf b rd o z e n s o 上y e a r s t h ec o n t e n t si np r o p e r t i e so fg r a p h s p a t ha n dc v c l eb e c o m em o r ea n d m o r er i c ha n ds p e c i 矗c t h ep r o p e r t i e so f p a t hi n c l u d eh a m i l t o np a t h ( t r a c e a b i 王i “，) i o n g e s tp a t 上l p a n c o n n e c t l 、r l t ) p a c he x t e n s i b i l i t ) a n ds 。o n ：t h ep r o p e r t i e so fc v e l e i n c l u d eh a m i l t o nc y c l e 1 0 n g e s t c ) 7 c l e ( v e r t e x ) p a n c ) r c l i c i t y v e r t e d i s j o i n tc v c l e c y c l cc x t c i l s i b i l i t va i i ds o0 1 1 h ( w ( j v c r - 聊( ：a i l1 1 ( ) t ( 1 ( m ) 。t 1 1 ( 、a c tt l l a ti tk u s u a l l ) v e r 、d i f f i ( u l tt ( 时1 1 ( 1 、 h a m i j r o np r o b j e ml nt h o s eg r f 巾h sw i t h o u ta n ) r e s t r i c t i o n t h e nw et u r nt oe x d l o r e t n eg r a p h sn o tc o n t a i n i n gs o m ef o r b i d d e ns u b g r a p h ss u e ha sc l a l k f r e e ；r r a p h s t h e n r s tm o t l v a t l o nt o rs t u d ) h l gp r o p e r t i e so fc l a ? 一e eg r a p h sa p p a r e n t b a p p e a r e d f r o m b e l n e k esc h a r a c t e r i z a t i o no fl i n eg r a p h si nf 1 刁一 1 8 h o w e v e r ，t h em a i n i m p u l s et h a t t u r n e dt h ea t t e n t i o no ft h eg r a p ht h e o r yc o m m u n i t yt ot h ec l a s so fc l a w f t e e 霉，a p h s 矾a sg l v c ni n1 a t e7 0 sa n de a r l ) 8 0 s s o m ef a n l o u sr e s u l t sa b o u tc l a 7 f i e eg r a p h s c a nb es e e ni nf 2 一f 4 j ：f 1 9 - f 3 4 i na d d i t j o n ：t h ed e 矗n i t i o no fc l a w f e e ；r r a p hh a s b e e ne x t e n d e dt os e v e r a ll a r g e rg r a p hf a m i l i e si nd i 雎r e n tv i e w s ，s u c ha sq u a s i c l a w 上r e eg r a p h s ，a i m o s tc l a w e eg r a p h s ( k 1 4 ；2 ) 一g r a p h s ，d c tg r a p h se t c a a i n o u c h e 7 d e f i n e dan e wg r a p hf a m i l y q u a s i c l a w - f r e eg r 印h sa n dh ea l s og i v e ns e v e r a lr e i s u l t sa b o u tp a t h sa n dc y c l e si nt h en e wg r 印hf a m i l y a f c e rt h a t ，m a n yr e s e a r c h e r s h a v ed o i l eal o to fw o r kt os t u d yh a m i j t o np r o b l e mi n q u a s i c j a 、和f r e eg r a p h s 陋5 i 【37 a l m o s tc l 龋，- f t e eg r 印h sa r ed e f i n e db yz r 撕o6 r ；u e c e 七i n 3 8 i ti sa l s oal a r g e r g r a p hf a m i l yt h a nt h a to fc l a 肌f r e eg r a p h s h o w e v e r ，i ti sv e r yd i 伍c u l tt oe 赋e n dm a n v g o o dr e s u i t so fc l a w - 靠e eg r a p h st oa l m o s tc l a w - f r e eg r a p h s t h e r e f o r e ，y 如y a nt e n g a n dh a i y a ny b ug a 阿et h ed e 矗n i t i o no fs t r o n 9 1 ya l m o s tc l a r w 行e eg r a p h s 5 1 ，w h i c h 山东师范入学硕士学位论文 c o n t a i nt h ef a m 计o fc l a ? 一f r e eg r a p h sa n di sc o n t a i n e di nt h ef a m 沁o fa l m o s tc l a f r e eg r a p h s h o 矾p v e r m a n 、g o o dr e s u l t so fc l a w f r e eg r a p h st h a th a v en o tb e e n e x t e n d e dt oa l l o s tc l a w f r e eg r a p h sc a nb ee x t e n d e dt 。s t r o n g l 、a l m o s tc l 弧f r e e g r a p h ss u c r e s s f u l l v v 、，es 研av e r t e xt i sa i o c a l l ) c o n n e c t e dv e r t e xo fg r a p hg i ft h en e i g h b o ro f z i ngi sf o n n e c t o d i n19 8 9 c u n z u a nz h a n g g a v et h ( 、d e f i n i t i o no fq 1 】a s j - r o n n e ( t e d g r a p l l s a f c c i t l l a th cs t u d i e dt h cp r o p c r t i e so fc l a 、 ? 一士r c cg r a p l l sa n dq u a s i c l a _ f i e c g r a p h si nt h ec o n d i t i o n so fq u a s i l o c a l l ) c o n n e c t e d i n2 0 0 2 、7 a n 、r a n r e n ga n dh a i y a nd e a n e da l m o s t1 0 c a l l 、c o n n e c t e dg r a p h s t h et r i a n g u l a r l ) c o n n e c t e dg r a p h 氇喀d e f i n e db ) h o n g j i a nl a ii n2 0 0 4 ，h ea l s o g a v em a n 、g o o dr e s u l t so fc l a w f r e e g r a p h su n d e rt h i sc o n d i t i o n x i a o 、i n gq uh a se x t e n d e dt h e s er e s u l t st oq u a s i c l a 瓢- f r e ( 、g r a p ha n ds t r o n 9 1 ) a l m o s tc 1a 珩e eg r a p h s i nt h ( ) 1 a t t e rv e a r sm a n 、r e l a t e d d c f i n i t i o n ss u c ha s2 一o r d e ri l c i g h b o i c o n n e c t e d n c l o c a lc o l l n e c ta n ds oo n t h e d e f i n i t i o no ft h e 日一l o c a lc o n n e c t e dg r a p h a sg a ，v po nt h eb a s i co ft h er e s e a r c ho n m a n j d i f k r e n tg r a p h s i n1 9 9 _ 。z d e 咒淤咒撕矗亡e 七d e f i n e dt 1 1 ec o n c e p to fc l o s u r e a n dg a v em a 琊g o o d r e s u l t so ft h eh a m i l t o np r o b l e m t h i sc l o s u r em a i n k i n c r e a s e se d g e si nt l l en e i 曲b o r o ft h el o c a l l ) c o n n e c t e dv e r t e x e s l a t t e r 日j b r d e r s ”l “a n d 丁r d ，n 7 e fd e f i n e dt h e 厶，4 一r l ( ) s u r pa n d 上f ：一c l o s u r e 片d ， ，l p n d a ( 1 e n e dt h p ( - 一( 1 0 s i l r pa n d ( 毛一c l o s u r e t h e s p n l 【j t i y a t e ：dw ct od o f i u ct h c 2 一c k j s u r ea l l dk ；一c l u s u i c i nt h i sp a p e i w cn l a i l l l 、r c s e a r c ht h e p a t h sa n dc ，d e so fc l a 乙矗e eg r a p h sa n dq u a s i c l a w f t e eg r a p h si nt h ec o n d i t i 。no f 虬一1 0 c a lc o n n e c t i o n a n ds o m ep r o p e r t i e so f - 一c l o s u r ea n d 一c l o s u r e o fc l a 瓢- f t e eg r a p h sa n dq u a s i - c l a w f r e eg r a p h s w h i c hw ed e f l n e di nt h i sp a p e r i nt h e 矗r s tc h a p t _ e r 伦g i v eab r i e fi n t r o d u c t i o na b o u tt h eb a s i cc o n c e d t s t e r m i n o l o 舀e sa n ds y m b o l sw h i c hw i l lb eu s e di nt h i sp a p e r i nt h em e a n t i m e w e a i s og i v es o m er e l a t e dr e s e a r c hb a c k g r o u n d sa n ds o m ek n o w l lr e s u l t s i nt h es e c o n dc h a p t e r w em a i n l ) s t u d yt h ) p r o p e r t i e so fh - l o c a l l yc 。n n e c t e d g r a p h sa n ( 1g i v et l l ( 、f ( ) 1 1 0 、) l n gr e s u l r s ： t h e o r e m 2 1i fgi sa ( ：( ) n i l e c t p dk 2 1 0 c a l l 、t ( o i l n e c t e dg r a i ) h t h e ng i s2 c o n n e c t e do rg 兰b ( 耳1 2 ) t h e o r e m 2 2e v e r yc o n n e c t e d n l o c a i l yc o n n e c t e dc l a w - 舶eg r a p h o f o r d e r 2 m ( m 2 ) i s2 c o n n e c t e d 5 山东师范大学硕十学位论文 6 t h e o r e m 2 3l e tgb eac o n n e c t e dk 2 1 0 c a l l ) c o n n e c t e dc l a 矾- _ 行e eg r a p h ，a n d f o rv z 可e ( g ) p = z l z 2 z ki st h es h o r t e s tp a t hb e t w e e na n yt w od i 丘i e r e l l t v e r t e x e s t h e n 七6 t h e o r e m 2 4l e tgb eac o n n e c t e d 人，3 一l o c a l l ) c o n n e c t e dc l a w - f r e eg r a p h g z 鲈：) i sao fg t h e nt h el e n 昏ho ft h es h o r t e s tp a t hb e t w e e na n yt w ，o d i f - f e r e n tv e r t e x e so fg 人7 ( z y ：) i sn o tm o r ct h a n7 i nt h et h i r d ( h a p t e r r em a i n l ) e x t e n dt h er e s u l to ft h et h i r dc h a p t e r t h e o r e m 3 1 - 6i fgi sac o n n e c t e d 虬1 0 c a l l ) c o n n e c t e dc l a w 一矗e eg r a p hw i t h g l 4 t i l e ng i sh a i i l i l t o n i a l l t h e o r e m 3 2 3i fg i sac o n n e c t e d k 2 一l o ( a 1 1 ) p o n n e r t e dc l a w - f r e e lg r a p hw i t h 巧( g ) 23 t h e ngi sf u l l yc y c l ee x t e n d a b l e i nt h ef o r t hc h a p t e r ：w eg i v et h ef o l l o w i n gr e s u l t sa b o u tj 也一c l o s u r ea n d 醚一c l o s u r e t h e o r e m4 2 3l e t ( ；b eac l a ? 一f r e eg r a p ha n dl e t 。yb ea ne l i g i b l ee d g e o fg l e tg z ”b eak 2 1 0 c a lc 。m p l e t i o no fga tt 可t h e nt h eg r a p hg 。i ss t i l la c l a m - f r e eg r a p h c o r o l l a r y4 2 4 i fgi sac l a 。一f r e eg r a p h t h e nt h e 2 一c l o s u r eo fgi s a c l a 瓢f r e eg r a p h t h e o r e m4 2 5l e tgb eaq u a s i c la ：w f t e eg r a p ha n d1 e tz 可b ea ne l i g i b l e e d g eo fg l e tg 。b eak 2 1 。c a lc o m p l e t i o no fg a tz 可t h e nt h eg r a p hg z i ss t i l l aq u a s i c l a w - f r e eg r a p h c o r o l l a r y4 2 6 i fgi saq u a s i 一( ：l a 矾。f r e ( jg r a p h t h e nt h p 凡2 一c l ( ，s u r eo fgi s aq u a s i c l a w f r e eg r a p h t h e o r e m4 3 1l e tgb eac l a w f r e eg r a p ha n dl e tz yb ea ne l i g i b l ee d g e o fg l e tg ：= b ea 砭一1 0 c a lc o m p l e t i o no fga t z 可t h e nt h eg r a p hg 毛i ss t i l la c l a w 一e eg r a p h c o r o l l a r y4 3 2 i fgi sac la _ w f r e eg r a p h t h e nt h e 砭一c l o s u r eo fgi sa c l a w 一丘e eg r a p h t h e o r e m4 3 3l e tg b eaq u a s i c l a w - 矗e eg r 印ha n dl e t z 3 ，b ea ne l i g i b l e e d g eo fg l e tg 毛b ea 砭一1 。c 甜c o m p l e t i o n 。fg a tz 耖t h e nt h eg r a p hg 毛i ss t i u aq u a s i c l a 瓢f r e eg r a p h 山东师范大学硕士学位论文 c o r o l l a u r y4 3 4 i fgi saq u a s i c l a 7 f r e eg r a p h t h e nt h e 一c l o s u r eo fgi s s t i l laq u a s i c l a 矾- 靠e eg r a p h t h e o r e m4 3 5l e tgb ea 善；r a p h t h e nk 2 ，( g ) i sw e l ld e a n e d i nt h el a s tc h a p t e r w eg i v et h e 幻u o w i n gr e s u l ta b o u tt h ep r o p e r t 、o fc 、r c l e e x t e n d a b l ei n ，1 4 ：2 一g r a p h t h e o r e m5 5l e tgb eac o n n e c t e da l m o s tl o c a l l j c o n n e c t e dk 1 4 ：2g r 印h w i t hi n d e p e n d e mc e i l t e r so f i n d u c e dd a w ( 1 3 ) i sf u n ) c y c l ee x t e n d a b l e k e y w o r d s ：“1 ) c y c l ee 热e n s i o n ：h a m i l t o n ：c l o s u r e ：一c l o s u r e = 虬一c l o s u r e c l a s s i f i c a t i o n ：0 1 5 7 5 7 山东师范大学硕士学位论文 8 第一章预备知识 1 1 符号概念介绍 本文仅考虑有限无向简单图所使用的记号和术语约定如下其中未加说 明的部分请参照文献f 1 1 设g 是一个图1 ，( g ) 三( g ) 分别表示g 的顶点集和边集对于r z 可l ( g ) s 丁v 7 ( g ) 及g 的子图日：令 人7 ( f ) = u 、，( g ) ：u 。e ( g ) ) a p = a ( ) u 秽) 人0 ( u ) = j 7 i ( t ) ns ，八0 ( 丁) = u ，丁a 0 ( t j ) ? b 丁 = u 。丁人0 p 人j ( h ) = k ( 1 厂( 日) ) h ( 丁) = k ，( 日) ( 丁) 8 ( ) = 一日( 口) a ”( = a 台一日 e ( s 丁) = s e f g ) ：5 s f 丁) 口2 ( g ) = m i ( 1 n ( 丁) i + i 7 ( ! ，) ：t 可岳e ( g ) ) g 的由s 导出的子图记为g 【翻1 i = ( 日) i 称为h 的阶 将图g 中与t 关联的边的数目l 做顶点l ，的度记为( f g ( r ) 即( f g = l ( u ) i 在不引起混淆的前提下也简记为d ( t ) 用6 g ：g 分别表示g 中顶点的最小度和最 大度也常简记为巧 如果图g 中不存在詹一1 个顶点的集合分离g 则称g 是七一 连通的图g 的连通度k ( g ) - m a x 鼻：g 是七一连通的，。设2 i 厂( g ) 。如果( t ) 的导 出子图g f ( r ) 1 是七一连通的则称 是g 的一个局部七一连通点如果图g 的每一个 顶点都是局部七一连通的则称g 是局部矗一连通的 设p = z l z 2 z t 为图g 的一条路筑巧y ( p ) ( 1 i j ) 用z - 2 和z 分 别表示尸上的点z 川和z 州z 产1 和z _ 1 也分别记为z 产，z f ；用z i p q 和巧a i ( j ) 分 别表示p 的子路z i z + 1 。，和z ，。卜1 设c = u l u 2 u 1 是图g 中的圈，让，y ( c ) ( 1 i 歹r ) ，用可2 和r 产2 分别表示c 上的点耽一f 和+ 2 口_ 1 和u 产1 也分别记为u _ 和口产；用饥c 吩和c 分别表 示c 上的路+ 1 吻和仇一1 ( 这里点的下标均模r ) 以g 的顶点乱，u 为两端点的路叫做g 的( 乱，u ) 一路设p 是g 的一条( u ，u ) 一路，如 果g 中不存在( u ， ) 一路p 7 ，使得v ( p 7 ) cv ( 尸) 且ip ，i l j p l ，则称p 为g 的一条极 山东师范大学硕士学位论文 短( ，u 1 ) 一路显然连通图中任意两点之间都有极短路以顶点t 1 - 为两端点的最 短路的路长叫做u r 之间的距离记作d f t u ) 经过g 中每个顶点恰好一次的路( 圈) 称为( g 的) h a m i l t o n 路( 圈) 若g 中存在 一个h a m i l t o n 圈则称g 是哈密顿的 如果v 牡f y ( g ) 图g 都有( 乱t ，) 一h a m i l t o n 路则称g 是h a m i l t o n 连通的若 v u t 1 厂( g ) 图g 都有长为f ( d ( u u ) f 1 1 【? ( g ) l 一1 ) 的f “r ) 一路则称g 是泛连 通的如果图g 满足：对咖2 一v ( g ) 及g 的任意一条f “t ) 一路尸只要17 ( 尸) l | 、( g ) j 就存在g 的f “t ，) 一路j p 7 使得17 ( p ) c1 厂( p 7 ) 且 17 ( 尸，) j = ( 尸) i + 1 则 称g 是路可扩的满足条件的p 7 叫做尸的扩路 令1 17 ( g ) l = n 。若对任意的e ( 3 f 咒) g 中都有长为f 的圈则称图g 是泛圈 的若对任意的，( 3 ，咒) g 中过任意点都有长为珀勺圈则称图g 是点泛圈的 如果图g 满足：( 1 ) g 的每个顶点都在长度为3 的圈上：f 2 ) 对g 中任意一个圈c ： 只要1 1 厂( c ) 2 。则n a i ( z ) o ( i = 1 2 齐) 从而g n ( z 玑) ：不连通这与g 的n 2 一局 部连通性矛盾所以= 2 ，即g 一丁只有两个分支。4 1 和。4 2 要保证g ( z 彰1 ) 连通必 有h 4 1 ) = 寥1 ) ，同理a 2 ) = y 2 ) 从而g 笺b 定理得证 推论2 2 阶2 m 一1 ( 伪2 ) 的连通一局部连通无爪图是2 一连通的 证明假设图g 是阶2 m 的连通一局部连通无爪图：但g 不是2 一连通的设丁 是g 的割点，则由g 是无爪图知g z 有且只有两个分支4 和b ，且aj e 7 均为g 的完全 子图 由于i g z i 2 m l ，所以a 和j e 7 中必有个，其顶点数2m 不妨设| | a 仇从a 中任取一点t a 中余下的点与z 组成的集合记作c ，则g f c 是的完全子图 且阶m 在g q 中任取一个，显然g 是由分支b 和点u 及c 中余下的部分 1 5 山东师范_ j 学硕士学位论文 组成的：即g 】不连通。这与g 是人，m 一局部连通图矛盾推论得证 定理2 3 设g 是k 2 一局部连通无爪图，v z e ( g ) p = 丁1 t 2 z 七是g n ( z 矽) 中 任意两点问的最短路则知墨6 证明假设j u e ( g ) p = z 1 t ：z 是 中某两点间的最短 路、且七27 易证u 和、都不能与 z l z 2 z 七) 中的多于4 个的顶点相邻事实上若u 与其中5 个 顶点z z z 娟相邻( 其顶点按下标递增的顺序排序) 则g 钆z 小。z ；。) 兰 k 这与g 是无爪图矛盾 由于矗27 ，所以前7 个点必然有3 个点只与钉和t ，中一个点相邻而余下的点只 与另一个点相邻不妨设与“相邻的顶点为3 个且为巧。奶。：z 如同样设1 1 2 歹3 7 由于彻j ? z 如譬e ( g ) 所以g 钆巧，z 弦t ) 竺k 1 3 这与g 是无爪图矛 盾所以假设不成立，从而定理得证 定理2 4 设g 是k 3 一局部连通无爪图g ( z 秒： j 是g 的任一三角形，则g 卜( 丁 y ：) ! 中任意两点间最短路的长不超过7 证明设g 是虬一局部连通无爪图g z 驴：) 是的任三角形儿t 是g 沙( z ：) 中任意两点g n ( z y ：) 中最短( 1 ) 路为尸：】2 圮其中f l = u 七= u 论断1 ：设是图中两点问的最短路，则v 1 i j 2 只要卜一j l 2 都有z ：毛 e ( g ) 论断2 ： z ，可，：) 中任意一点都不能与尸上的5 个点相邻 事实上，若 z y ，z ) 中存在一点( 不妨设为z ) 与尸上的5 个点乃。o j 。幻；相邻， 其中j i l j 2 蟊则由论断1 知g k 巧。，o j 。t j 。 竺k l ，3 ，这与是无爪图矛盾论断2 得 证 由论断2 及鸽巢原理知尼1 2 1 6 山东师范大学硕士学位论文 ( 1j 若七= 1 2 由论断2 知z y ：都至多与尸上的4 个点相邻而尸) ca ( z 秒：) ，所 以z ：可：都只与尸上的4 个点相邻且z 矽：三点中任意两点在p 上没有公共邻点 设丁与尸上的4 个顶点7 1 。f 。j 7 1 。j 。相邻其中) ：1 j 2 j 3 歹4 贝0 y 和：都不和 这4 点相邻从而，g k 幻，矗y 兰凡1 3 这与g 是无爪图矛盾所以f 1 2 ( 2 ) 若艮= 1 1 由论断2 及鸽巢原理知伽y 0 中任一点都至少与尸上的3 点相 邻否则若 z y ：) 中有一点f 不妨设为丁) 只与尸上的一点或两点相邻则p 上余 下的点中必有5 个顶点与可或：相邻这与论断2 矛盾而t ，( p ) c ( 7 可：) ：所以 丁：) 中必有一点与p 上的4 个顶点相邻不妨设该点为z ，且z 在p 上的邻点为屯。j ：岛。幻。 其中歹l 歹2 歹3 扎即丁与尸上其他点都不相邻由论断2 及鸽巢原理知p 上其 余7 点中必有4 点。如：时山( i 1 i 2 i 3 i 4 ) 与y 或：相邻( 不妨设为y ) 同样由论 断2 知：夥与p 上的其余点都不相邻从而由论断l 知g 【 z 岛。o 如y ) 竺凡这与g 是 无爪图矛盾所以膏1 1 ( 3 j 若厅= 1 0 由论断2 及鸽巢原理知 z 矽二) 中至少有一点与尸上的4 点相邻设 卫。与