（应用数学专业论文）无爪图的周长及hamilton性.pdf

东北大学硕士学位论文摘要 无爪图的周长及h a m i l t o n 性 摘要 随着现代科学技术的不断发展，图论已经成为十分有用的学科，它的广泛应 用于交通运输，计算机科学等领域，所以，至今仍有许多学者在致力于图论的研 究工作。 在本文的第一章中，了解了图论的历史和现状，同时给了本文的主要内容， 研究目的和意义；在第二章中，介绍了本文所需的定义等一些预备知识，在第三 章中我们研究了3 一连通无爪图的最长圈问题。其中，第一节，回顾了很多好的 结果和定理，在第二节中，应用幅度的概念，给出了在3 一连通无爪图中，所包 含的最长圈长度的下限。在第四章中重点研究了h a m i l t o n 性的问题，其中第一节 介绍了h a m i l t o n 问题在近些年来的主要的结果。在第二节中给出了2 连通无爪图 是h a m i l t o n 图的一个充分条件。 本文中，我们通过对幅度的研究，给出了3 一连通无爪图最长圈的下界和2 一 连通无爪图是h a m i l t o n 图的充分条件。本文的研究结果，加深了人们对于无爪图 h a m i l t o n 性的了解，有利于进一步认识并最终解决h a m i l t o n 问题的研究工作。 关键词：3 一连通无爪图周长幅度 东北大学硕士学位论文 a b s t r a c t l o n g e s tc y c l e sa n dh a m i l t o np r o p e r t i e so fk 1 ，3 一f r e eg r a p h s a b s 仃a c t w i t ht h ed e v e l o p m e n to fm o d e ms c i e n c ea n dt e c h n o l o g y , g r a p ht h e o r yh a sb e e n p r o v e dt ob eav e r yu s e f u ls u b j e c t i t i su s e di n m a n yf i e l d s ，s u c h a st r a f f i ca n d c o m p u t e rs c i e n c e ，s om a n yp e o p l es t u d yt o p i c si ng r a p ht h e o r y i nc h a p e ro n e ，w es t u d yt h eh i s t o r ya n dp r e s e n ts i t u a t i o no fg r a p ht h e o r y ；a l s ow e p o i n tt h em a i nw o r k ，t h ep u r p o s ea n dt h em e a n i n go fo u rs t u d y i nc h a p e rt w o ，w e i n t r o d u c es o m ed e f i n i t i o n sa n dt e r m i n o l o g i e s i n c h a p e rt h r e e ，w es t u d y t h e c i r c u m f e r e n c ei n3 - c o r m e c t e dc l a w - f r e eg r a p h s i ns e c t i o no n e ，w el o o kb a c ko nm a n y a c h i e v e m e n ta n dm e t h e d s i ns e c t i o nt w o ，w eg e tt h ec i r c u m f e r e n c ei n3 - c o n n e c t e d c l a w - f r e eg r a p h s i nc h a p e rf o u r , w es t u d yt h eh a m i l t o n n i a n i ns e c t i o no n ew el o o k b a c ko i lm a n ya c h i e v e m e mi nh a m i l t o n i ns e c t i o nt w o ，w eg i v eas u f f i c i e n tc o n d i t i o n f o rh a m i l t o n i a ni n2 - c o r m e c t e dc l a wf r e eg r a p h s b yu s i n gs p o k en u m b e r , w eg e t t h ec i r c u m f e r e n c ei n3 - c o n n e c t e dc l a w - f r e e g r a p h sa n das u f f i c i e n tc o n d i t i o nf o rh a m i l t o n i a ni n2 - c o n n e c t e dc l a wf r e eg r a p h s t h e r e s u l to ft h i sp a p e rc a r lh e l pp e o p l et os t u d yc l a wf r e eg r a p h sa n dt h er e l a t i o ns p o k e n u m b e ra n dh a m i l t o n p r o p e r t y k e y w o r d s ：3 - c o n n e c t e d ，c l a w - f r e eg r a p h ，c i r c u m f e r e n c e ，s p o k en u m b e r 1 1 1 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成 果除加以标注和致谢的地方外，不包含其它人已经发表或撰写过的研究成果，也 不包括本人为获得其它学位而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 学位敝作者繇闻诳 日期”y 。2 西 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规 定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论 文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关 数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文第一章引言 第一章引言 1 1 图论的历史和现状 图论是近二十年来发展十分迅速，应用比较广泛地各新型的数学分支支。1 9 3 6 年，哥尼格发表了世界上第一本图论专著。从此，图论成为一门独立的学科，特别 是近十年来，它的发展更是惊人，人们对于线性图理论和各方面的广泛应用进行 了大量的工作。在当今世界知识爆炸的时代，科学技术突飞猛进，信息量象暴风 雪般增加，各门学科相互渗透，图论作为组合数学和离散数学的重要分支，是富 有趣味和应用极为广泛的一门学科，是研究自然科学，工程技术，经济管理和社 会问题的一个重要数学工具。图论应用范围极为广泛，他不仅应用于自然科学， 也应用于社会科学，它非但广泛应用于电力网络，电信网络，运输能力，开关理 论，编码理论，控制理论，反馈理论，随机过程，可靠性理论，化学化合物的辨 识，计算机程序设计，故障诊断，人工智能，印刷电路板设计，图案辨识，地图 的着色，情报的检索，也应用于诸如语言学，社会结构，经济学，运筹学，兵站 学，遗传学等方面。因此，图论受到了全世界数学界和工程技术界乃至经济管理 者，越来越广泛的重视。 另一方面，图论和数学的其他分支，如群论，矩阵论，概率论，拓扑学，数 值分析，组合数学等都有着密切的联系。事实上，图论为任何一个包含着一种二 元关系的系统都提出了一个数学模型；部分的，也因为它用了图解式的表达方法， 图就具有了一种直观的和符合美学的外形，在这个领域里，虽然有一些结果在本 质上看来是初等的，但是，图论中的确存在着大量的，十分错综复杂的问题，对 于这些问题往往可以难住最好的，甚至是声誉卓著的极老练的数学家。 总之，图论是- f 3 极为有用的学科，无论从理论上，还是从实践两方面来看， 都是前途无量的。 关于图论的历史和现状 一个图就是一个集合v 连同矿的一些二元子集的集合构成的一个数学结构。 1 7 3 6 年是图论历史的元年，图论的开拓者，大都公认的是1 8 世纪的大数学家e u l e r ， 东北大学硕士学位论文第一章引言 早在1 7 3 6 年，他曾研究过著名的k o n i g s b e r g 七桥问题，当时是作为一种数学迷宫 游戏研究的，e u l e r 及其漂亮的解决了这个问题，而且还把作了这个问题作了深入 一步的一般化了，并给出了关于一个图存在e u l e r 迹的判定方法( 即此图必须是连 通的，并且每个顶点都于偶数条边与之相关联) 。 在e u l e r 之后，大约过了一个世纪，到了1 8 4 7 年k i r c h h o f f 为了解类线性联 立方程而发展了树的理论，这个线性方程组是用来描述一个电网络的每一条支路 中和环绕每一个回路的电流的。它虽然是一个物理学家，但他像一个数学家那样 思考问题，他把一个电网络和其中的电阻，电容，电感等等都抽象化了，他用 个只由点和线组成的相应的组合结构来代替原来的电网络，而并不指明每条线所 代表的电器元件类型，这样一来，k i r c h h o f f 实际上是把每个电网络用它的基本图 来代替。他还证明为了解这个方程，并不需要分别考虑一个电网络的图中的每一 个圈，与此相反，他用一个简单而有力的构造法指出，只要考虑一个图的任何一 个“生成树”所能决定的那些独立圈就够了。他的这个方法，现在己经成为种 标准方法。 k i r c h h o f f 到c a y l e y 1 9 5 7 年，c a y l e y 非常自然的在有机化学的领域中发现了一族重要的图，称为 树。他从事于计算有给定的碳原子数为盯的饱和碳氢化合物g 皿。的同分异构 物，当然，c a y l e y 抽象的重新叙述了这个问题：求有p 个点的树的数目，其中每 个点的度等于1 或4 。他未能立即成功的解决这个问题，所以他改变了这个问题， 逐步计数了：有根树( 其中有一个点与其各点有区别的树) ，树，每个点的度至多 等于4 的树，从而解决了那个化学问题。后来，j o r d a n 作为一个纯粹的数学家， 他从纯数学的对象独立的发展了树( 1 8 6 9 年) 。s y l v e s t e r 于1 8 8 2 年曾说过：j o r d a n 这样做“一点也没有觉察到它于现代化的化学学说有关”。我国著名的化学家唐敖 庆教授把图论应用于化学方面也取得了一系列的成果。 关于四色闯题 1 8 5 0 年，g u t h f i e 在给他兄弟f r e d e r i c h 的信中提到了四色问题，并且发现 英格兰地图可以用四种颜色进行染色f r e d e r i c h 问他的老师d e m o r g a n 继而 d e m o r g a n 又将此问题提出给h a m i l t o n 。过了2 0 年之后，因为这个问题一直没有 一2 一 东北大学硕士学位论文第一章引言 人能够解决，所以把此问题向伦敦数学协会的会员公开征解。可以说，在图论中， 也许是在全部数学中，最出名的问题，要首推著名的“四色问题”了。任何一个 数学家可以在5 分钟之内将这个非凡的问题向一个普通人讲述清楚，可是在讲述 清楚之后，虽然两个人都懂这个问题，但是，要解决它，谁也无能为力。 1 8 7 9 年k e m p e 给出了这个猜想的许多错误“证明”中的第一个“证明”。还 有t a i t 也发表论文，宣称证明了四色问题。可是十年以后h e a w o o d 发现了k e m p e 的错误，然而他应用了k e m p e 的思维方法证明了五色问题。后来，o r e 和s t e m p l e 对于少于4 0 个国家的所有地图证明了这个猜想，所以，有人推测，假如一旦找到 一个反例，那它一定是极其庞大和复杂的。在探求真理得到路上，通过人们的不 断努力，四色问题这个困惑人的问题，终于在它诞生后的1 2 6 周岁时获得了解 决，1 9 7 6 年伊利诺大学的a p p l e 和h a k e n 在k o c h 的协助下，用计算机证明了数 学史上悬挂多年的四色猜想是正确地。这是二十世纪科学史上重要事件之一。他 们用了一百亿次逻辑判断，花了1 2 0 0 多个小时，从此，四色猜想便晋升为四色定 理：z ( 平面图) 4 。 四色问题的原始提法是：地图或地球仪上，最多用四种颜色即可把每一国的 版图染好，使得国界线两侧异色。 这个问题如此简单，但是，1 8 7 6 年以前百余年间，有多少精干的数学家潜心 研究过它，无奈谁也未能得出实质性进展，时至今日，仍欠理论性( 非计算机) 证明。当然，大批优秀数学家的工作也并非徒劳，人们在冲击四色猜想时采用的 思路，方法和技巧，为图论的宝库增添了一个又一个精彩的结论，例如，1 9 1 2 年 b i r k h o f t 提出颜色多项是理论。1 8 7 9 年，伦敦数学会的k e m p e 发表证明四色猜想 的论文，尽管他的证明在十年后被证明是错误的，但k e m p e 的极为精巧的论证方 法，用a p p e l 的话来说，其中“包含了一个世纪后终于引出正确证明的绝大部分 基本思想”。1 8 9 0 年，h e a w o o d 用k e m p e 的方法证明了五色定理：z ( 平面图) z + ，或y ? z 岛，则i ( 口，口。) 巨la r o ( a , + 1 ) n ( 口，口。) i + ，+ 1 ， ，= l 其中f + 3 时，值取i + ，一3 ，f ，_ ，= 1 , 2 ，3 ，= m i n | p ( u ，“) | | i = 1 , 2 ，3 ) ，再设 ( 口，) n ( a ，a 。) = 爿，等，f f )， 乙( 口i 1 ) n ( d ，d 。+ ) = 叩? ，群，7 产 ， 。( 口i 1 ) n ( a 。，a i + 2 ) = 岔，等，f j 。) ，以上结果对口i 1 ，i = 1 , 2 ，3 ，亦成立。 证明：以i = 1 ，x ， y j 为例证明之，其他情形同样证明 设 z 0 ( d j l ) n ( 口l ，口2 ) ， z n 。( 口；1 ) n ( 口j ，a 2 ) ，且x z， ( 。( 口1 ) u 。( 4 ；1 ) ) n ( z ，主) = g ，贝0 i ( y ，z ) | ，+ 1 否则有更长圈 于是引理得证。 c + = a i p ( u 1 ，甜2 ) a 2 ，x 】 。? 1 ，z 口；1 ，a , - 1 d 一1 5 东北大学硕士学位论文第三章3 一连通无爪图的周长 命题及定理证明 受到文献 5 1 ， 5 2 的启发，本章通过对图的幅度o ( g ) 的研究，猜想了下面 的定理并给出了证明。 定理a ：在3 一连通非h a m i l t o n 无爪图中，图g 的最长圈的长度： c ( g ) m i n 3 0 ( g ) + 占，6 d 。 为证明该定理，我们先来证明下面两个命题 命题l ：设g 为3 连通非日无爪图，c 为g 的最长圈，若o ( d ) 5 + ，则 c ( g ) m i n 3 0 ( g ) + 万，6 5 。 证明：若o ( g ) 占+ ，则必存在点z v ( r + ) ，使d ( z ) = o ( c ) ，a ( z ) j 情形a ：设z 是r 的孤立点，则n ，( z ) = n ( z ) ，立即有c ( c ) 4 0 ( g ) 情形b ：设r c r 是r 的连通分支，且r = “，z ，因为g 是3 连通的，故 虬( ”) a ，由虬( z ) 此时有c ( g ) 24 0 ( g ) 情形c ：设r c r 是r 的连通分支，且lz ( r ) 障3 ，z r ，因为g 是3 连通 的，故至少有3 点“，v ，1 4 ) er ，是c ( “) o ，n 。( v ) o ，n 。( w ) o ，且 【p ( u ，v ) 陋d r ( z ) + 1 ，i p ( v ，“) | d + 1 ，l p ( w , u ) 除d 月+ 1 。 情形1 ： y f o ，或 z f a ，或 叩l j ) a ，或 “) o ，i = 1 , 2 ，3 至 少有一个标号成立不妨假设协。 0 ， 爿 g 。 情形1 1 ： , 7 a ，且玎 x 产 断言1 ：j ( 口? 1 ，y i ) 险d 。( ：) + 1 否则有更长圈 c = 眇 ，a p ( u ，v ) a 2 口；1 1 ；2 1 口? 1 】y ： 同样可得 断言2 ：l ( 口；1 ，2 1 ) j d r ( ：) + 1 断言3 ： i ( 叩，口尹) 陲d 。( z ) + 1 否则有更长圈 c = 一 7 7 ，廿i 】p ( “，v ) a 2 n i l 【o ；1 ，i 1 】 情形1 2 ： r 刁f ) ，且叩 鼻。，f _ 1 , 2 ，3 ，至少有一标号条件成立。不妨假设 工产 簋。由g 的3 连通性，( 日 口；。) 上必有顶点与( 口：，a ，) 或( d ，a 1 ) 上的 顶点相连。不妨设z ( d i l ，町1 ) ，z x y ( 。2 ，a 3 ) ，且x y e 。 考虑顶点口一和 x 以与口的关系，已知口i 1 不与 工，) 中任何顶 点相联，由无爪性有( z i ) 为完全图。 断言5 ： l ( x ，z + ) i + i ( 口r ，_ y ) 巨d r ( z ) + 1 1 7 东北大学硕士学位论文第三章3 一连通无爪图的周长 否则有更长圈 c = a i d i l ，y 【z ，口一】 茁+ ，a 3 1 】日；1 a 3 p ( w ，u ) a 1 j 断言6 ： i ( x 一，算) l + i ( 工，d ，) 1 + i ( _ y ，口i 1 ) 陲d r ( z ) + 1 否则有更长圈 c = 口1 口一【口i 1 ，z 一】 x ，x 】眇，口】d i l a 2 p ( v ，u ) a l 所以有 c ( g ) 3 0 ( g ) + j + 3 情形2 2 ： 算产 矗。，i = 1 , 2 ，3 ，此时显然有 c ( g ) 6 6 至此命题1 证毕 命题2 ： 设g 为3 连通非日无爪图，臼( g ) 万，即对一切z v ( r ) ，则 c ( g ) 3 0 ( g ) + 占 证明：若口( g ) y l + ：，或_ y o i ： z i 。，i = 1 , 2 ，3 。上述条件至 少一个标号成立，x c a 1 ( i = 1 , 2 ，3 ) 的邻域作同样的假设，由引理3 1 4 立刻有 c ( a ) 3 6 + d 月( z ) + 3 同命题1 有 c ( g ) 3 6 + j + 3 3 0 ( g ) + 占+ 3 情况b ：z ， ：7 1 ，或x 5 y l + 2 ，或聪；： z k ，对一切i = 1 , 2 ，3 成立。对 a , - 1 ( i = 1 , 2 ，3 ) 的邻域亦成立。 情形1 ： z ? 庐，i = 1 , 2 3 至少一个标号成立，或 叩? ) 矽，i = 1 , 2 ，3 至 少一个标号成立，不妨假设f 即f ) ，叩( 印，) 。 情形1 1 ：叩 y ；，设 叫 中与叩相邻的顶点为x + ，x 一，观察点口】， 日产，戈，与日1 的关系，由无爪性有下面三种情况： ( 1 ) 口i 1a e 1 8 东北大学硕士学位论文 第三章3 一连通无爪图的周长 断言1 ：1 ( x ? 1 ，j ，：) 陋d r ( z ) + 1 否则有更长圈。 c = 日r ，口i 1 】 口2 ，x ， 口i 1 l p ( u ，w ) a 3 口；i ，y ：】口；1 ( 2 ) 口i 1x ? - e ，同样可得断言1 。 ( 3 ) 口产z ，e 断言2 ：j ( x 一，刁) i + l ( x 产，y 1 ) l d r ( z ) + 1 否则有更长圈。 c = 【口；1 ，口i 1 】 叩，工，1 口r ，x 一】口1 a 。p ( u ，w ) 口，y ； 4 ；1 情形1 2 ：y ： 刁 z ：，设 叫) 中与叩相邻的顶点为y + ，y + 断言3 ： i ( y 一，7 ) 1 2d 月( z ) + 1 否则有更长圈。 c = 口；1 ，口i 1 】【叩，口3 p ( w ，“) 【口l ，y 一 口；1 情形1 _ 3 ： z ； 3 0 ( g ) + j 情形3 2 ：i x d n 彰) p 1 ，i = 1 , 2 ，3 类似命题l 中情形2 1 可得 c ( g ) 3 6 + + d r ( 三) + 3 3 0 ( g ) + d r ( z ) + 3 总之，若d 。，( z ) = 妒，则立即有 c ( g ) 3 6 + + 占+ 3 3 0 ( g ) + j + 3 若d 。( z ) 矿，则c 路中另有3 1 d 。( z ) 1 个顶点，所以： c ( g ) 3 6 + 占3 0 ( g ) + 占 至此命题2 证毕 定理a ：在3 一连通非h a m i l t o n 无爪图中，若o ( g ) 为图g 的幅度，则图g 的 最长圈的长度： c ( g ) m i n 3 0 ( g ) + 万，6 占 。 证明： 由命题1 ，命题2 立即可得定理证明。 3 3 小结 h a m i l t o n 问题多年以来一直是人们关注的问题，可一直都没有得到一个图是 h a m i l t o n 图的充分必要条件，于是人们开始从图的最长圈问题入手，试图解决 h a m i l t o n 问题。在本章中，我们研究了3 一连通无爪图的最长圈问题。其中，第一 节，回顾了很多好的结果和定理，在第二节中，应用幅度的概念，给出了在3 一连 一2 0 - 东北大学硕士学位论文第三章3 一连通无爪图的周长 通无爪图中，所包含的最长圈长度的下限。在3 一连通非h a m i l t o n 无爪图中，若 o ( o ) 为图g 的幅度，则图g 的最长圈的长度的下限m i n 3 0 ( g ) + 占，6 8 。 一2 l 一 东北大学硕士学位论文 第四章2 一连通无爪图的h a m i l t o n 性 第四章2 一连通无爪图的h a m i l t o n 性 在目前研究无爪图h a m i l t o n 性的文献中，绝大多数使用的是最小定点度j 和 独立点集的度数和来讨论的，本章应用幅度a ( g ) 的概念，找到了2 一连通无爪图 是h a m i l t o n 图的一个充分条件。 受文献 5 3 1 的启发，本章通过对幅度0 ( g ) 的研究，得到了在n 阶2 一连通无爪 图g 中，曰( g ) 为图g 的幅度，若口( g ) = l 一j 一2 ) 时，则g 为h a m i l t o n 图。 本章中，g 表示有限简单图，d ( 种表示点x 的度数，巧为g 的最小顶点度 万= m i n d ( x ) ix v ( g ) ，占为图g 中所有的距离为3 的两点顶点度较大的度 数的最小值， 5 = r a i n m a x ( d ( x ) ，d ( y ”lx ，y y ( g ) ，d ( x ，力= 3 即f a n 型定理条件 c ( g ) 表示图g 的周长。 c = x l ，x 2 x , d 一( z 川= x 1 ) 为g 的圈。 【z ，工】_ c x ，x ，】_ x ，x x ，( x ，x j ) = i x ，z 】一 z ，z j ) 。( x ，x ，) 表示c 上短弧 段的定点集。p 表示g 的路，以茁，口，珊分别表示点的连通数，点的独立数， 和分支数。 称g 是1 一坚韧图( 简称坚韧图) ，如果对任意使c a ( g s ) 1 的子集 s 矿( g ) ，有c o ( g s ) q s i 。 当1 聊口( g ) 时，盯。( g ) = m 血 。s d ( “) f 趵g 的埘个点的独立集) a 本文用幅度0 ( g ) 来讨论3 一连通无爪图的最长圈，取得一定结果，下面先介 绍幅度这一概念： 设g 为p 阶3 连通无爪图记 f = cic 是图g 的最长圈) 而对任cef ，定义 邢，= 毒辣：篙溯g 。c 朋 并i d t ，( g ) = m 掘x f ( c ) l c f ) ，称o ( g ) 是图g 的幅度( s p o k en u m b e r ) 其它的术语和记号请参考文献 1 1 和 2 5 。 东北大学硕士学位论文 第四章2 一连通无爪图的h a m i l t o n 性 4 1 关于h a m iit o n 问题的回顾 h a m i l t o n 是一个古老的问题，有过很多好的结果，下面是对于h a m i l t o n 性问 题的一些回顾。 在文献 4 1 1 中对于k 正则的无爪图给出判断如下： 定理4 1 1 1 ：设g 为k 正则的2 一连通无爪图，则 ( 1 ) c ( g ) m i n l 矿( g ) i ，4 尼一2 ； 2 ) 当l v ( g ) 恒5 k 一3 时，g 为h a m i l t o n 图。 关于g 的独立点集与g 的h a m i l t o n 性的关系，有下面一些熟知的结果。 定理4 1 2 t 4 2 】：若盯2 ( g ) 昙 1 ，则g 是h a m i l t o n 图； 定理4 1 - 3 ”1 ：若盯，( g ) 胛3 ，则g 是h a m i l t o n 图； 定理4 1 4 | 4 3 j ：若a ( g ) r ( g ) ，则g 是h a