（应用数学专业论文）st图的路和圈问题.pdf

独创声明 本人声明所呈交的学位论文足本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证节使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示谢意。 学位尊文作者妣茗叙 导师妣： 学位论文版权使用授权书 乏嘞 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被企阅 和借阅。本人授权学校可以将学位论文的全部或部分内容编入有关数据库 进行搜索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。( 保密的学位论文在解密后使用本授权书) 学能论文作者签名：詹敌 导师签名： 签字只； l j ：2 0 0 7 年| h 只 签字开期：2 0 0 7 年 月r 山尔师范人学硕+ 学位论文 【s 胡图的路和圉问题 李敏 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 路和圈是图的两种基本结构，足分析和刻画图的有力工具，有大量的实际问 题可以归结为图的路和圈问题，所以这方面一直足图论中的热点研究领域关 于路和劂的进展，已经取得了长足的发展，这方面的研究成果和进展可参见文 献【1 3 】- 【1 6 】事实上，图论中三大著名难题之一的日n m 小问题本质上也足图的 路和圈问题经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体 路的方面包括图的日a m m d m 路( 可迹性) ，最长路，日a m z f t 连通，泛连通，路可 扩等等；圈的方面包括图的日m “o n 圈，最长圈，( 点) 泛圈，完全圈可扩，点不交 的圈，圈覆盖等等 由于直接研究一般图的h n m 淝叭问题往往比较困难，于足人们转而研究不 含有某些禁用子图的图类继b e i n e k e l 9 6 8 ，1 9 7 0 年发表的关于线图性质的两篇 文章 17 】一【1 8 】之后，人们开始关注包含着线图的无爪图7 0 年代末8 0 年代初，足 研究无爪图的一个非常活跃的时期关于无爪图方面的部分优秀成果可参考2 卜 【4 】，【19 】一 3 3 】另外，无爪图的概念也被从不同角度推广到了更大的图类，如半无爪 图，几乎无爪图，( 甄4 ；2 ) 一图，d c t 图等关于点不交的圈也足人们热衷的一个问 题，一些成果可参考【9 】【1 2 】2 0 0 5 年，刘春房在【5 】中定义了一种新的图类一忙，小图， 即任意s 个点之j 至少含有条边，这类图的特点足其边的分布比较均匀，因而在 交通网络，通信系统，计算机的网络配茕等方面有着很典型的应用，本文就是研 究f s ，引_ 图的路圈性质 在第一章中，我们主要介绍了本文的研究背景以及已有的一些结果，以及文 章中所涉及的一些概念和术语符号 在第二章中，我们具体讨论了【s ，叫一图在不同连通度下关于路圈的几个结果： 定理2 1 3 设g 足肛连通的畴+ 2 ，l 卜图，则g 含日m 妣路 定理2 1 4 设g 足缸连通的噼+ l ，1 卜图，则g 含日n m i 如d n 圈 定理2 2 1 设g 是n 6 ) 阶连通【5 3 】一图，则g 中最长路的长度不小于n 一2 ， 且路长的界足紧的 山东师范入学硕+ 学位论文 定理2 2 2 设g 足n m 7 ) 阶连通【5 ，3 卜图，则g 中最长圈的长度不小于b 2 j ， 此界足最好可能的 定理2 3 2 二连通 5 ，3 卜图或者含有h 咖i f m 圈或者同构于d ，其中d ，3 ， l ，1 ，3 ，鲍，4 ，k l ，l ，4 ，或者d 足图2 3 卜图2 3 1 0 中的图， 推论2 3 3 设g 足顶点数不小于8 且6 ( g ) 3 的参连通【5 ，3 j 一图，则g 含有日n m 砒m 圈 在第三章中，研究了【4 ，2 卜图的路可扩性，得到下面的结果： 定理3 5 设g 足连通，局部2 - 连通的【4 ，2 卜图，或者i g l 同构于甄，l l ，3 ，或者f g i 足 路可扩的 在第四章中，研究了【5 ，3 】一图的圈可扩性，证明了下面的结果： 定理4 3 设g 足6 ( g ) 3 的连通，局部连通【5 ，3 卜图，则g 足完全圈可扩的，或 者g 型f ( f 见图4 3 ) 推论4 4 设g 足6 ( g ) 3 ，l g i 8 的连通，局部连通 5 ，3 卜图，则g 足完全圈可 扩的 在第五章中，研究了【4 ，2 1 一图的点不交圈，证明了下面的结果： 定理5 5 假设g 足n 3 七+ 2 ) 阶并且观( g ) 23 七的【4 ，2 卜图，则g 含有尼个点 不交的圈 关键词：【s ，小图；路可扩；完全圈可扩；点不交圈；日o m m o n 分类号：0 1 5 7 5 2 山东师范人学硕十学位论文 p a t h sa n dc y c l e si n s ，小g r a p h s m i nl i 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 强d o n gn o r m a lu n i v e r 8 i t y j i n a n ，s h a i l d o n g ，2 5 0 0 1 4 ，p r c h i n a a b s t r a c t p a t h sa n dc y c l 鹊a r et w ob 舾i cs t r u c t u r e so fg r 印h s i nf a c t ，m a n yp r a c t i c a lp r o b l e m s c a nb ea t t r i b u t e dt ot h ep r o b l e mo fp a t l l s 趴dc y c l e s t h e r e f o r e ，t h er e s e a r c ha b o u t t h e m 培v e r ya c t i v e w h a tl sm o r e ，t h ef a m o u sh 锄n t o np r o b l e m i sa b o u tp 砒h sa n d c y c l e so fg r a p hi n 鹤s e n c e a f t e rt h ed e v e l o p m e n tf o rd o z e l l so fy e a r s ，t h ec o n t e n t s i np r o p e r t i 岛0 fg r a p l 珂p a t ha 1 1 dc y c l eb e c o m e1 n o r ea l l dl n o r er i d l 锄l ds p e c i f i c t h ep r o p e r t i e so fp 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 l i t y ) ，1 0 n g e s tp a t h ，p a n c o n - n e c t i v i t y p a t he x t e n d s i b i l i t ya n ds oo n ；t h ep m p e r t i e so fc y c ki n c l u d eh 锄i l t o n c y c l e ，l o n g e s tc y c l e ，( v e r t e x ) p a n c y c l i c i t y v e r t e x d i s j o i n tc y c l e ，c y c l e 戗t e n 出i b i l 时 a n dg oo n h o w e v e r ，w ec a nn o td e n yt h ef a c tt h a ti t i su s u a l l yv e r ) rd i 币c u l tt os t u d y h a m i l t o np r o b l e mi nt h o s eg r a p l l sw i t h o u ta n yr e s t r i c t i o n t h e nw et u r nt oe ) ( p l o r e t h 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 c ha sc l a w f r e eg r a p h s t h e n r s tm o t i v a t i o nf o rs t l l d y i n gp r o p o r t i c so fr l a w f r c og r a p h sa p p a r ( m “ya p p ( ! a r “if r o m b e i n e k e sc h a r a c t e r i z a t i o no f1 i n eg r a p h si n1 1 7 h 1 8 卜h o w e v e r ，t h em a i ni m p u l s et 王l a t t u r n e dt h ea t t e n t i o no ft h e 铲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 r e eg r a p l l s w a s 百v e ni nl a t e7 0 sa n de a r l y8 0 s s o m ef a m o u sr e s u l t sa b o u tc l a w f r e eg r a p h sc a n b es e e ni n 【2 】一【4 】，【19 】一【3 4 】i na d d i t i o n ，t h ed e f i n i t i o l lo fc l a w f r e eg r a p hh a sb e e n e x t e n d e dt os e v e r a l l a r g e rg r a p hf a m i l i 幅i nd i 髓r e n tv i e w s ，s u c h 舾q u 嬲i c l a w f r e e g r a p h s ，a i m o s tc j a w 矗优g r a p b ，( i 4 ；2 ) 一g r a p l l s ，d c tg r a p h se t c a l s 0 ，t h e r ea r ea l o to fg o o dr e s u l t sa b o u tv e r t e 静d 埘o i l l tc y c l e si n 【17 】一【18 】l i uc l l u l l f a i l g 【5 】d e f i l l e d an e wg r a p hf a m i l y i s ，叫- g r 印l l s ，t h a ti s ，t h e r ea r ea t1 e a s tte d g e si ne v e r yi n c l u d e d s u b g r a p l l so fsv e r t i c e si ng r a p hg 【s ，t 卜g r 印l l sc 龇lb ei l ；e di l l t r a f i f i cn e t w o r k c o m l i l u l l i c a t i 0 1 l s ，t l l ec o l l 矗g u r a t i o i lo fc o i l l p u t e rl l e t w o r k s ，e t c i i lt l l i sp 印e r w e m a i n l yd i s c u s st h ep r o p e r t i e so fg r 印l l s p a t ha n dc y c l ei n 【s ，小g r a p l l s i i lt l l c 丘r s td l a p t c r w c 百v cs o i n cr c l a t t x lr 惴c a r c hb a c k g r o u i l l sa i l ds o i n ck l l o w i l r e s u l t s i nt h em e a n t i m e ，w ea l s og i v eab r i e fi n t r o d u c t i o na b o u tt h eb 鹪i cc o n c e p t s ， t e r n l 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 3 山东师范火学硕十学位论文 i nt h es e c o n dc h a p t e r ，w em a i n l y8 t u d yt h ep a t h sa n dc y c l e so ff 8 ，t 卜f a p h sa n d g i v et h ef o u o w i n gr e 8 m t 8 ： t h e o r e m 2 1 3l fg i 8a 虹c o n n e c t e d 阵+ 2 ，l 】- 扩印h ，也e ngh a 8ah o m 砒饥 p a t h t h e o r e m 2 1 4i fgi sa 缸c o n n e c t e d 陋+ 1 ，l 卜9 r 印 ，t h e ngh a 8a 日0 竹l 砒帆 c y c l e t h e o r e m 2 2 1i fgi 8ac o n n e c t e d 【5 ，3 】一9 r 印危w i t hl g i = n 6 ，t h e nt h e l o n g e s tp a t ho f g i 8a t l e a 8 tn 一2 m o r e o v e r ，n 一2 i sb e s tp 0 8 s i b l e t h e o r e m 2 2 2i fgi sa c o n n e c t e d 【5 ，3 】一9 r 础w i t hi g f = 扎7 ，t h e nt h e l o n g e s tc y c l eo fg i 8a tk a 8 t 【n 2 j m o r e 0 v e r ，h 2 ji sb e s tp o s s i b l e t h e o r e m 2 3 2i fgi sa2 - c o 肋e c t e d 【5 ，3 1 一g r 嘞，t h e ngh a sa 日8 m 讹帆 c y c l e ，o rg 鲁d ，w h e r ed 鲍，3 ，甄，1 ，3 ，恐，4 ，k 1 ，1 ，4 ) ，o rd i so n e0 ft h eg r a p l l s f r o mg r a p h 2 3 1t og r a p h 2 3 1 0 c o r o l l a i y 2 3 3 i fgi 8a2 - c o n n e c t e d 【5 ，3 】一g r 叩 w i t hi g i 8a n d6 ( g ) 3 ， t h e ngh a 8a 日n m l 批mc y c l e i nt h et h i r dc h a p t e r ，w em a i n i yo b t a i nt h er 鹤u l ta sf o l l o w 8 ： t h e o r e m3 5i fgbac o n n e c t e d ，1 0 c a u y2 一c o n n e c t e d 【4 ，2 】一g r 印 ，t h e ng 垒 k l ，l ，l 3o rg i sp a t he x t e n d a b l e i nt h ef o u r t hc h a p t e r ，w em a i n l yg i v es o m ec o r r e 8 p o n d i n gr e s u l t 8o ff u l l yc y c l e e x t e n d e n c e ： t h e o r e m4 3i fgi 8a c o n n e c t e d ，l o c 8 l l yc o n n e c t e d 【5 ，3 】一9 r n p w i c h6 ( g ) 3 ， t h e n g 竺fo r g i 8 f u l l yc y c l ee x t e n d a b l e c o r o l l a r y4 4i fg i sac o n n e c t e d ，l o c 柏l yc o n n e c t e d 【5 ，3 】一夕r 印 w i t h6 ( g ) 3 a n d g i 8 ，t h e n g i 8 f u l l yc y c l ee x t e n d a b l e i nt h el a 8 tc h 印t e r ，w e 西v et h ef o u 讲“n gr e s u l ta b o i l tv e r t e x d i s j o i n tc y c l e si n 【4 ，2 卜g r 印h ： t h e o r e m5 5l e tgb ea 【4 ，2 卜g r a p h ，s u p p o s ei g i = 几3 七十2a n d 盯2 ( g ) 3 后t h e ng c o n t a i l l s 七口e r t e z d i 町斫mc y c l e s ， k e y w o r d s ：k 小g r a p h 8 ；p a t he x t e n s i o n ；f u l l yc y c i e 麟t e i l 8 i o n ；v e r t e x d 埘o i n t 4 山尔师范人学硕十学位论文 c ”l e s ；h a i l t o n c l a s s i f i c a t i o n ：0 1 5 7 5 5 山尔师范人学硕十学位论文 第一章预备知识 1 1 研究背景及已有结果 一、研究背景 图的h a m i l t o n 性足图论研究中的热点问题之一一百多年前，爱尔兰数学家 哈密尔顿提出了这样一个问题：一个连通图有h 锄i l t o n 圈的充分必要条件足什 么? 这就足著名的哈密顿问题该问题一经提出就受到广泛关注，后经研究发现 它足个n p c 问题 对图的路圈性质的研究足以哈密顿问题为起点发展起来的，相关的研究主 要集中在两个方面，一足寻找图具有某些路圈性质的允分条件，二足研究某些特 殊图类的路圈性质后者中的特殊图类主要足指不含某些特定结构的导出子图 的图类，这些特定结构的导出子图又称作禁用子图无爪图就足以k t 3 为禁用子 图的图类由于其深刻的研究背景一一线图都足无爪图，上个世纪的七八十年代 无爪图受到图论界的广泛关注，对无爪图的路圈性质的研究也足在这个时期开 始的 经过几十年的发展，图的路圈性质所涉及的内容r 益丰富和具体比较常见 的路的方面有可迹性，h a m i l t o n 连通，泛连通性，路可扩性等，圈的方面有哈密顿 圈，( 点) 泛圈性，完全圈可扩性等同时从无爪图的禁用子图。3 的结构出发，又 相继定义了一些新的图类，如几乎无爪图，半无爪图，( ，p ；q ) 一图等等一方面 人们尝试把无爪图中的结论推广到更大的图类，另一方面人们也希望得到这些 新的图类在路圈方面的一些新的结果 基于以上研究背景，本文选择了【s ，t 】一图中的路圈性质作为研究的内容，主要 沿着推广已有结论和探索新结果两个思路进行研究 二、已有结果 6 山东师范人学硕+ 学位论文 2 0 0 5 年，刘春房，工江鲁【5 】给出【s ，胡一图的定义及下面的结果： 定理2 1 1 【5 】设g 足【4 ，2 卜图，则 ( 8 ) g 足连通的当且仅当g 同构于硒，3 或者g 有h l 化d n 路 ( b ) g 足2 一连通的当且仅当g 同构于鲍，3 或者g 同构于，l ，3 或g 有日m 砒圈 定理2 1 2 【5 1 设g 足2 一连通【5 ，2 卜图，则g 同构于恐，4 或g 含有h o m 疵路 2 0 0 6 年，蔺厚元，孔淑霞【6 】给出下面结果： 定理2 3 1 1 6 】设g 足3 连通【5 ，3 卜图，则g 有日o m i 髓圈或者g 型面vg 1 9 9 7 年，王江鲁，朱永津等【7 1 在几乎局部连通条件下证明了： 定理3 1 【连通，局部参连通的无爪图足路可扩的其中，局部2 一连通条件是 不能降的 2 0 0 3 年，尤海燕【4 3 】证明了几个关于( k l ，4 ；2 ) 一图在路方面的结果： 定理3 2 p 3 1 设g 为连通的( k - ，4 ；2 ) 一图，i g 7 ，则g 有哈密顿路或有长至少 为2 6 + 2 的路 定理3 3 【4 3 】设g 为连通的( k l 4 ；2 ) 一图，i g i 7 ，6 4 手，则g 有哈密顿路 定理3 4 【4 目连通，局部3 - 连通的( 甄，4 ；2 ) 一图足路可扩的并且指出其中的局 部连通度条件足最好可能的 1 9 9 0 年，h e n d r y 【8 】在无爪图中给出了下面关于完全圈可扩的结论： 定理4 1 l q 顶点数不小于3 的连通，局部连通无爪图足完全圈可扩的 1 9 9 4 年，兄力五沈七 3 8 】将定理4 1 推广到几乎无爪图得到： 定理4 2 删顶点数不小于3 的连通，局部连通的几乎无爪图g 中，如果不含 与k 1 4 同构的导出子图，则g 足完全圈可扩的 1 9 9 7 年，b r a n d te ta 1 9 给出了有关图可以剖分成点不交圈的一个允分条件： 7 山东师范人学硕+ 学位论文 定理5 1 【9 1 设l g l 足阶数不小于4 七并且c r 2 ( g ) 孔的图，则g 可以剖分成k 个点 不交的圈证明定理5 1 需要下面的结论： 定理5 2 f 1 1 】假设i g i 足阶数不小于3 七并且观( g ) 4 七的图，则g 含有七个点不 交的圈 1 9 6 3 年，c o r r 6 d ia i l dh a j n a l 【1 0 】曾给出过下面这个一般结论： 定理5 3 1 1 q假设i g i 足阶数不小于3 七并且6 ( g ) 2 七的图，那么g 含有七个点 不交的圈 h i k 0 8e n o m o t 0 【1 2 】在1 9 9 8 年给出了比定理5 2 更好的结论： 定理5 4 【12 】假浏g i 足阶数不小于3 七并且砚( g ) 24 七一l 的图，则g 含有七个 点不交的圈其中，叻( g ) 4 七一1 足最好可能的 1 2 符号概念介绍 本文仅考虑有限无向简单图，所使用的记号和术语约定如下，其中未加说 明的部分请参照文献 1 】 设g 足一个图，y ( g ) ，e ( g ) 分别表示g 的顶点集和边集对于口，z ，暑，y ( g ) ， s ，t y ( g ) 及g 的子图日，令 ( 口) = u y ( g ) ：删e ( g ) ) ，【 】= ( u ) u 飓( 口) = ( 口) n s ，慨( 丁) = 乩e t 帆( ) 0 ( 何) = r s ( y ( 日) ) ， k ( ? ) = m ，( h ) ( 丁) e ( s ，丁) = 武e ( g ) ：5 s ，? ) 盯2 ( g ) = m 讥 l 扛) i + i ( y ) i ：$ 暑隹e ( g ) ) g 的由s 导出的子图记为g 【s 】1 日 = i y ( 日) i 称为h 的阶 将图g 中与口关联的边的数目叫做顶点”的度，记为d g ( 口) ，即d g ( ) = i ( ”) l ， 8 山尔师范大学硕十学何论文 在不引起混淆的前提下也简记为d ( 口) 用如，g 分别表示g 中顶点的最小度和最 大度，也常简记为6 ， 如果图g 中不存在后一1 个顶点的集合分离g ，则称g 足七一连通的，图g 的连通 度k ( g ) = m a x 七：g 足后一连通的) 。设t ，矿( g ) ，如果( 口) 的导出子图g 【( 口) 】足七一连 通的，则称 足g 的一个局部七一连通点如果图g 的每一个顶点都足局部七一连通 的，则称g 足局部后一连通的 设p = z l z 2 乱为图g 的一条路，即y ( p ) ( 1 i j 墨) ，用z f 和z ，分 别表示p 上的点戤一l 和z 件l ，z 乒1 和z f l 也分别记为z ，z f ；用觑p 巧和7 。0 j ) 分 别表示p 的子路z t + l 巧和巧巧一l 戤 设g = 饥也珥口1 足图g 中的圈，饥，y ( g ) ( 1 l j r ) ，用町2 和时。 分别表示c 上的点地一f 和仇“，町1 和时1 也分别记为町和讨；用和优醌分别表 示g 上的路让吨+ l 和u 地一l ( 这晕点的下标均模r ) 以g 的顶点u ，口为两端点的路叫做g 的( 乱，”) 一路设p 足g 的一条( 钍，钉) 一路，如 果g 中不存在( 缸，口) 一路p ，使得y ( ，) cy ( p ) 且i p 7 i i p i ，则称p 为g 的一条极 短( u ，u ) 一路显然，连通图中任意两点之臼j 都有极短路以顶点“， 为两端点的最 短路的路长，叫做u ，口之间的距离，记作d ( 乱，”) 经过g 中每个顶点恰好一次的路( 圈) 称为( g 的) h a m i l t o n 路( 圈) 若g 中存在 一个h 啪i l t o n 圈，则称g 足哈密顿的 如果讹，口y ( g ) ，图g 都有( 钍，盯) 一h 锄i l t o n 路，则称g 是h 栅i l t o n 连通的若v t y ( g ) ，图g 都有长为z ( d ( 让，口) 2 i y ( g ) i _ 1 ) 的( 口) 一路，则称g 足泛连通的 如果图g 满足：对地，口y ( g ) 及g 的任意一条( 札，钉) 一路p ，只要f y ( p ) l i y ( g ) f ， 就存在g 的( “，口) 一路p ，使得y ( p ) cy ( p ) 且i y ( p ，) i = l y ( p ) l + 1 ，则称g 足路可 扩的满足条件的p ，叫做p 的扩路 令i y ( g ) i = n ，若对任意的f ( 3 z n ) ，g 中都有长为z 的圈，则称图g 足泛圈 9 山东师范大学硕十学位论文 的若对任意的z ( 3 fs 礼) ，g 中过任意点都有长为f 的圈，则称图g 足点泛圈的 如果图翻谚足：( 1 ) g 的每个顶点都在长度为3 的圈上；( 2 ) 对g 中任意一个圈c ， 只要i y ( c ) f i y ( g ) l ，就存在g 的圈g 7 ，使得y ( g ) cy ( ) 且i y ( ) i = i y ( g ) i + 1 ， 则称g 足完全圈可扩的 设f 为一个图，如果图g 不含同构于f 的导出子图，则称g 为p ，r e e 的 如果图g 中任意s 个点的导出子图中至少含有条边，则称图g 为【8 ，胡一图 由【s ，t 】一图的定义容易知道，b 卜图有下述性质： 性质lk 小图足【s ，一l 卜图 性质2 【s ，小图剐s + l ，司一图 性质3f s ，小图足【8 + 1 ，+ 1 卜图 性质4 设g 足f s ，| _ 图，对g 任意子图日，如果i l s ，则日足【s ，牛图， 1 0 山东师范犬学硕十学位论文 第二章【s 司图的路和圈 这一章主要研究连通及2 连通条件下【5 ，3 】一图的路和圈第一节介绍了【5 ，3 卜 图的概念及有关结论，后两节给出了本章的主要定理及其证明 2 1【5 ，3 卜图及七- 连通【8 ，司图的日o m 砒o m 路( 圈) 刘春房最早在2 0 0 5 年提出【s ，小图的概念【目：如果g 中任意s 个点的导出子图中 至少含有条边，则称图g 为【s ，小图【5 ，3 】- 图即指g 中任意5 个点的导出子图中至 少含有3 条边，它足 4 ，2 卜图的推广 引理2 1 3 f 5 j 设p = 口1 啦足连通图g 的最长路，日足g p 的一个分支， 饥 r p ( 圩) ，则 ( a ) ( 仇) u ( ) y ( p ) ； ( b ) 谚，町隹- ( 日) ；饥，口1 时，吻町譬e ( g ) ； ( c ) 若又有码p ( h ) “ j ) ，则町哼，时哆，口哼，时隹e ( g ) 根据引理2 1 3 及易得定理2 1 3 和定理2 1 4 定理2 1 3 设g 足七一连通的【七+ 2 ，1 】- 图，则g 含日o m f m 路并且后+ 2 足最好 可能的，如果把七十2 升到七+ 3 ，则1 可以增加到2 ，3 ，4 甚至更大其中尬4 可以说 明 证明假设g 足髓连通的【七+ 2 ，1 卜图，但g 不含h 册l i 此路令l g i = n ，取g 的 最长路p = 饥吨，则p n 一1 设日足g p 的一个分支，则由g 足肛连通的易 知i p ( 日) i ，不妨取z l ，z 2 ，z k p ( h ) 由引理2 1 3 易知i e ( g p l ，z ，z 1 ，z 2 ， ，z k 】) l = o ，矛盾于g 足陋+ 2 ，1 卜图 定理2 ，1 3 证毕 山尔师范人学硕 学位论文 定理2 1 4 设g 足七一连通的陋+ 1 ，1 卜图，则g 含日o m t z o 棚圈并且七+ 2 是最好 可能的，如果把七+ 1 升到七十2 ，则1 可以增加到2 ，3 ，4 甚至更大其中蜗3 可以说 明 证明假设g 足一连通的雎+ 1 ，1 卜图，但g 不含日o m m 觎圈令i g i = n ，取g 的 最长圈e = 1 也q ”l ，则z 礼一1 设日足g e 的一个分支，则由g 足七一连通的 易知i ( 日) i2 七，不妨取z 1 ，z 2 ，z 女a ( 日) 由引理2 1 3 易知i e ( g k ，z l ，z 2 ， 一，z k 】) i = o ，矛盾于g 足陋+ 1 ，1 图 定理2 1 4 证毕 2 2连通【5 ，3 卜图的最长路( 圈) 本节选取 5 ，3 】一图作为研究的对象，得到： 定理2 2 1 设g 足n ( n 6 ) 阶连通1 5 ，3 】一图，则g 中最长路的长度不小于n 一2 且路长的界足紧的 定理2 2 2 设g 足n 7 ) 阶连通【5 ，3 】一图，则g 中最长圈的长度不小于【几2 j 此界足最好可能的 图2 2 1 和图2 2 2 中的图说明定理2 ，2 1 中路长的界足紧的 图2 2 1图2 2 2 1 2 山尔师范人学硕士学位论文 ( 一) 定理2 2 1 的证明 假设g 是n ( n 6 ) 阶连通【5 ，3 】一图，p = t ，1 t ，2 坳足g 的最长路下面假设p 佗一2 引理设日足g 尸的一个分支，则l p ( 日) i = 1 证明否则，设仇，p ( h ) 且i j 取仳y ( 日) ，且钍仇e ( g ) 下面分2 种情形来说明 情形1 i u l p i = 2 且i 仇p 吩i = 3 且i 吩p i = 2 时 因为p n 一2 ，所以i y ( g ) y ( p ) i 2 ，从而存在u y ( g ) y ( p ) ，且“ 若e ( g ) ，则得长于p 的路：讹地p ，矛盾于p 足最长路 所以，w 隹f ( g ) 考虑g h 仃，饥，订，】，由引理2 i 3 易知口l ，伽i ，“时，u ，w 1 ， 饥_ ， 1 ，时口1 隹e ( g ) ，矛盾于g 足【5 ，3 卜图 情形2 l 口1 p 巩l 3 或l 地p 吩i 4 或i p f 3 时 1 0 当h p 啦i 3 时，考虑g 阻，u ，町，可，叫，则由引理2 1 3 易知l ，“，删f ， 咋可，口1 ，町坳， 1 哼，町丐e ( g ) ，矛盾于g 足f 5 ，3 卜图 2 0 当i 饥p q i 4 时，考虑g 阻， l ，时，丐，坳】，由引理2 1 3 易知“ 1 ，牡铷，让对，咋丐， u 砂，u 1 ，口町，讨坳隹e ( g ) ，矛盾于g 足1 5 ，3 卜图 3 0 当i p 脚i 3 时，考虑g 阻， 1 ，时，哆，嘲，由引理2 1 3 易知删l ，缸吻，“谚，坳哆 ”时，”哼，讨哆，可- 譬e ( g ) ，矛盾于g 足【5 ，3 卜图 以上矛盾说明引理成立 下面完成定理2 2 1 的证明 因为g p 至少有一个分支，不妨设为研，结合引理设p ( 凰) = 饥 分5 种情形来说明 1 3 山东师范大学硕十学位论文 情形1 i 口1 p 仇i = i 仉f | _ 2 时 1 0 若g p 有1 个分支，即片l ，则易知i 王h i _ l ，| g i = 4 ，矛盾 2 0 若g p 有2 个分支，不妨设另一分支为啦，则结合引理2 1 3 及引理易 知 r p ( 日2 ) = 地) 易知1 日1 j = l j 如净1 ( 否则易得长于p 的路) 从而l g l = 5 ，矛盾 3 0 若g p 有不少于3 个的分支，不妨设凰，凰，凰足g p 的3 个不同分支， 取y ( 日1 ) ，口y ( 凰) ，u y ( 凰) ，则结合引理2 1 3 及引理知p ( 马) = 地 ，j = 1 ，2 ，3 考虑g 【u ，口，u ，口1 ，叫，易知钍 ，讹，删l ，仳坳，讥，伽l ，伽i ，u 们，“铷，移l 铷垡e ( g ) 矛盾于g 是【5 ，3 】一图 情形2l 1 尸珥i = 2 且i p i = 3 时 1 0 若g p 有1 个分支，不妨设为何，则易知1 日i = 1 否则，易得长于p 的路从 而p n 一1 ，矛盾 2 0 若g p 有不少于2 个的分支，不妨设研，j 屯足g p 的2 个不同分支，易 知l h ，l = i 凰l - l ( 否则，易得长于_ p 的路) 不妨设y ( 皿) = “) ，y ( f 如) = ”) ， 考虑g m ，口，时，移1 ，叫，由引理2 1 3 知伽，“口l ，“，口口l ，伽b ，u 产，t ，l 咋隹e ( g ) ，又因 为g 足【5 ，3 卜图，所以u 1 时e ( g ) ，从而得长于p 的路：蜥w l 也乱，矛盾 情形3l 口1 p 嘶l = i 饥尸i = 3 时 1 0 若g p 有1 个分支，即凰，则易知i 皿i = 1 否则设“，移y ( 日1 ) 且u e ( g ) 考虑g m ，”，时，町，嘲，町时簪e ( g ) ，否则得长于p 的路： h m ) 锄：吱p p 又，珏时，砒j p ，乱町，口町，口时，钉，町隹e ( g ) ( 由引理2 1 3 易知) 矛盾于g 足 5 ，3 】 一图 2 0 若g p 有不少于2 个的分支，不妨设玩，飓足g p 的2 个不同分支，设 y ( h 1 ) ， 1 ，( 兄) ，且“仇e ( g ) 考虑g 阻， ， 1 ，时，硝，易知“口，”吻，伽 ，缸秽l ，口1 1 4 山东师范大学硕十学位论文 讨”l ，口t ，l ，m i p 聋e ( g ) ，矛盾于g 足i 5 ，3 】一图 情形4i 口l p 地f = 2 ，j 饥p i 4 时 1 0 若g p 有1 个分支，即日l ，则易知i 吼i = 1 否则，易得长于j p 的路，矛盾 所以p 竹一1 ，矛盾 2 0若g p 青不少于2 个的分支时，不妨设日1 ，凰足g p 的2 个不同分支， 取y ( 日1 ) ，地 r p ( 皿) ，t ，y ( 飓) ，p ( ) = 锄) ，考虑g 【“， ，口1 ，时，】，由引 理2 1 3 易知“口，b ，删1 ，“时，删l ， l 时， 1 ， 簪e ( g ) ，矛盾于g 足【5 ，3 卜图 情形5i u l p 吨i 3 且l 地p l24 时 1 0 若g p 有1 个分支，即研，设“y ( 日1 ) 且u 讧e ( g ) 考虑g 【u ，秽1 ，町，时， 铷】，由定理2 1 3 知删l ，似- ，t 町，埘，1 ，t f 铷，钞1 时隹e ( g ) ，又，g 足 5 ，3 卜图，所以 町时e ( g ) 设足町在仉p 上最后一个邻点，则结合引理2 1 3 ( b ) 知，叼咋 o ) 若吩= 啄，则l h l i = 1 否则，易得长于p 的路从而p n 一1 ，矛盾 6 ) 若啄，考虑g 沁，口l ，町，哆，】，由引理2 1 3 知删1 ，“，u 町，t ，1 ，町隹 e ( g ) ；由引理知钍哆隹e ( g ) ；由假设知町哆隹e ( g ) 若 1 哆e ( g ) 则得长 于尸的路： 伽t p l ，j ip 饥1 ) jp p 所以，f e ( g 阻，口，町，秽 ，】) l 2 ，矛盾于g 足【5 ，3 卜图 2 0 若g p 有不少于2 个的分支，不妨设上屯足不同于日1 的另一个分支设 y ( 日1 ) ，u y ( f 如) ，m k e ( g ) 考虑g 阻，口，口l ，时，吻】，由引理2 1 3 知u 口， l ，u ，“时， l ，u 邯， 1 坳，町咋隹f ( g ) ，矛盾于g 足【5 ，3 卜图 至此定理2 2 1 的证明结束 ( 二) 定理2 2 2 的证明 图2 2 3 中的图( m 4 ) 说明定理2 2 2 中圈长的界足最好的 1 5 山东师范大学硕十学位论文 o 图2 2 3 假设g 足n 7 ) 阶连通【5 ，3 】一图，但g 中最长圈的长度小于i n 2 j 取图g 中的 一条最长路p = ”1 吨，由定理2 2 1 知p n 一1 ，即p = 几一1 或者p = 礼 设 譬y ( p ) ，并设t 0 足 l 在尸上的最远邻点，饥足在p 上的最远邻点，则i ，j 陷2 1 下面分两种情形完成定理2 2 2 的证明 情形1 产n 一1 情形1 ，1 当= 忱且地= 一l 时 考虑g h 1 ，口3 ，咋_ 2 i 叫，由引理2 1 3 知t ，口l ， 1 ， 口l 隹e ( g ) ；由定理2 2 1 知l ( u ， 一2 ) n e ( g ) i 1 ；由刚才的假设知”l 均，u 1 一2 ，地铷，一2 隹e ( g ) 得矛盾 情形1 2 当忱，或者地吻一1 时 不妨设砌考虑g p ，口l ，啦，一2 ，+ 1 】，由引理2 1 3 知m ，1 ，口1 ，仉_ 隹e ( g ) ； 由刚爿的假设知l 吩+ 1 茌e ( g ) 又，+ 1 隹e ( g ) ( 否则圈q = l 尸u l 和圈c ；= + l p + l 中至少有一个的长度h 2 j ) ：一l 唧甓e ( g ) ( 否则得圈 l p 一1 a w l t ，1 ) ； 一1 岳e ( g ) ( 否则得h a l i l i l t o n 路”一1 7 习1 p ) 结合图g 足【5 ，3 】一图知饥0 + 1 口1 t 。一1 ，一1 + l e ( g ) 考虑g p ，”1 ，一1 ，码+ 2 ，嘲，由引理2 1 3 知f l ， 1 坳， 咋譬e ( g ) ；由刚才的假设 及论证知”一1 ，t ，+ 2 ，口1 + 2 ，一l 隹e ( g ) 又，一1 t 。+ 2 隹e ( g ) ( 否则得h a m i l t o n 路 饥0 + 1 t 。口l p 吩一l 码+ 2 p 矛盾于g 足【5 ，3 卜图 1 6 山尔师范人学硕十学位论文 情形2p = n 结合假设易知i 地p l 2 考虑g p l ，吩一1 ，+ l ，一2 ，叫，结合刚才的论证易 知 l 吩+ i ，地地一1 ，口1 ，一1 吻，