（运筹学与控制论专业论文）连通图中可去边和圈的研究.pdf

原创性声明 8 1 1 1illl 11i lt l lil l ll l l l l l ll tl l l l l l 17 9 4 3 9 2 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：匿垄璺日期：丝! 旦! ! 丛 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：廑堑垄导师签期：趔! ：r 目录 摘要i 英文摘要v 符号说明x 第一章绪论1 1 1 基本概念和术语1 1 2 连通图的构造3 1 3 连通图中的可收缩边4 1 4 连通图中的可去边9 1 5 图的棱哈密顿性1 3 第二章不含三角形的k 连通图中可收缩边的性质1 7 2 1 预备知识1 7 2 2 定理2 1 3 的证明1 8 2 3 结束语2 2 第三章3 连通图中的可去边2 3 3 1 预备知识2 3 3 2 一个有用的引理2 5 3 33 连通图最长圈上的可去边3 0 3 43 连通图支撑树上或支撑树外的可去边3 4 3 53 连通图的可去边和最长圈上的弦3 7 第四章5 连通图上的可去边 4 1 基本定义和符号 4 2 预备知识和一些已知结果 4 35 连通图圈上的可去边 4 45 连通图支撑树上的可去边 第五章图的棱可圈性的度和条件 5 1 预备知识 5 2 定理5 1 2 的证明 5 3 定理5 1 4 的证明6 8 参考文献7 3 致谢8 1 作者简介8 2 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 连通图中可去边和圈的研究 康海燕 ( 山东大学数学学院，济南2 5 0 1 0 0 ) ( 法国巴黎南大学( 巴黎1 1 大) 信息科学实验室，9 1 4 0 5 ) ( 指导教师：李国君 教授 e v e l y n ef l a n d r i n 教授) 摘要 图论是离散数学中一个重要研究领域它在计算机科学，化学，社会科学 和生物学等方面都有很广泛的应用 连通图的构造是图论中一个非常重要的研究课题它与网络模型和组合优 化联系密切，使它具有重要的理论价值和应用价值自1 9 6 1 年，t u t t e 利用3 连通图中可收缩边的存在性给出了3 连通图的构造方法之后，人们致力于研究 各种类型连通图的构造可收缩边和可去边这两个概念不仅在连通图的构造上 发挥重要作用，而且还是递归证明图的某些性质的重要工具本文第二章至第 四章主要研究连通图中可收缩边和可去边的性质以及他们在特定子图上的分布 情况 第二章主要研究了不含三角形的k 连通图中收缩边的一个性质设g 是k 连通图，e = u v 是图g 中的一条边用g e 表示从图g 中删除顶点让，t ，并 添加新的顶点使得与u ，v 所有的邻点相邻所得到的图如果c e 仍然是 k 连通图，那么e = u 秒称为图g 的k 可收缩边不存在k 可收缩边的非完全 k 连通图称为收缩临界k 连通图对于k = 3 ，t u t t e 8 3 1 证明了阶大于4 的3 连 通图存在3 可收缩边，所以不存在阶大于4 的收缩临界3 连通图对于k = 4 ， m a r t i n o v 和f o n t e t 分别证明了收缩临界4 连通图g 是4 正则的，且每条边恰 在一个三角形上，即g 或者是锈或者是7 2 - 边连通立方体的线图【3 2 5 9 这 里7 2 一边连通立方体可由尬或4 中去掉1 因子的图通过构造的方法得到 当k 5 时，收缩临界k 连通图的结构比k = 3 和k = 4 的情况复杂得多所 以对于k 5 的情形，人们一般考虑收缩临界k 连通图的局部结构1 9 8 2 年， t h o m a s s e n 8 1 1 证明了收缩临界k 连通图含有三角形，即如果k 连通图g 不含 三角形，那么g 中存在一条边e = 让秽使得任何k 点割都不同时包含顶点让和 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 口最近，f u j i t a 等【3 7 】证明了如果k 连通图g 的最小度至少是【3 k 2 j + 2 ，那 么g 有一条k 可收缩边e = 札t ，使得g 一 乱，u 仍然是k 连通的结合以上两 个结果，我们证明以下结论，同时给出图例说明最小度条件是必须的 结论1 设g 是不合三角形的k 连通图， k22 ，如果6 ( g ) k + 1 ，那么g 中 有一条边e 使得g y ( e ) 仍是k 连通的 对于k 连通图中的可去边，h o l t o n 等 3 9 】首先给出了3 连通图中可去边 的定义后来尹建华在1 9 9 9 年定义了4 连通图可去边的概念f 9 3 】最近厦门大 学徐丽琼在她的博士毕业论文【9 1 】中把3 连通图和4 连通图的可去边的概念推 广到k 连通图设e 是k 连通图g 的一条边，gee 表示图g 做下列运算所 得的图：( 1 ) 从g 中去掉e 得图g e ；( 2 ) 如果e 的某个端点在g e 中度数 为k 一1 ，则去掉此端点，再两两连接此端点在g e 中的k 一1 个邻点；( 3 ) 如 果经过( 2 ) 中的运算后，有重边出现，则用单边代替它们，使得此图为简单图 如果gee 仍为k 连通图，则称e 为g 的可去边g 的所有可去边的集合记 为协( g ) 早在1 9 6 9 年，类似于3 连通图中的可收缩边的结果，b a r n e t t e 等 【1 2 】证明了每个阶大于4 的3 连通图必有可去边，并且给出了3 连通图的一个 递归构造方法这是关于可去边的最早成果尹建华 9 3 】证明了4 连通图g 不 存在可去边的充要条件是g 是c 詈或锘，并利用这个结果和4 可收缩边的性质 给出4 连通图的一个递归构造方法，他的方法比s l a t e r 7 1 】的构造方法简单很 多徐丽琼等【9 1 9 2 】给出了k 连通图中可去边的定义后，证明了不同构于玩 的5 连通图中必有可去边另外对不含可去边的k 连通图作了如下猜想：对于 k ( k 3 ) 连通图g ，g 中不存在可去边当且仅当k 为奇数时，g 笺k k + 1 ；当k 为偶数时，g 竺k k + l 或h ( k + 2 ) 2 ，后来这个猜想被苏健基等证实 7 6 】至此k 连 通图中的可去边的存在性问题得到圆满解决同时可去边在特殊子图结构上的 分布问题也被广泛研究，本文关于可去边的结果就集中于此 第三章主要研究了3 连通图中可去边的分布苏健基 7 2 】证明了3 连通图 的哈密顿圈上的可去边数依赖于图中极大半轮的个数我们把这个结果推广到 3 连通图的最长圈上吴吉昌等【4 3 】【8 8 】证明3 连通3 正则图的支撑树上或者 支撑树外至少有2 条可去边我们把这个结果推广到不含极大半轮的3 连通图 中同时我们利用3 连通图可去边的性质证明了t h o m a s s e n 在1 9 7 6 年提出的 猜想( 3 连通图的最长圈上有弦) 对两类图是成立的，并给出图例说明这个结论 没有被之前的结果覆盖该章的结果列举如下： 结论2 设g 是阶大于5 的3 连通图并且g 不是轮， c 是g 的最长圈，则 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 以) 如果c 不通过任何极大半轮，那么c 上至少有了条可去边； 偿) 如果c 仅通过一个极大半轮，那么c 上至少有2 条可去边； p ) 如果c 仅通过两个极大半轮，那么c 上至少有j 条可去边 结论3 设g 是没有极大半轮的3 连通图，那么g 的支撑树上或支撑树外至少 有2 条可去边 结论4 设g 是3 连通图且i g i 6 ，c 是图g 上的最长圈，如果l e ( c ) n ( g ) l 5 ，则c 上有弦 结论5 设g 是3 连通图且i g l 9 ，c 是图g 的最长圈，如果i ( e ( g ) 一e ( c ) ) n e r ( g ) l 7 而且g 中任意的原子都跟c 有交点，则c 上有弦 第四章主要研究了5 连通图中可去边的分布徐丽琼在给出5 连通图的可 去边的定义后讨论了它的分布情况，并证明了 9 1 】对于5 连通图g ，如果最小 度至少是6 或围长至少是4 或g 中不含原子，那么g 中任意的圈c 至少有两 条可去边；如果最小度至少是6 或围长至少是4 ，那么g 中任意的支撑树丁上 至少有两条可去边我们推广了上述结果 结论6 设g 是阶大于7 的5 连通图，那么g 上任意的三角形上有j 条可去 边 结论7 设g 是阶大于9 的5 连通图，c 是g 的一个圈，那么 以j 如果c 与任何原子都是点不交的，则c 上有2 条可去边； 俚，) 如果c 仅与一个原子有交点，则c 上有j 条可去边； 俐如果g 中不合原子且c 是哈密顿圈，则c 至少有3 条可去边； “j 如果g 中每对相邻的点对z ，y 都有d ( x ) + d ( y ) 1 1 成立，则c 上有2 条 可去边 结论8 设g 是阶大于9 的5 连通图，丁是g 的支撑树，如果g 不含原子， 则t 上有2 条可去边 论文的最后一部分是关于图的棱可圈性图g 的棱是指g 与完全图的 笛卡尔积，记作g 口恐如果g k 2 是哈密顿的，那么称图g 是棱哈密顿的 对于图g 的非空顶点子集s ，若g 中存在一个圈经过s 的所有顶点，那么称s 是可圈的；若g 口中存在一个圈经过s 以及它的拷贝中所有的顶点，那 么称s 是棱可圈的图的哈密顿圈问题是图论中的一个经典问题自1 8 5 7 年 h a m i l t o n 正式引入这个概念以来已有大量的定理、猜想、综述最近一个研究 趋势是寻找哈密顿圈的变形来衡量图距离哈密顿性。有多近”，图的棱哈密顿性 就是其中之一最近，o z e k i 【6 5 】首次研究了图具有棱哈密顿性的度和条件，证 i n 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 明了对阶n 2 的连通图g ，如果a 3 ( c ) 礼，那么g 是棱哈密顿的同时他们 给出实例说明所得的界是最好的我们把这个结果推广到特定子集上，另外我 们还讨论了无爪图的情形 结论9 设g 是连通图且它的阶死22 ，d s y ( g ) ，s 是1 g 连通的如果 a 3 ( s ) n ，那么s 在g 口恐中是棱可圈的 结论1 0 设图g 的阶礼2 ，s 为g 的顶点子集，且s 0 ，同时满足如下条 件： ( z ) s 是1 g 连通的， ( i i ) sun ( s ) 中所有的顶点都不是爪的中心， ( i i i ) ( s ) 佗一3 倜g 中考虑， 那么s 在g e k 2 中是棱可圈的或者s 是( a ，b ，c ) 一结构子图 关键词：连通图；可收缩边；可去边；最长圈；支撑树；棱；可圈性 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 r e m o v a b l e e d g e s ，c y c l e sa n dc o n n e c t i v i t yi n g r a p h s h a i y a nk a n g ( s c h o o lo fm a t h e m a t i c s ，s h a n d o n gu n i v e r s i t y , j i n a n2 5 0 1 0 0 ) ( l r i ，p a r i s - s u du n i v e r s i t y ( p a r i s11 ) ，o r s a y , 9 1 4 0 5 ，f r a n c e ) e n g l i s ha b s t r a c t g r a p ht h e o r yi sav e r yi m p o r t a n tr e s e a r c hf i e l do fd i s c r e t em a t h e m a t i c s i t i sw i d e l ya p p l i e di nv a r i o u sd i s c i p l i n e s ，s u c ha sc o m p u t e rs c i e n c e ，c h e m i s t r y , s o c i a l s c i e n c ea n db i o l o g ye t c s i n c et u t t eg a v eac o n s t r u c t i o no f3 - c o n n e c t e dg r a p h si n 1 9 6 1 ，r e s e a r c ho n s t r u c t u r a lc h a r a c t e r i z a t i o n so fg r a p h sb e c o m e sav e r yp o p u l a r t o p i ci ng r a p ht h e o r y i tp l a y sa ni m p o r t a n tr o l ei nb o t ht h e o r e t i c a lr e s p e c ta n d p r a c t i c a la p p l i c a t i o n sd u e t oi t sc l o s ec o n n e c t i o nt on e t w o r km o d e l i n ga n dc o m b i n a t o r i a lo p t i m i z a t i o n t h e c o n c e p t so fc o n t r a c t i b l ee d g e sa n dr e m o v a b l ee d g e so fg r a p h sa r ep o w e r f u lt o o l st o s t u d yt h es t r u c t u r eo fg r a p h sa n dt op r o v ep r o p e r t i e so fg r a p h sb yi n d u c t i o n p r o m c h a p t e r2t oc h a p t e r4 ，w ef o c u so nt h et h ee x i s t e n c eo fc o n t r a c t i b l ee d g e sa n d t h ed i s t r i b u t i o no fr e m o v a b l ee d g e si nc e r t a i ns u b s t r u c t u r e so fc o n n e c t e dg r a p h s i nc h a p t e r2 ，w ef o c u so i lt h ep r o p e r t yo fc o n t r a c t i b l ee d g e si nk - c o n n e c t e d g r a p h sw i t h o u tt r i a n g l e s l e tgb eak - c o n n e c t e dg r a p ha n de = 让z ，a ne d g eo f g b ya ew ed e n o t et h eg r a p ho b t a i n e df r o mgb yd e l e t i n gt h ev e r t i c e su va n d a d d i n ga n e wv e r t e xv es u c ht h a t i sa d j a c e n tt oa l lt h ef o r m e r n e i g h b o r so f 钍a n d 移i fa ei ss t i l lk c o n n e c t e d ，t h e nei sc a l l e dak c o n t r a c t i b l ee d g e an o n c o m p l e t e k - c o n n e c t e dg r a p hgi sc a l l e da nc o n t r a c t i o nc r i t i c a l l yk - c o n n e c t e dg r a p hi fgh a s n ok - c o n t r a c t i b l ee d g e s f o rk = 3 ，t u t t e 8 3 p r o v e dt h a te v e r y3 - c o n n e c t e dg r a p h w i t ho r d e ra tl e a s t5h a sa3 - c o n t r a c t i b l ee d g e f o rk = 4 ， m a r t i n o va n df o n t e t p r o v e dt h a ta n yc o n t r a c t i o nc r i t i c a l l y4 - c o n n e c t e dg r a p hi se i t h e r 碟o rt h el i n e v 山东大学，法国巴黎南大学( 巴黎l l 大) 博士学位论文 g r a p ho fac u b i c ( 7 2 ) 一c o n n e c t e dg r a p h 3 2 5 9 h e r e ，t h ec u b i c ( 7 2 ) 一c o n n e c t e d g r a p h sc a nb eo b t a i n e d i nac o n s t r u c t i v ew a yf r o mk 4o rt h ec u b e 蜀，4 一( 1 一f a c t o r ) f o rt h ec a s ek 5 ，i th a sb e e np r o v e dt h a tt h ec l a s so fc o n t r a c t i o nc r i t i c a l l y5 - c o n n e c t e dg r a p h si sr i c h s os u b s t r u c t u r ep r o p e r t i e so fc o n t r a c t i o nc r i t i c a l l y 缸 c o n n e c t e dg r a p h sh a v eb e e ni n v e s t i g a t e d i n1 9 8 2 ，t h o m a s s e n 8 1 】g o tt h a te v e r y c o n t r a c t i o nc r i t i c a l l yk - c o n n e c t e dg r a p hc o n t a i n sa t r i a n g l e ，t h a ti st os a y , i fa k - c o n n e c t e dg r a p hgh a sn ot r i a n g l e s t h e ngh a sa ne d g ee = u us u c ht h a tn o 舡 v e r t e x - c u t sc o n t a i nb o t hua n du r e c e n t l y ，f u j i t ae t c 3 7 】p r e s e n t e dar e s u l tw h i c h s t a t e dt h a t ，i ft h em i n i m u md e g r e eo fk - c o n n e c t e dg r a p hgi sa tl e a s t 【3 k 2 j + 2 ， t h e ngh a sac o n t r a c t i b l ee d g ee = 扎秽s u c ht h a tg 一 孔，秽 i ss t i l lk - c o n n e c t e d c o m b i n i n gt h ea b o v et w or e s u l t s ，w ep r o v et h ef o l l o w i n gc o n c l u s i o n ，m e a n w h i l e ， w eg i v ee x a m p l e st os h o wt h em i n i m u md e g r e ec o n d i t i o ni sn e c e s s a r y c o n c l u s i o n1l e tgb eak ( k 2 ) 一c o n n e c t e dt r i a n g l e - f r e eg r a p hw i t h6 ( g ) k + 1 t h e ngh a sa ne d g ees u c ht h a tg y ( e ) i ss t i l l 七一c o n n e c t e d f o rr e m o v a b l ee d g e so fk - c o n n e c t e dg r a p h s ，i n1 9 9 0 ，h o l t o ne t c 3 9 f i r s t d e f i n e dr e m o v a b l ee d g e si na3 - c o n n e c t e dg r a p h l a t e r ，y i n 9 3 ld e f i n e dr e m o v a b l e e d g e si na4 - c o n n e c t e dg r a p h r e c e n t l y , x u 9 1 】g e n e r a l i z e dt h ec o n c e p to fr e m o v o a b l ee d g e si na3 - c o n n e c t e dg r a p ha n da4 - c o n n e c t e dg r a p ht ok - c o n n e c t e dg r a p h s l e tgb eak - c o n n e c t e dg r a p h ，a n dl e teb ea ne d g eo fg l e tgeed e n o t et h e g r a p ho b t a i n e df r o mgb yt h ef o l l o w i n go p e r a t i o n ：( 1 ) d e l e t eef r o mgt og e tg - e ； ( 2 ) f o ra n ye n dv e r t e xo few i t hd e g r e ek 一1 ，s a yz ，d e l e t ez ，a n dt h e na d de d g e s b e t w e e na n yp a i ro fn o n - a d j a c e n tv e r t i c e si nn c e ( z ) i fgo ei sk - c o n n e c t e d ，t h e n ei ss a i dt ob ear e m o v a b l ee d g eo fg t h es e to fa l lr e m o v a b l ee d g e si sd e n o t e d b y 昧( g ) e a r l yi n1 9 6 6 ，b a r n e t t ee t c 1 2 】p r o v e dt h a ta 3 - c o n n e c t e dg r a p ho f o r d e ra tl e a s tf i v eh a sar e m o v a b l ee d g ea n dg a v eac o n s t r u c t i o no f3 - c o n n e c t e d g r a p h s t h i si st h ee a r l i e s tr e s u l ta b o u tt h er e m o v a b l ee d g e s i n 【9 3 ，y i np r o v e d t h a tt h e4 - c o n n e c t e dg r a p hw i t h o u tr e m o v a b l ee d g e si se i t h e r 锘o r 锘b a s e d o nt h i sr e s u l t ，h ep r o v i d e dac o n s t r u c t i v ec h a r a c t e r i z a t i o no f4 - c o n n e c t e dg r a p h s ， w h i c hi sm u c hs i m p l e rt h a ns l a t e r sm e t h o d 【7 1 】a f t e rd e f i n i n gr e m o v a b l ee d g e si n k - c o n n e c t e dg r a p h s ，x ue t c 9 1 9 2 】p r o v e dt h a tt h e5 - c o n n e c t e dg r a p hw i t h o u tr e - m o v a b l ee d g e si sk 6 m e a n w h i l e ，t h e yc o n j e c t u r e dt h a t ，f o rak ( k 3 ) 一c o n n e c t e d g r a p hg ，gh a sn or e m o v a b l ee d g ei fa n do n l yi fe i t h e rg 笺g k + 1f o rkb e i n g v l 山东大学，法国巴黎南大学( 巴黎1 l 大) 博士学位论文 o d d ，o rgi si s o m o r p h i ct oe i t h e rg k + 1o rh ( k + 2 ) 2f o rkb e i n ge v e n r e c e n t l y , t h e c o n j e c t u r ew a sv e r i f i e dt ob et r u eb ys ue t c 【7 6 】s ot h ep r o b l e mo ft h ee x i s t e n c e o fr e m o v a b l ee d g e si sr e s o l v e d o nt h eo t h e rh a n d ，t h ed i s t r i b u t i o no fr e m o v a b l e e d g e si nc e r t a i ns u b s t r u c t u r eo fc o n n e c t e dg r a p ha l s oa t t r a c t sm u c h a t t e n t i o n i nc h a p t e r3 ，w ei n v e s t i g a t et h ed i s t r i b u t i o no fr e m o v a b l ee d g e si n3 - c o n n e c t e d g r a p h s s u 【7 2 】p r o v e dt h a tt h ed i s t r i b u t i o no fr e m o v a b l ee d g e s o nah a m i l t o nc y - d eo f3 - c o n n e c t e dg r a p h sd e p e n d so nt h en u m b e ro fm a x i m a ls e m i w h e e l s w e g e n e r a l i z et h er e s u l t t ol o n g e s tc y c l e si n3 - c o n n e c t e dg r a p h s w ue t c 4 3 】( 8 8 】 p r o v i d e dt h er e s u l t sw h i c hs t a t e dt h a t ，t h e r ea r ea tl e a s tt w or e m o v a b l ee d g e si n o ro f fa n ys p a n n i n gt r e eo fa3 - c o n n e c t e d3 - r e g u l a rg r a p h w ea l s oi m p r o v et h e r e s u l t s u s i n gt h ep r o p e r t i e so fr e m o v a b l ee d g e si n3 - c o n n e c t e dg r a p h s ，w ep r o v e t h a tt h o m a s s e n sc o n j e c t u r e ( e v e r yl o n g e s tc y c l ei na3 - c o n n e c t e dg r a p hh a sa c h o r d ) i st r u ef o rt w oc l a s s e so f3 - c o n n e c t e dg r a p h s ，i na d i t i o n ，w eg i v ee x a m p l e s t os h o wt h a tt h e s ec l a s s e sa r en o tc o v e r e db yp r e v i o u sr e s u l t s n o w ，w el i s tt h e c o n c l u s i o n so ft h i sc h a p t e r c o n c l u s i o n2l e tgb ea3 - c o n n e c t e dg r a p hd i s t i n c t 加仇w h e e l sw i t hg l 6 a n dcal o n g e s tc y c l e t h e n ( 11i fcd o e sn o tp a s st h r o u g ha n ym a x i m a ls e m i w h e e l , t h e ncc o n t a i n sa tl e a s t t h r e er e m o v a b l ee d g e s ； ( 2 1l lcp a s s e st h r o u g hp r e c i s e l yo n em a x i m a ls e m i w h e e i , t h e nc c o n t a i n sa tl e a s t t w or e m o v a b l ee d g e s ； ( 3 ) i fcp a s s e st h r o u g hp r e c i s e l yt w om a x i m a ls e m i w h e e t s ，t h e ncc o n t a i n sa r e 。 m o v a b l ee d g e c o n c l u s i o n3l e tgb ea3 c o n n e c t e dg r a p hw i t h o u ta n ym a x i m a ls e m i w h e e l s a n dl e ttb eas p a n n i n gt r e e g t h e nt h e r ea r ea tl e a s tt w or e m o v a b l ee d g e s 饥 o ro f ft c o n c l u s i o n4l e tgb ea3 - c o n n e c t e dg r a p ho na tl e a s t6v e r t i c e sa n dl e tcb ea l o n g e s tc y c l e 盯g 玎i e ( c ) ne r ( g ) l 5 ，t h e nch a sac h o r d c o n c l u s i o n5l e tgb ea3 - c o n n e c t e dg r a p ho na tl e a s t9v e r t i c e sa n dl e tcb e al o n g e s tc y c l e 巧g 可l ( e ( g ) 一e ( c ) ) ne r ( c ) i 7a n dt h e r ei sn oa t o mo f g v e r t e x d i s j o i n t 栅现c t h e nch a sac h o r d i nc h a p t e r4 ，w ef o c u so nt h ed i s t r i b u t i o no fr e m o v a b l ee d g e si n5 - c o n n e c t e d 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 g r a p h s f o r5 - c o n n e c t e dg r a p h sg ，x ug o t n oa t o m s ，t h e na n yc y c l ec o n t a i n sa tl e a s t o rg ( g ) 4 ，t h e na n ys p a n n i n gt r e eo fg w ee x t e n dt h e s er e s u l t s t h a t ，i f6 ( g ) 6o rg ( a ) 4o rgh a s t w or e m o v a b l ee d g e si ng ；i f6 ( g ) 6 c o n t a i n sa tl e a s tt w or e m o v a b l ee d g e s c o n c l u s i o n6l e tgb ea5 - c o n n e c t e dg r a p hw i t ho r d e ra tl e a s t8 t h e na n y t m a n g l ec o n t a i n sar e m o v a b l ee d g e c o n c l u s i o n7l e tgb ea5 一c o n n e c t e dg r a p hw i t ho r d e ra tl e a s t1 0a n dca c y c l e 0 1g t h e n ( 1 ) i lci sv e r t e x d i s j o i n tw i t ha n ya t o m ，t h e ncc o n t a i n st w or e m o v a b l ee d g e s ： ( 2 ) i | ch a sc o m m o nv e r t i c e sw i t hp r e c i s e l yo n ea t o m 。t h e ncc o n t a i n sar e m o v a b l e e d g e ； l3 ) l lgc o n t a i n sn oa t o m sa n dci sah a m i l t o nc y c l e 。t h e ncc o n t a i n sa tl e a s t t h r e er e m o v a b l ee d g e s ； 似ji fd ( x ) + d ( y ) 1 1f o ra n yp a i ro fa d j a c e n tv e r t i c e sz ：yi ng ，t h e ncc o n t a i n s t w or e m o v a b l ee d g e s c o n c l u s i o n8l e tgb ea5 一c o n n e c t e dg r a p hw i t ho r d e ra tl e a s t1 0a n dt a s p a n n i n gt r e e0 lg 1 lgc o n t a i n sn oa t o m s 。t h e ntc o n t a i n sa tl e a s tt w or e m o v a b l e e d g e s t h el a s tp a r to ft h et h e s i si sd e v o t e dt ot h ep r i s mc y c l a b i l i t yo fg r a p h s t h e p r i s mo v e rag r a p hg i st h ec a r t e s i a np r o d u c tg 口鲍o fgw i t ht h ec o m p l e t eg r a p h 鲍gi ss a i dt ob ep r i s mh a m i l t o n i a ni fg f - k 2i sh a m i l t o n i a n w es a yt h a tas e t 日v ( a ) o fv e r t i c e si sc y c l a b l ei ngi ft h e r ei sac y c l eci ngc o n t a i n i n ga l l v e r t i c e so fh f o rh y ( g ) ，w es a yt h a thi sp r i s mc y c l a b l ei nc d k 2f fh uh 7 w h e r eh 7i st h ec o p yo fhi sc y c l a b l ei ng d k 2 t h eh u n tf o rh a m i l t o nc y c l e si n g r a p h si so n eo ft h eo l d e s ta n da l s oo n eo ft h em o s ti n v e s t i g a t e dt o p i c si ng r a p h s s i n c et h ec o n c e p tw a sf o r m a l l yi n t r o d u c e db yh a m i l t o ni n1 8 5 7 ，t h e r eh a v eb e e n al a r g en u m b e ro ft h e o r e m s ，c o n j e c t u r e s ( b o t ho p e na n dr e f u t e d ) ，s u r v e y s ，a n d w e bs i t e sd e d i c a t e dt ot h i sh u n t o n eo ft h er e c e n tt r e n d si st of i n dv a r i a t i o n s o nt h en o t i o no fah a m i l t o nc y c l ef o rt e s t i n gh o w “c l o s e ”ag i v e ng r a p hgi s t ob e i n gh a m i l t o n i a n 鼢eg r a p hw i t ht h ep r o p e r t yo fb e i n gp r i s mh a m i l t o n i a ni s s u