（基础数学专业论文）二部图的覆盖和2连通、无爪图的hamilton性.pdf

查苎垄兰堡主兰堡垒查 一一! 查! l 摘要 随着现代科学技术的不断发展，图论已成为十分有用的学科，它 广泛应用于交通运输、计算机科学等领域，所以，至今仍有许多学者 研究图论问题。 在本文的第一章中，了解了图论的历史和现状，又给出了本文的 主要内容、研究目的和意义：在第二章中，介绍了本文所需的定义等 一些预备知识，在第三章中，研究了图的一类特殊的覆盖；在第四章 中，讨论了图的h a m i l t o n 问题，其中，第一节，回顾了很多h a m i l t o n 问题的好结果，在第二节中，应用距离为3 的点的度数和这一条件， 给出了在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 图、距离、无爪图 a b s t r 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 d t ob eav e r yu s e f u ls u b j e c t i ti su s e di nm a n yf i e l d s ，s u c h 够t r a f f i ca n dc o m p u t e r s 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 t e r1 , w es t u d yt h eh i s t o r ya n d p r e s e n ts i t u a t i o n o f g r a p ht h e o r y ；a l s ow ep o i n t t 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 t e r2 , w ei n t r o d u c e s 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 nc h a p t e r3 , w es t u d yas p e c i a lk i n do fc o v e r i n g si n g r a p h s i nc h a p t e r4 , w es t u d yt h eh a m i l t o n i a n i ns e c t i o n1 ，w el o o kb a c ko nm a n y a c h i e v e m e n ti nh a m i l t o n i a n i ns e c t i o n2 ，w ep r o v et h a tt h e r ea r eh a m i l t o nc y c l e si n 2 - c o n n e c t e d ，k 1 3 - f r e eg r a p h s n o wt h e r ea r ef e ws t u d i e si nt h ec o v e r i n g so f g r a p h s ，f i r s t ，i nt h i sp a p e rb yr e s t r i c t i n g t h es u no ft w od i s a d j a c e n tv e r t i c e s w eg e tc y c l e sw i t l lg i v e ne d g ei nb i p a r t i t eg r a p h s m t lc y c l e s n e x t ，b yu s i n gt w ov e r t i c e sw h o s ed i s t a n c ei s3 ，w eg e tas u f f i c i e n t c o n d i t i o no fh a m i l t o n i a nf o rt h ef i r s t t i m e ，i t i sa l s oaf l e wm e t h o dt o s t u d y h a m i l t o n i a n k e y w o r d ：c o v e t i n g ，b i p a r t i t eg r a p h s ，h a m i l t o n i a n ，d i s t a n c e ，k ! , 3 - f r e eg r a p h s 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论 文中取得的研究成果除加以标注或致谢的地方外，不包含其他人 已经发表或撰写过的研究成果，也不包括本人为获得其他学位而 使用过的材料。与我一同工作过的同志对本研究所做的贡献均已 在论文中作了明确的说明并表示谢意。 本人签名：王蛘 日 查些查堂塑主芏堡垒查 苎二主三i 立 第一章引言 第一节图论的历史和现状 图论是近二十年来发展十分迅速，应用比较广泛的一个新兴的数学 分支。1 9 3 6 年，哥尼格发表了世界上第一本图论专著，从此，图论成为 一门独立的学科，特别是近十多年来，它的发展更是惊人，人们对于线 性图的理论和各方面的广泛应用进行了大量的工作。在当今世界知识爆 炸的时代，科学技术突飞猛进，信息量向暴风雪般的增加，各门学科相 互渗透。图论作为组合数学和离散数学的重要分支，是富有趣味和应用 极为广泛的一门学科，是研究自然科学，工程技术，经济管理和社会问 题的一个重要数学工具。图论应用的范围很广，它不仅应用于自然科学， 也应用于社会科学。它非但广泛应用于电力网络、电信网络、运输能力、 开关理论、编码理论、控制论、反馈理论、随即过程、可靠性理论、化 学化合物的辨识、计算机的程序设计、故障诊断、人工智能、印刷电路 板的设计、图案识辨、地图的着色、情报检索，也应用于诸如语言学、 社会结构、经济学、运筹学、兵站学、遗传学等等方面。因此，图论受 到了全世界数学界和工程技术界乃至经济管理者，越来越广泛的重视。 另一方面，图论和数学的其它分支，如群论矩阵论，概率论，拓 扑学，数值分析，组合数学等都有着密切的联系。事实上，图论为任何 一个包含了一种二元关系的系统提出了一个数学模型；部分地，也因为 它是用了图解式的表示方法，图就具有了一种直观的和符合美学的外形。 在这个领域里，虽然有一些结果在本质上看来似乎是初等的，但是，图 论中的确存在着大量的、十分错综复杂的问题，对于这些问题往往可以 查垄苎兰塑主茔堡垒查 一生= 生! ! ! l 难住最好的、甚至是声誉卓著的极其老练的数学家。 总之，图论是一门十分有用的科学，无论从理论上，还是从实践两 方面来看，都是前途无量的。 关于图论的历史和现状 一个图就是一集合v 连同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 实际上是把每个电网络用它的基本图来代替。他还证明，为了 解这个方程，并不需要分别考虑一个电网络的图中的每一个圈，与此相 反，他用一个简单而有力的构造法指出，只要考虑一个图的任何一个“生 成树”所能决定的那些独立圈就够了。他的这个方法，现在已经成为一标 准的方法。 查i ! 查芏堡主堂堡垒查 苎= 主型：t k i r e h h o f f 到c a y l e y 的十年 1 8 5 7 年，c a y l e y 非常自然的在有机化学的领域中发现了一族重要的 图，称为树。他从事于计算有给定的碳原子数为疗的饱和碳氢化合物： 巴h ：。的同分异构物。当然，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 这样做 “一点也没有觉察到它与现代化的化学学说有关”。我国著名化学家唐敖 庆教授把图论应用于化学方面也取得了一系列成果。 关于四色问题 l8 5 0 年g u t h r i e 在给他的兄弟f r e d e r i e h 的信中提到四色问题 并且发现荚格兰地图可以用四种颜色进行染色。f r e d e r i e 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 年之 后，因为这个问题一直没有人能够解决，所以才把此问题向伦敦数学会 的会员公布征解。可以说，在图论中，也许在全部数学中，最出名的难 题，要首推着著名的“四色猜想”了。任何一个数学家可以在五分钟之 内将这个非凡的问题向一个普通人讲述清楚，可是在讲述清楚之后，虽 然两个人都懂得了这个问题，但是，要解决它，可谁也无能为力。 18 7 9 年k e m p e 给出了这个猜想的许多个错误“证明”中的第一个“证 明”还有t a i t 也发表论文，宣称证明了四色问题可是十年以后 1 查些垄兰堡主堂堡笙查一三，已三! ： 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 多个机时，从此，4 c c 便晋 升为四色定理：x ( 平面图) 4 。 四色猜想的原始提法是：地图或地球仪上，最多用四种颜色即可把 每一国之版图染好，使得国界线两侧异色。 这个问题如此之简单，但是，1 9 7 6 年以前的百余年问，有多少精千 的数学家潜心研究过它，无奈谁也未能得出实质性进展，时至今日，仍 欠理论性( 非计算机的) 证明。当然，大批优秀数学家的工作并非徒劳， 人们在冲击4 c c 时采用的思路、方法和技巧，为图论的宝库增添了一个 又一个精彩成果，例如，1 9 1 2 年b i r k h o f t 提出了颜色多项是理论。1 8 7 9 年，伦敦数学会的k e m p l e 发表了证明4 c c 的论文，尽管他的证明十年 后被人指出错误，但k e m p l e 的极为精巧的论证方法，用a p p e l 的话来说， 其实“包含着一个世纪后终于引出正确证明的绝大部分基本思想”1 8 9 0 年，h e a w o v d 用k e m p l e 的方法证明了五色定理欲平面图) l m i ，则m 称为g 的最大对集。 图g 的一个覆盖是指矿的一个子集k ，使得图g 的每条边都至少有 一个端点在足中。图g 的一个h a m i l t o n 圈c ，也是图g 的一个覆盖。 设s 是g 的一个子集，若s 中的任意两个顶点在g 中均不相邻，则 称s 为g 的一个独立集。 子集z 称为g 的本质独立集，如果乜，z ：) 量z ，满足d ( z 。，z ：) = 2 ，这 里a ( z 。，z 2 ) 表示点毛和z ：之间的距离。 对于0 q k ，有一个非负的有理序列( q ，0 2 c 口。) ，称为( g ，i ) - l t w 序列，如果它满足： ( 1 ) 口l 1 ； ( 2 ) 对于v i i ，f 2 ，i s 2 ，3 ，g + 1 ) ，。o 七+ l ，则：。i ( 气- 1 ) s 1 。 东北大学硕士学位论文 第三章有圈二部图的覆盖 第三章有圈二部图的覆盖 在文【13 1 中猜想，对于任意整数k 2 ，存在( ) 使得二部图 g = ( k ，吒，e ) 中，”l - - i x l = ( k ) ，且对于g 中任意一对不相邻的顶点 x k ，匕，有d ( 砷+ d ) 雄+ 七。那么，对于g 中任意k 个独立边 e i , e ：，巳，存在顶点不重的k 个圈c i ，c 2 ，q ，使得 e ，e ( c t ) ，ie 1 , 2 ，一，k 和v ( c lt , j c 2u u q ) = v ( o ) 。文【l3 】【1 2 对于 k = 2 ，3 时证明了猜想成立，本章中对于k = 4 证明了猜想的正确性。 在本章中，讨论的只是简单的有限图，所使用的术语和记号请参 见文 ii 儿l3 】。设g