（基础数学专业论文）关于一些图的ramsey数.pdf

大连理工大学硕士学位论文 摘要 图论是离散数学的一个重要分支，它在物理、化学、天文、地理、生物学，尤其是计 算机科学中有非常广泛的应用 本文主要研究某些图的r ，s e y 数问题，对任意两个图g 和h ，图的r a h l s e y 数r ( g ， h ) 定义为最小的整数n ，使得阶数为n 的任意图f 都包含g 作为子图或f 包含日作为 一个子图本文研究了树对轮的r 枷8 e y 数本文主要内容及结构如下： 在第一章中简要叙述了图e y 数的发展，介绍了图论的基本概念和术语 由于星图的特殊性，星图对其它图的砌m s e y 数得到了广泛的关注在第二章中研究 的是星对轮的胁m s e y 数在本掌中先给出并证明了关于图的r a a s e y 数的一些结果然 后利用文献【2 6 】和 3 2 介绍并讨论了星对轮的一些结果 路径也是一类特殊的图许多数学工作者都对关于路径或轮的戤m m e y 数进行了研 究在第三章我们研究的是路径对轮的勘衄s e y 数f 钆d r e e 等人考虑了所有路径对圈的 r a 。s e y 数 s u r a h m a te t 蛆得到了路径对矾或t 的r 8 a s e y 数陈耀军从更一般的情 况考虑了路径对轮的鼬m s e y 数并给出了下面的结果： 毋昂，w 鲁) = 3 n 一2 ，对奇数m 且 m 一1 2 ；r ( r ，w 。) = 2 n 一1 ，对偶数m 且n m 1 3 因此在第二节中我们就给 出了路径对轮在其他情况下的结果； 以及这样一个边界：若m 6 ，m 为偶数且n + 2 m 2 n 一4 ) 或为偶数，n 4 ， m = 2 n 2 或m 2 n ) ，则 m + 争z 渊r 删 ( 籍k ，m m + 簖 ) 星和路径都是特殊的树，因此在第四章章中我们来研究树对轮的r a m s e y 数e t b a s k o r o 给出了树对w j 或w j 的r a d l s e y 数：r ( 霸，帆) = 2 n 一1 ，其中n 4 ；r ( ，w ，5 ) = 3 n 一2 ，其 中n 25 所以e t b a s k o r 0 猜想了下面的结果当n m 7 且m 为奇数时，r ( ，w ，m ) = 3 n 一2 本章第二节中我们就证明了当m 为奇数且m 7 时，r ( ，矸，m ) = 3 n 一2 ，其中 关键词：m m s e y 数；树；星；轮；路径 时 一 眨 一时 数 且+ 偶 数h 聃 敬渤 3 ， | | 时虻 一 仇m 轨孰 李群：关于一些图的r m 8 e y 数 o nr a m s e yn u m b e r so fs o m eg r a p h s a b s t r a c t g r a p ht h e o r yi sab r a n 出o fm a t h e m a t i c s ，e s p e c l a l l ya n 呈m p o r t 如tb r a n 出0 fd i s c r 吼em a t b e m a t i c s i th a sb e e a p p l i e di nm a n yd j 臼e n t 矗e l d si nt h em o d e r nw o r l d ，s u c ha sp h y s i c c s ， c h e i u i s t ha s t r o o 瑚孔g e o g r a p h y ) b i 0 1 0 瞄a sw e l la si nc o m p u t e rs c i e n c ea n de n 舀n e e r i n g t h i st h e s i 8d i s c u s st h er a m 8 e yn u l b e r so fg r 印h s f o r 百v e nt w og r a p h sg8 n d 日，t h e r a m 8 e yn u 瑚- b e rr ( g ：口) i sd e 6 n e dt ob et h e8 m a l l e s tp o s i t i v ei n t e g e r 乱s u 曲t h a te v e r yg r 印h fo fo r d e r n m u s tc o n t a i n ga sas u b g r a p ho r f m 8 tc 0 t a i n 日8 sas u b g r a p h w ed i s c u s s t h e r a m 8 e vn m n b e r sf o rt r e e 8v e r s u sw h e e l s t h es t r u c t 砒eo ft h i st h e s i 8i s8 r r a n g e da 8f o u a w s ： w er e c i t eb r i e 丑yt h ed e v 0 1 0 p m e n to ft h et h er a m s e yn u m b e r so fg r 印h s ，a n di n t r o d u c et h e b a s i cc o n c e p t so f 口a p ht h e o r ya n dt e r l si nc h a p t e r1 f b r t h es p e c i a l i t y0 fs t 甜f 印h ，t h er 衄s e ym 1 】l b e r so fs t a r 8v e r s u so t h e rg r a p h 8h a v e b e e nw i d e 垮c o n s i d e r e d i nc 1 1 a p t e r2 w es t u d yt h ei 洫l s e yn 眦曲e r so f8 t 8 r sv e r 8 l l sw h e e l s i n t h i sc h a 批e i ，w e 触8 t l y 舀v ea n dp r o v e8 0 m er e 锄l t 8a b o u tt h er a 1 s e yn u 血b e r so fg r a p b ；t h e n w ep r e 8 e ta n dd i s c u s ss o m er e s u l t so ft h er 鼬s e y u m b e r ss t a r sv e r s u sw h e e l sm b 虹n gu s eo f r e f e r e n c e sf 2 6 1a df 3 2 p a t hi sa l s o88 p e c 试g r a p h ， m a n yp e o p l ew o r k i n go nm 砒h e m a t i c sr e s e a r c l l e do nt h e r a m s e yn u m b e r so fp a t h 8o rw h e e l s i nc 1 1 印t e r3 ，w es t u d yt h e 胁n 8 e yn u m b e r so fp 诎l s v e r s u sw h e e l s f h u d r e ea n dd t b e r so o n s i d 删t h er 榔e yn u 珂b e r sf o ra l lp a t h c y d 8p a i r s s u r a h m a te t a lo b t a i n e d 七h e e yn 舢曲b e r 8o fap a t hv e r s l l s 胍o rw ，5 y a o j u nc h e n e v 翻u 8 t e dt h er a 皿s e yn u m b e r so fp a t h sv e r s u 8w h e e l si nam o r eg e l l e r 啦s i t u a t i 0 a n dg a v et h e f o 玎0 w i n gr e s u l t ：蜀r ，w k ) = 3 礼一2 ，f o r mo d da n d 住2 m 一1 兰2 ；r ( r ，h ，m ) = 2 佗一l ，f o r m e v e na 以d 几2m 一1 3 s ow eg i v et h e e yn u m b e r sf o rp a t h 8v e r s u 8w h e e l sf o ro t h e r c a s e si ns e c t i o n2 ： f 二+ ，芝三基篙= 。帅：。， r ( r ，4 ，仇) = m + 2f b r ( 扎= 3 姐do d d 竹t 5 ) l 豪：；芝竺墨麓f 甚篓攀酣坯畦2 一q a n ds u c hb o u n d ：i f 6 ，m i se v e a i 】d + 2 m 2 n 一4 ) o r ( ni 8e v e n ，n 4 ，m = 2 n 一2 0 r m 2 ”) ，七h e n m + 孚卜2 r ( r ，) m 詈； 一1 ) + n ，m + 簖” i i 大连理工大学硕士学位论文 s t a r 8a n dp a t h s 甜es p e c i 出t r e eg r 8 p h 8 s ow es t u d yt h er a 瑚s e yn u m b e r so ft r e e sv e 卜 8 u sw h e e l si nc 1 1 印t e r4 e t b a s k o r og a v et h e e yn u m b e r so ft r e e sv e r 8 u sw 4o rw 5 ： 冗( 矗，l k ) = 2 扎一1 ，w h e r e 住4 ；冗( 2 k ，佴，5 ) = 3 秆一2 ，w h e r e 托25 s oe t b a s b 。r og u e s s e d t h ef o l l a 呐n gr e s u l t ：r ( 矗，仰k ) = 3 他一2f o rn 兰m 7a n dmi so d d i nt h es e c t i o n20 f t h i s c h a p t e r ，w ep r o v et h ef o l l o w i n g 瑚u l t s ：r ，佴，m ) = 3 n 一2f o rm i so d da n dm 7 ，w h e r e n = m m + 1 m + 2 k q 懈r o r d $ i k m l s e ym l 珈l b e r ；t r e e ；s t a r w h e e l ；p a t h i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明 确的说明并表示了谢意。 作者签名：童盈差日期：罂i ! ! ：垡 大连理工大学学位论文版权使用授权书 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 夸月羊 j 竺叁 鲨! d 月上l 日 大连理工大学硕士学位论文 1 绪论 1 7 3 6 年是图论的历史元年，这一年欧拉( e l l l e r ) 研究了著名的柯尼斯堡七桥问题，发 表了图论的首篇论文，开创了图论科学的研究1 9 3 6 年，匈牙利著名的图论学家k o n 堙 发表了有限图与无限图理论，这是图论的第一部专著，它总结了图论二百年的主要 成果，是图论的重要里程碑此后，图论开始飞速发展起来，成长为数学科学中一门独立 的学科它的分支很多，例如，算法图论、极值图论、网络图论、代数图论、随机图论、 模糊图论、超图论等。由于现代科技尤其是大型计算机的迅速发展，使图论大有用武之 地，无论是数学、物理、化学、天文、地理、生物等基础科学，还是信息、交通、战争、 经济乃至社会科学的众多问题，都可以应用图论方法予以解决 图论是离散数学的骨干分支，离散数学则是计算机科学技术与网络信息科学的思想 基础多年来，为了实现高速计算的目的，数学促进了计算机科学的形成与发展例如图 灵机的数学理论为计算机的诞生打下了基础；另一方面，随着计算机科学在社会发展中 作用的日益提升，它又反过来促进数学的发展例如，1 9 7 6 年，伊利诺大学的a p p l e 和 h a k e n 用计算机证明了四色猜想成立1 9 9 3 年罗彻斯特理工学院的s p r 崩z i s z o w s k i 和 澳大利亚国立大学的b d m 出玎用计算机求得rm s e y 数r ( 4 ，5 ) = 2 5 图论最吸引人的特色是它蕴涵着大量强有力的思想、漂亮的图形和巧妙的论证，即 使是非常困难的尚未解决的问题，它的表述也可能是平易近人的。现实生活中处处可以 发现图论的难题，图论是最接近百姓生活、最容易阐述的一门数学分支，具有实质性的 难度又有简朴的外表是很多图论问题的特点之一，它的证明往往需要极其繁琐的细节 图论与数学的其它分支不同，它不象数论、拓扑等学科那样有一套完整的理论体系 和解决问题的系统方法图论所涉及的问题比较广泛，而解决问题的方法千变万化，非 常灵活，常常一种问题一种解决方法，而这些方法之间又豪无联系。因此，鹪决图论中 的问题不仅仅需要知识，而且还需要智慧和灵活深入的思考 二十世纪后，图论的应用已经渗透到许多的其他学科领域，如物理、化学、信息学、 运筹学、博弈论、计算机网络、社会学、语言学，以及集合论、矩阵论等从二十世纪五 十年代以后，由于计算机的迅速发展，有力的推动了图论的发展，使图论成为数学领域 中发展最快的分之之一 1 9 3 0 年，英国的逻辑学家f p s e y 提出了这样一个问题：任意六个人中必有三个 人互相认识或互不认识这个问题据称为融e y 问题对该问题的讨论导致了r a m s e y 定理、胁t s e y 数、砌m 8 e y 图、扩展一s e y 定理以及一些深层次的数学问题图的 孪群：关于一些图的r 眦s e y 数 舶潞e y 理论近几十年来已经发展成为m u n s e y 理论的一个非常活跃的领域早期发展图 的r 舡n s e y 理论的主要动机是希望它能产生解决经典r a m s e y 数的一些较大值的方法尽 管这个期望就像数学中经常发生的一样未能实现，但这个领域却发展成为一个独立的方 向而且与经典胁m e y 数的值相比，由图的r a m s e y 理论产生的结果更具有价值和意义 1 2 图论的基本概念 一个图是由非空点集y = v ( g ) 和y 中元素的无序对的一个集合e = e ( g ) 所构成 的二元组，记为g = ( y ( g ) ，e ( g ) ) ，简记为g = ( k e ) ，矿中的元素称为顶点或者点，e 中的元素称为边我们用m ( g ) = lei 表示图g 中的边数，用n ( g ) ) = iyi 表示图的顶点 个数，个图的顶点个数又称图的阶；在不引起混淆的情况下简记为m ，n 对虬 y ( g ) ， 若u 曰( g ) ，则称u 与口邻接，否则称不邻接，记为u ”蓝e ( g ) 若边e 1 ，e 2 e ( g ) 有一 个公共顶点，则称e - 与e 2 相邻 如果一个图的g 的顶点集v ( g ) 与边集f ( g ) 都是有限集，则称该图为有限图，否 则，称为无限图本文仅讨论有限图只有一个顶点所构成的图称为平凡图，其它所有 的图称为非平凡图显然，至少有一个顶点才能称为图所以我们总要求一个图的顶点 集合是非空的 一条边的两个端点如果相同，称此边为环两个点之间多于一条边的，称为多重边 不含环和多重边的图称为简单图，含有多重边图称为多重图没有环及多重边的图称为 简单图 以点 y ( g ) 为端点的边数叫做点”的顶点度，记作d g ( ”) ，无混淆情况下简记为 d ( ”) 或d l l 顶点度为d 的顶点称为d 度点，零度点称为孤立点，1 度点称为悬挂点，连 接悬挂点的边称为悬挂边用( g ) 和j ( g ) 分别表示图g 的最大和最小顶点度，简记为 和6 若y ( g ) = 口l ，观， ，称非负整数序列 d ( ”1 ) ，d ( 2 ) ，d ( ”。) 为图g 的度 序列 每一对顶点间都有边相连的无向简单图称为完全图，有n 个顶点的无向完全图记作 坼。图g 称为二部图或者偶图，如果点集v 可以分成两个非空子集x ，y ，即x u y = y 且 x n y = d ，使得e 中每条边的一个端点属于x ，另一个端点属于y 二部图g 称为完全 图，若对任意u x ，”y ，都有伽e 若完全二部图的两个部分有jx s ，iyi = t ， 则记作恐_ f 当其中的一部分，不妨设x 只含有一个点时，我们称为星，记作虬。其 中度为t 的点称为星的中心 路r 是指点集为y ( r ) = 1 ，”2 ，) ，边集为e ( r ) = ”1 2 ，一1 ) 的图， 或称为路( ，) ，或一路，n l 是路的长度起点和终点重合的道路叫圈。 长度为的圈称为一圈；为偶数，称偶圈；女为奇数，称奇圈；3 - 圈常称为三角形 n 个顶点的圈记作g 轮图- = 扣 + c k 是有m + 1 个点的图，即点。与圈c k 的所 有点邻接构成的图，点。称为轮w ，m 的中心 g 中点“与”称为连通的，如果在g 中存在u 一”路若g 中任意两点连通，则g 弥为连通图，否则称g 不连通没有圈的图我们称为森林，记作f ；没有圈的连通图称 为树，我们记作t 树中度为1 的顶点称为树的叶子。 2 大连理工大学硕士学位论文 图口称为g 的子图，如果y ( h ) g y ( g ) ，e ( 日) e ( g ) ；若日包含g 的所有的点， 则称日为g 的支撑子图；当日是森林时，我们称为支撑森林；当日是树时，我们称为 支撑树对集合x 矿( g ) ，导出子图 或g x 是以x 为点集的g 的最大子图 图g 1 = ( ，e 1 ) 和g 2 = m ，玩) 的并是图g = ( ku ，e 1u 岛) ，记作：g 1ug 2 设矿是图g = ( ke ) 的顶点集的一个非空子集，以y 作为顶点集，以两个端均在 y 。中的边的全体为边集的子图，称为由导出的g 的子图，记为g y ，我们说，g 7 是g 的导出子图 在g 中顶点的连通关系下，可将y ( g ) 划分成有限个等价类，其中每一个等价类构 成的g 的子图称为g 的一个连通分支，g 的连通分支数目记为u ( g ) ，可见g 为连通图 当且仅当u ( g ) = 1 若在图g 中去掉一个点后图的连通分支数增加，则称该点为g 的割 点 设百是以y ( g ) 为顶点的图，若召中两点在召中相邻当且仅当它们在g 中不相邻， 则称百为g 的补图 图g 1 与g 2 称为同构的，记作g 1 垒g 2 ，如果存在双射圣：y ( g 1 ) 一y ( g 2 ) ，是对 任意u ，”y ( g 1 ) ，u 口e ( g ) ，当且仅当西( 西( ”) e ( g 2 ) ，我们说图g 的一个复制指的 是与图g 同构的图 通过图g 的每个顶点的圈就称为哈密顿圈具有哈密顿圈的图就称为哈密顿图 用n 种颜色对图g 的顶点进行着色，且没有相异的邻接顶点着相同的颜色，则称为 g 的一个n 一顶点着色n 一顶点着色常简称为n 一着色使图g 为n 一着色的n 的最 小值称为g 的色数，记作爿( g ) 若z ( g ) = n ，则g 为n 一色的 本文所考虑的图均为无环、无重边的简单有限无向图文中的图论术语和记法主要 参考b o n d y 和m u r t y 的著作g r 印ht h e o r yw i t ha p p h c a t i o n 8 【3 5 本文主要的工作包括以下几个方面： ( 1 ) 简要叙述了图r m s e y 数的发展，介绍了图论的基本概念和术语； ( 2 ) 由于星图的特殊性，星图对其它图的r a m s e y 得到了广泛的关注第二章中研究 的是星对轮的r 1 s e y 数在本章中先给出并证明了关于图的r a m s e y 数的一些结果然 后利用文献【2 6 和 3 2 】介绍并讨论了星对轮的一些结果 ( 3 ) 路径也是一类特殊的图许多数学工作者都对关于路径或轮的r a m s e y 数进行了 研究f a u d r e ee ta 1 考虑了所有路径对圈的r a m 8 e y 数s u r a h m a te ta j 得到了路径对 或w ，5 的r ：l s e y 数陈耀军从更一般的情况考虑了路径对轮的胁e y 数并给出了下面 的结果：蜀r ，i ) = 3 n 一2 ，对奇数m 且n m 一1 兰2 ；r ( r ，矸，m ) = 2 n 一1 ，对偶数m 且”m 一1 3 因此在第三章第二节中我们就给出了路径对轮在其他情况下的结果： r ( r ，) = 当= 1 且m 3 时 当n = 2 且m 3 或n = 3 且偶数m 4 时 当n = 3 且奇数m 5 时 当m = n = 3 或n 兰4 ，m 为奇数且1sm 2 n 一1 时 当n 4 且偶数m 有4 m sn + 1 时 3 l 2 2 1 + + 一 一 m m 轨轨 ，fii_i，-，、ii_i_lli 奎登：薹王二些围塑曼璺婴型墼 以及这样一个边界若26 ，m 为偶数且n + 2 ms2 竹一4 ) 或为偶数， n 芝4 m = 2 n 一2 或m 2 n ) ，贝0 m + 警冽r ，) 2 “薯胪1 m m + 高 ) ( 4 ) 星和路径都是特殊的树，因此在第四章中我们来研究一下树对轮的胁- s e y 数 e t b 8 s k o r o 给出了树对髓或w ，5 的r a s e y 数：五( ，) = 2 稚一1 ，其中n 4 ； 配( 兀，) = 3 扎一2 ，其中n 5 所以e ，t b a s k o r 0 猜想了下面的结果当n m 7 且m 为 奇数时，兄( ，i ) = 3 n 一2 在第四章第二节中我们就证明了当m 为奇数且m 7 时， r ( ，) = 3 扎一2 ，其中凡= m ，m + 1 ，m + 2 4 大连理工大学硕士学位论文 2 星对轮的r 舢1 s e y 数 本章主要介绍一种特殊的树图星图对轮的s e y 数因为星图是一类非常特殊 的树图，所以关于星对轮的m s e y 数的研究已经有许多的可供参考的文献在这些文献 中就给出了许多关于星对轮的m s e y 数的完美的结果我们先引入图的r m s e y 理论中 的一个重要的定理以及由它推导出来的一些很好的结论；然后我们又介绍了关于星对轮 的胁1 8 e y 数的一些结果 2 1图的r 砌s e y 数的一些结果 在这部分中，我们将要引入一个在以后证明中经常用到的定理以及它的一些重要的 结论这个定理是c h v a t a j 和h a r a u 在1 9 7 2 年得出来的，其叙述如下 引理2 1 1 i 3 6 】对一个没有孤立点的圈g ，有 r ( g ，日) ( z ( g ) 一1 ) ( c ( 日) 一1 ) + 1( 2 1 ) 在这里z ( g ) 表示图g 的色数，c ( ) 表示图日的最大连通分支的顶点的数目 证明：设m = ( g ) 一1 ) ( c ( 日) 一1 ) 十1 ，把均。的边看作是把( ( g ) 一1 ) 个不同虬旧卜1 的 拷贝图的点连接得到的从而给图墨。的边着色可以看作是给( g ) 一1 ) 个图噩一， 的拷贝图的所有边用颜色2 着色，而所有剩余的边( 即不同的甄一1 交叉连接的边) 用 颜色1 着色很明显，不存在g 的用颜色1 着色的拷贝图否则我们就用( 疋( g ) 一1 ) 种 颜色给图g 的拷贝图着色，与一，相对应，这就与z ( 回的定义矛盾另一方面，也 不存在h 的用颜色2 着色的拷贝图，这是因为墨。中用颜色2 着色的最大的连通分支有 c ( 日) 一1 个点 c h v a t 8 】在1 9 7 7 年利用定理2 1 l 得出了图的r 自s e y 理论中被认为是最完美的结果 之一，即下面的定理 定理2 1 2 【2 3 】对有m 个点的任意树丁k ，有 证明：由定理2 1 1 知， 下面只需要证明 r ( 2 1 m ，j 矗) = ( m 一1 ) m 一1 ) 十l r ( ，) ( m 1 ) ( n 一1 ) + l 5 f 2 2 1 李群：关于一些图的r s e y 数 r ( 2 m ，k n ) ( m 一1j ( 凡一1 ) + 1 ( 23 ) 对于m = 2 或n = 2 ，( 2 3 ) 式显然是成立的假设( 2 3 ) 式对于m7 + n7 m + n 时，( 2 3 ) 式是成立的，其中m 7 ，n 是任取的考虑用红和蓝两种颜色着色一个二色图嘶。_ 1 ) ( ，1 ) + 1 设树丁是从树r 中去掉某个端点。( 这里z 是与树r 中的g 邻接的) 而得到的树由归 纳假设，二色图k f 。一1 ) ( 。1 1 + 1 要么包含蓝图作为一个子图，要么包含红图作为一 个子图因此我们可以假设红图r 是包含在二色图k f 。_ 1 1 卜1 、+ 1 中的一个子图所以 我们去掉这个红图t 中的m 一1 时，就剩余这样一个二色图k ( 。一1 ) ( 。一2 ) + 1 再由归纳假 设，二色图陋一1 1 f 。一2 ) + 1 要么包含蓝图甄一1 作为一个子图，要么包含红图r 作为一个 子图那我们就假设二色图k i 。- 1 ) ( 。一2 1 + 1 包含蓝图玛。】作为一个子图，结果，在个二色 图k f 一，) f 。一1 ) + 1 就有不相交的红图r 和蓝图_ 】最后我们再看一下点与蓝图珞一】 中的点邻接的所有的边的情况若这些边中的任一条都是红色的，则我们就得到一个红 图r ；若所有边都是蓝色的，则我们就得到一个蓝图玛。这就完成了归纳的步骤和定理 的证明 把定理2 1 2 稍微推广一下，我们就会的下面的结果这个结果是定理2 1 1 的个 特殊情况 定理2 1 3 4 】若g 是有n 个点的连通图，则 五( 凰，g ) 一1 ) ( 几一1 ) + 1 这个定理的证明由定理2 1 1 可以直接得出 下面这几个定理因为证明方法与定理2 1 2 基本相同，而且得到的结果也包含了定理 2 1 2 的结果，所以就被认为是定理2 1 2 的最基本的推广开始之前我们先引入一个关于 k g o o d n e s s 的基本引理和一个定理 引理2 1 4 【1 。】对于有n 个点的任意连通图g ，有 r ( 凰，回r ( 甄一1 ，g ) + n 一1 我们立刻就会的得到下面的定理 定义2 1 1 若图f 不包含g 且f 不包含日，则称f 是( g ，口) 一目0 0 d 图有n 个点的任意 ( g ，h ) 一9 0 0 d 图都可称为( g ，日，n ) 一9 0 d d 图 定理2 1 5 【1 若g 是k 9 0 0 d 的，则其也是( k _ 1 ) 一g o o d 的 现在回想一下自由边的定义，我们知道自由边是指一条与悬挂点相关联的边因此， 对一个图增加每一条自由边就表示增加一个点和该点与该图的某一点相关联的一条边 定理2 1 刚设图g 是有礼一1 个点的连通图，g 1 是g 增加一条自由边后的图，则 r ( k k ，g 1 ) = m a x 【r ( k ，g ) ，r ( k k 一1 ，g 1 ) + 札一1 3 证明：设m a x 限( 虬，g ) ，r ( 甄一1 ，g 1 ) + n 一1 = s 先证明r ( 凰，g 1 ) s 由引理2 1 4 ，显然有 r ( k k ，g 1 ) 2r ( k ，g ) 6 大连理工大学硕士学位论文 和 丑( f “，g ) r ( f “一1 ，g 1 ) 十n l 因此得到， r ( j 靠，g 】) s 下面再证明r ( 甄，g 1 ) ss 我们先考虑一个二色图如果我们已经有了红色甄，那我们就可以假设有一个蓝 图g 设”是图g 的一个点，使得在”点增加一条蓝色的自由边，就会得到蓝图g ，点 ”与非图g 中的点相连接后得到的图就认为是红色的但是s 一( n 一1 ) 2r ( 凰一1 ，g ，) 个 点仍在g 外，并且要么红图凰一l ，要么蓝图g ，就是我们要找的图，因此 r ( 尥，g 1 ) s 即 r ( 玩，g 1 ) = s 证毕 定理2 1 7 【1 】设g 是连通图，岛是对g 连续增加n 条自由边的图，则若n 足够大，g 礼 是k 9 0 0 d 的 利用定理2 1 6 就可以推导出下面的公式 r ( k k ，g n ) = m a x 【r ( 凤，g ) r ( 凤一1 ，g ) + 札一1 ，一，r ( 蚝，g ) + 一3 ) m 一1 ) ，( 七一1 ) ( 札一1 ) 1 推论2 1 8 对2 + 1 有 r ( & ，w 2 十1 ) 2 一2 这个不等式可以壹接由引理2 1 1 以及事实z ( 矸+ 1 ) = 4 和c ( 晶) = n 得出 推论2 1 9 对n 2 有 r ( 晶，仰k ) 22 n 1 这个不等式可以直接由引理2 1 1 以及事实爿( ) = 3 和c ( ) = n 得出 引理2 1 1 0 【3 q 对n 3 ，有n 个顶点的且最小度数6 ( g ) 2 的每个图g 都有一个哈密顿 圈 证明过程在第四章给出 2 2 星对轮的r a m s e y 数的一些结果 本节中我们就开始来看一下星对轮的r a h l s e y 数的一些结果在 1 0 1 中s u r a h m a te t 出已经证明了当n 2 m 一4 时，舶皿s e y 数r ( & ，m ) = 3 n 一2 ，这里m 5 ；在 5 中证 明了当n 为奇数且n 3 时，弛s e y 数r ( & ，瞰) = 2 n 一1 ，当n 为偶数且n24 时， r a m s e y 数r ( ，w - ) = 2 + 1 ；对每一个n 3 ，m s e y 数r ( s n ，矸，5 ) = 3 n 一2 本节主要是 证明当= m ，m + 1 ，m + 2 时，r ：l s e y 数r ( 晶，仉，m ) = 3 n 一2 ，这里m 是奇数且m 7 ；此 外，也给了一个如下的下界：对所有的n m 6 ，r ( 岛，职。) = 2 n + 1 ，这里m 为偶数 7 李群：关于一些图的r a i l l s e y 数 2 2 1r ( 晶，m 。) = 3 n 一2 ，n 为奇数 定理22 1 1 对n 23 有 r ( k + 1 ，w j 七十1 ) = 6 七+ 1 证明由推论2 1 8 就得到 r ( 岛k + l ，i k + i ) 3 ( 2 + 1 ) 一2 = 6 + 1 因此我们只需要证明r ( s 2 + 1 ，仰l k + 1 ) 6 + 1 即可 显然要用反证法来证明设f 是一个有6 + 1 个顶点的任意图我们就假设w 2 k + 1 f 且岛k + 1 仁f 则对所有的点口y ( f ) ，都可以得到如( u ) 6 a 一( 2 一1 ) = 4 + 1 因为f 中 顶点的数目是奇数，所以图f 中并不是所有顶点的度数都为奇数；因此，至少是存在一点 。y ( ，) ，使得如( o ) 6 七一( 2 一1 ) = 4 + 1 设a 是m ，f n ( 。) 的一个子集，且有川= 4 十2 设_ p = v ( f ) 一。一a ，则l p l = v ( f 卜。一a l = i v ( f ) l 一1 一 a i = ( 6 凫+ 1 ) 一1 一( 4 + 2 ) = 2 k 一2 通过观察，我们可以知道对所有的点n a ，我们都有口j 4 ( o ) 如( o ) 一“p i 十1 ) ，因此 d ( a ) ( 4 昆+ 1 ) 一( 2 七一2 + 1 ) = 2 豇+ 2 ( 2 - 4 ) 由引理2 1 1 0 ，这个不等式就暗示着a 包含了一个具有4 女+ 2 个点的哈密顿圈爿 设。是a 中的任意一点，对a 中其它点的记数就要依赖于在哈密顿圈“上与点z 的位 置关系更详细地说，就是当从。开始沿某一方向绕圈运行时，设z ，。2 + 1 ，c 2 ，c 2 一1 7 一，c 1 ，c 0 就是依次经过的点；当从。开始沿另一方向绕圈运行时，设z ，6 0 ，6 l ，b 2 ，b _ l ，6 2 k + 1 就是依次经过的点所以就有c o = 6 2 一1 ，c 1 = 6 2 a n dc 2 = 6 驰+ 1 为证明定理2 2 1 1 ，我们先证明几个必要的观察结果 观察2 2 1 2 对所有的1s is2 k ，点。至多与q 和b 中的一个邻接 证明若不然，我们就假设对某个i ，点z 与q 和k 都邻接则就有 z ，6 ，6 + 1 ，6 t + 2 ，一，6 2 一l ，c 1 ，c 2 ，一，龟 构成一个圈c 更准确地说，它是一个有2 k + 1 个顶点的圈把圈c 和点d 连接，就得到 一个轮七+ 1 包含在f 中这个结论w ，2 k + 1cf 就与我们前面的假设w j i 十1 f 矛盾 所以点g 至多与q 和6 。中的一个邻接 观察2 2 1 3 点z 与点c 0 = 一l 不邻接 证明若不然，把点z ，6 0 ，b 1 ，6 2 ，6 2 b 一1 构成的圈与点。连接就得到轮w j k + lcf 这个 结论k + 1 f 也与我们前面的假设 厂2 + l 正f 矛盾 观察2 2 1 4 点z 与点c 2 = 6 2 k + 1 不邻接 证明与观察4 2 7 的证明过程类似 观察2 2 1 5 点。与点6 2 和c 2 k l 都邻接 8 大连理工大学硕士学位论文 证明反证法假设点。至多与点6 2 和c 2 一l 中的一个邻接，则由观察2 21 2 2 2 14 就 有 2 k 一1 9 _ ( z ) = ( 口“，c l ( 。) ) + p ，。，唧。+ ，( z ) = l 2 七一2 = ( ed b 卯。( z ) + z 岵，舟扛) ) + 口b t ，( z ) + d 幻。一，c 2 。一，( 。) + 2 ) 6 0 ，吃。，。 + ，( z ) ( 2 七一3 ) + 口b 。，c 2 ) + d b 。一，向。一， ) + 3 2 血+ 2 ) 6 2 恕( z ) + 口k k 一1 ，c 2 k 一1 扣) 2 的情况 设f 是一个有6 一3 个顶点的任意图我们假设h 仁f 且s 2 t 仁芦则对所有的 点u y ( f ) ，都可以得到 d f ( ) ( 6 七一4 ) 一( 2 七一2 ) = 4 血一2 设。是f 的任意一点，a 是眠，f n ( o ) 的一个子集使得h = 戡一2 ，令p = y ( f ) 因此旧= 2 一2 通过观察，知道对所有的点n a ，我们都有口a ( 。) 如( n ) 一( 吲十1 ) ，因此 f 25 1 o 一4 口a ( ) ( 4 七一2 ) 一( 2 七一2 + 1 ) = 2 南一1( 2 6 ) 由上一节的引理2 1 1 0 知，a 包含了一个具有4 一2 个点的哈密顿圈h 设z 是a 中的任意一点，对4 中其它点的记数就要依赖于在哈密顿圈m 上与点z 的位 置关系更详细地说，就是当从z 开始沿某一方向绕圈运行时，设。，吼咄c 2 墙c 2 k 一3 ，c 1 ，印 就是依次经过的点；当从。开始沿另一方向绕圈运行时，设。，6 0 ，6 1 6 2 ，6 2 一3 ，6 2 k 一2 就 是依次经过的点且有c 0 = 6 2 k 廿 在证明该引理之前也需要证实一些必要的观察结果，这些结果的证明与前面类似， 所以在这里就不再重复了 观察2 2 2 3 对所有的1 t 2 一3 ，点至多与臼和b i 中的一个邻接 观察2 2 2 4 点z 与点c 0 = 6 2 女一2 不邻接 观察2 2 2 5 对所有的1 s2 一3 ，点z 恰正好与q 和如中的一个邻接 证明若对1 冬t52 一3 中的某个 ，点。与6 i 和q 都不邻接，则由观察2 2 2 3 和2 2 2 4 ， 有 2 一3 d 扛) = ( d b ，白( z ) ) + 口沁 c 2 。一：( 王) + d b 。一。扛) j = l ( 2 七一4 ) + 2 + 0 = 2 七一2 这就与不等式( 2 6 ) 矛盾 现在再继续引理2 2 2 2 的证明设0 1 ，“2 ，0 4 k 一2 是a 中的点且按顺序构成哈密顿 圈“设当i ij ( m o d 4 一2 ) 时，；和哟就代表同一个点由观察2 2 2 5 知，对所有的 j ，点o j 就正好与。件 和o ，一 中的一个邻接 特别地，n k + 1 正好与n 1 和n 2 k + l 中的一个邻接 假设。k + 1 与n l 邻接，因此就不与0 2 k + 1 邻接则0 2 h 1 一定与口3 + l 邻接且 是有2 个点的圈 另一方面，假设n k + l 与。2 + l 邻接，因此就不与n i 邻接则o l 一定与n 3 一l 邻接且 0 1 ，0 2 ，。，0 + 1 ，0 2 + 1 ，n 2 k + 2 ，0 3 k 一2 1 0 3 七一1 1 0 大连理工大学硕士学位论文 是有2 个点的圈 在这两种情况中，得到的有2 个点的圈就构成轮u cf 的边，o 就是它的中心 这就正好与我们的假设w 仁f 矛盾证毕， 现在开始定理2 2 2 1 的证明 证明由推论2 1 8 就得到 r ( s 2 + 2 ，- k + 1 ) 3 ( 2 + 2 ) 一2 = 6 七十4 因此我们只需要证明r ( 是k + 2 ，w 靠+ 1 ) 6 + 4 即可 设f 是一个有6 + 4 个顶点的任意图我们假设w ，2 * + 1 仁f 且岛k + 2 仁f 则对所 有的点u y ( f ) ，都可以得到如( ) ( 6 + 3 ) 一2 = 4 + 3 由引理2 2 2 2 知，有 r ( s 2 女+ 2 ，w ，2 + 2 ) s6 七+ 3 由前面的假设岛女+ 2 茌，则有 + 2 f 设。是f 中的一个点，恰好也是轮w + 2 的中 心，z = 卸，z 2 ，砘k + 2 ) 是f 的点集，它按顺序构成轮w ，2 k + 3 的边当iij m o d ( 2 + 2 ) 时，令和卸就代表同一个点 因为如( ) 4 + 3 ，因此存在y ( f ) 的一个子集a = n 1 ，2 ，啦k + 1 使得对所有 的t 和j ，都有a t z ，且对所有的i ，毗都与。邻接在这里我们选择且使得川= 2 女+ 1 在证明定理2 ，2 2 1 之前，我们先证明一些必要的观察结果 观察2 ，2 26 对所有的t ，若1 。2 + 1 ，则点至多与点盈和2 t + 3 中的一个邻接 观察2 2 2 7 对所有的 a ， d z ( ) 七+ 1 证明设”是a 中任意一点，下面就分三种情况进行讨论 情况1 若3 旧记= 3 0 ，因此吲= 2 + 2 = 6 。+ 2 现在考虑这样定义的一个序列 ( ) ，这里s 1 = 1 ，鼠+ 1is + 3 m o d ( 6 n + 2 ) 很明显，这个序列是周期性的并且周期是 6 n + 2 ；事实上也的确如此，该序列如下： 1 ，4 ，7 ，一，6 + l ，2 ，5 ，一，6 0 + 2 ，3 ，6 ，- ，6 ，l 由观察2 2 2 6 可知，对所有的t ，点”至多与z 函和勰+ ，中的一个邻接因此，点 至多与z 中【学】个点邻接又因为 学】= 3 n + l = + 1 ，所以对所有的点u a ，都有 d z