第三节 Ransey问题与Ransey数.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,1.3,R,amsey,问题与R,amsey,数,组合数学,Chapter,1,Contents,一、,R,amsey,问题,完全图的染色问题,二、,R,amsey,数,一、R,amsey,问题,完全图的染色问题,著名的,Ramsey,问题：,问题,1:,1958,年,6,7,月号美国,数学月刊,上登载着这样一个有趣的问题：“任何,6,个人的聚会，其中总会有,3,人互相认识或互相不认识,.”,问题,2:1959,年美国,数学月刊,第,2,期又进一步提出：“任何,18,个人的聚会，其中总会有,4,人互相认识或互相不认识,.”,转化为完全图的染色问题来解决,.,定义 有,n,个顶点且每两个顶点都有一条边的简单图称为,n,阶完全图，记为,K,n,.,于是,R,amsey,问题,1,为下面的定理,1.,定理,1,对,6,阶完全图,K,6,的边任意涂红、蓝两色,则必存在一个红色三角形或一个蓝色三角形,.,证明 设 是,K,6,的,6,个顶点,所连的,5,条边着红色或蓝色，由鸽巢原理知，其中至少有,3,条边同色,.,不妨设 所连的,3,条边均为红色,如图所示,若 间有一条红边,不妨设为 ，,则 是一红色三角形,.,否则，,间均为蓝边,即 是一蓝色三角形,.,显然,当 时,把,K,6,换成,K,n,定理的结论显然仍成立,.,但当,n,=5,时,定理的结论就不一定成立了,.,例如对下图所示的 实边涂红色,虚边涂蓝色,既无红色的三角形，也无蓝色的三角形,所以,6,为结论成立的最小数,.,这个最小数称为,Ramsey,数,记为,N(3,3;2),，即,N(3,3;2)=6.,定理,1,我们还可叙述为：,S,为,n,元集合,当,n,6,时,把,S,的所有,2,元子集放入两个盒子,则或者有,3,个元素其所有,2,元子集全在第一个盒子里，或者有,3,个元素其所有,2,元子集全在第二个盒子里,定理,2,对,9,阶完全图,K,9,的边任意涂红、蓝两色，则必存在一个红色,(,蓝色,),的,K,4,或者必存在一个蓝色,(,红色,),的,K,3,.,为了证明定理,2,先证下面的引理,引理 对,9,阶完全图,K,9,的边任意涂红、蓝两色,则必存在一个顶点,从这点引出的,8,条线段中,红色（蓝色）线段或多于,3,条或少于,3,条,证明 用反证法,如果不存在这样的顶点,即从每一顶点发出的线段中,红色（蓝色）线段都是三条,.,现在对,9,个顶点逐点统计由它们发出的红色（蓝色）线段的条数,应为,27,条,另一方面，若设,K,9,中实有红色（蓝色）线段总数为,m,条,现对这,m,条边的端点逐点统计由它们发出的红色线段的条数，,由于每条线段有,两个端点,故应有,2,m,条,由此得出,2,m,=27,这是不可能的,故引理得证,证明定理,2:,设 是构成,K,9,的,9,个顶点,由引理其中必有一点,不妨设为 ，,从这一点引出的,8,条线段中,蓝色线段或多于,3,条，,或少于,3,条,.,对这两种情况分别讨论如下：,(1),从,v,0,引出的,8,条线段中,蓝色线段多于,3,条,即至少有,4,条，,不妨设 为蓝色线段,点所构成的完全图,K,4,，,若这个,K,4,中没有一条线段是蓝,色的,则,再看由,四个,这个,K,4,就是一个红色的完全四边形,.,若这个,K,4,至少有一条蓝边,则它的两个端点连同,v,0,便构成一个蓝色三角形；,即结论成立,定理,2,对,9,阶完全图,K,9,的边任意涂红、蓝两色，则必存在一个红色,(,蓝色,),的,K,4,或者必存在一个蓝色,(,红色,),的,K,3,.,(2),从,v,0,引出的,8,条线段中,蓝色线段少于,3,条，即至多有,2,条,这时,从,v,0,引出的红色线段就会至少有,6,条，不妨设为,再看由 这,6,个点构成的,K,6,，,由定理,1,可知,这个,K,6,必有一个同色三角形,.,若是红色的,则这个红色三角形,的顶点连同,v,0,一起便构成一个红色的完全四边形,K,4,.,即结论成立,综合以上两种情况，定理,2,得证,若是蓝色的,这个三角形即为蓝色的,K,3,.,显然,当 时,把,K,9,换成,K,n,定理的结论显然仍成立,.,但当,n,=8,时,定理的结论就不一定成立了,.,例如对下图所示的 实边涂红色,虚边涂蓝色,既无红色的完全四边形，也无蓝色的三角形,所以,9,为结论成立的最小数,.,这个最小数称为,Ramsey,数,记为,N(3,4;2),，即,N(3,4;2)=9.,定理,2,我们还可叙述为：,S,为,n,元集合,当,n,9,时,把,S,的所有,2,元子集放入两个盒子,则或者有,3,个元素其所有,2,元子集全在第一个盒子里，或者有,4,个元素其所有,2,元子集全在第二个盒子里,R,amsey,问题,2,为下面的定理,3.,定理,3,对,18,阶完全图,K,18,的边任涂红、蓝两色,则必存在一个红色的,K,4,或者存在一个蓝色的,K,4,.,证明 设 是,K,18,的,18,个顶点，现考察,K,18,中,从,v,0,出发的,17,条线段,它们分成了红、蓝两类,由鸽巢原理知,至少有,9,条是同色的，,不妨设它们是红色,.,考察这,9,条红色线段,异于,v,0,的,9,个端点所构成的,K,9,，,由定理,2,知,K,9,中必存在一个红色,三角形,K,3,或一个蓝色完全四边形,K,4,.,若是后者，则命题得证；,若是前者,则这个红色三角形的三个顶点和,v,0,便构成一个红色的完全四边形,.,所以,定理成立,.,显然,当 时,把,K,18,换成,K,n,定理的结论显然仍成立,.,但当,n,=17,时,定理的结论就不一定成立了,.,例如把,K,17,的,17,个顶点记为,在把数字,1,2,16,分为,A,B,两组,按以下规则对,K,17,的边进行涂色：,涂红色；,涂蓝色；,这样涂得的,K,17,即不存在红色,K,4,的也不存在蓝色的,K,4,所以,n,=18,是定理结,论成立的最小数,.,这个数记为,这个数记为 ,定理,3,我们还可叙述为：,S,为,n,元集合,当,n,18,时,把,S,的所有,2,元子集放入两个盒子,则或者有,4,个元素其所有,2,元子集全在第一个盒子里，或者有,4,个元素其所有,2,元子集全在第二个盒子里,当,n,=?,时,对完全图,K,n,的边任涂红、蓝两色,则必存在一个红色的,K,5,或者存在一个蓝色的,K,5,.,目前已证得,43,n,49.,当,n,=?,时,对完全图,K,n,的边任涂红、蓝两色,则必存在一个红色的,K,6,或者存在一个蓝色的,K,6,.,目前已证得,102,n,165.,二、R,amsey,数,关于完全图的两种颜色的染色问题，可归纳出如下的一般情况：,对于任意给定的两个正整数,a,和,b,，存在,最小的正整数,N,(,a,b,;2),使得当,对,K,m,的边任意涂于,红、,蓝两色,K,m,中必存在红色的,K,a,或蓝色,K,b,.,我们把,N,(,a,b,;2),称为,Ramsey,数,.,简记为,r,(,a,b,).,由上面的定理可知,:,S,为,n,元集合,对于任意给定的两个正整数,a,和,b,，存在最小的正整数,N,(,a,b,;2),当,n,N,(,a,b,;2),时,把,S,的所有,2,元子集放入两个盒子,则或者有,a,个元素其所有,2,元子集全在第一个盒子里，或者有,b,个元素其所有,2,元子集全在第二个盒子里,Ramsey,于,1928,年已经证明了对于任给的整数,a,和,b,Ramsey,数 的存在性,.,但是,Ramsey,数的确定却是一个非常难的问题,以致于至今知道的还极少,.,(,见,P,17,表,.,),虽然 难以确定，但关于它具有以下的一些性质,性质,1,为,Ramsey,数，则有,性质,2,对任意的正整数,有,证明 令,下面只要证明对,K,N,的边任着红、蓝两色，必存在红色的,K,a,或,蓝色的,K,b,.,设,x,为,K,N,的一个顶点，与,x,关,联的边有,N,-1,条，对这些,边,任意着红、蓝两色,由鸽巢原理,性质,2,对任意的正整数,有,1.,若至少有,r,(,a,-1,b,),条红边,.,这些红边与,x,相关联的,顶点有,r,(,a,-1,b,),个,在这些顶点构成的完全图 中,必有一个,红色,的,K,a,-1,或一个蓝色的,K,b,.,若为红色的,K,a,-1,则该红色的,K,a,-1,加上,顶点,x,及,x,与,K,a,-1,之间的红边,即构成一个红色的,K,a,;,否则，就有一个蓝色的,K,b,.,2.,若至少有,r,(,a,b-,1),条蓝边,.,这些蓝边与,x,相关联的顶点有,r,(,a,b-,1),个,在这些顶点构成的完全图 中,必有一 个,红色,的,K,a,或蓝色的,K,b,-1,.,若为前者结论成立,若为后者,则该蓝色的,的,K,b,-1,加上顶点,x,及关联的蓝边,即构成一个蓝色的,K,b,.,所以有,性质,3,对任意的正整数,当,都为偶数时,有,证明,考虑由,t,个点所构成的完全图,K,t,，将它的边涂以红、蓝两色,我们证明必定存在红色（蓝色）的,K,a,或,存在蓝色（红色）,K,b,为此,我们从,t,个点中选取一个点,v,0,它与其余,t,-1,个点所连成的,t,-1,条边中，一定出现有多于,2,m,-1,条红色边，或少于,2,m,-1,条红色边,因为否则从每一顶点引出的红色边都是,2,m,-1,条,这时从,t,个顶点引出的红色边将共,(,2,m,-1,)(2,m,+2,l,-1),有条,.,由于其中每条边有两个端点都被计算了两次,假设,k,t,中有,h,条红色边,于是便有,产生矛盾，所以从,v,0,引出的,t-1,条边中，一定出现有多于,2,m,-1,条红色边，或少于,2,m,-1,条红色边,对上面的两种情况分别讨论如下：,(1),从,v,0,点引出的,t,-1,条边中红色边多于,2,m,-1,条，即至少,有,2,m,条,我们考察由,2,m,条红色边所有异于,v,0,的端点构成的完全图,K,2,m,.,因为,所以,K,2,m,中必定存在红色的,K,a,-1,，或存在蓝色的,K,b,若为后者结论成立,若为前者,则红色的,K,a-,1,连同,v,0,一起便构成了红色的,K,a,结论也成立。,(2),从,v,0,点引出的,t,-1,条边中红色边少于,2,m,-1,条，即至多有,2,m-,2,条,于是蓝色边至少有,2,l,条，,我们考察由,2,l,条蓝色边所有异于,v,0,的端点构成的完全图,K,2,l,因为,所以,K,2,l,中必定存在红色的,K,a,，或存在蓝色的,K,b-,1,若为前者结论成立,若为后者,则蓝色的,K,b-,1,连同,v,0,一起便构成了蓝色的,K,b,结论也成立,所以有,性质,4,对任意的正整数,有,证明 对,a+b,进行归纳,.,当,a+b,5,时，有,a,=2,或,b,=2,由性质,1,结论成立,.,假设对一切满足,5,a+b,m+n,的,a,b,都成立，下面证明,a+b,=,m+n,时结论也成立,.,由归纳假设有,由归纳法，结论成立,.,世界各国的数学竞赛经常出现与,Ramsey,问题有关的题目,.,例,1,（波兰）平面上有,6,个点，任何,3,点都是一个不等边三角形的顶点，则这些三角形中，有一个三角形的最长边是另一个三角形的最短边,.,证明：以平面上这,6,个点构作完全图,K,6,并按如下方式用红、蓝二色对,K,6,的边着色：,对,K,6,的每个三角形的最短边都涂上红色，剩余的边再涂上蓝色,.,由定理,1,，此,K,6,中必有同色的三角形,.,由于该三角形的最短边,为红色,因此这个同色的三角形是红色的三角形,.,而这个三角,形的最长边为红色,按涂色方法知,必是另一个三角形的最短边,.,所以,有一个三角形的最长边是另一个三角形的最短边,.,1964,年第六届国际数学奥林匹克数学竟赛有这样一道试题：,有,17,名学生互相通信讨论,3,个问题，但每对学生间仅讨论其中一个问题，证明至少有,3,名学生间彼此讨论的是同一个问题,.,这个问题是前面,Ramsey,问题,1,问题,2,的推广，把它转化为图的染色问题，可得到下面定理：,定理,4,对,17,阶完全图,K,17,的边任涂红、蓝、黄三色，则必存在一个同色的三角形,.,证明 设 是,K,17,的,17,个顶点，现考察,K,17,中,从,v,0,出发的,16,条线段,当对它们涂于红、蓝、黄三色时,由鸽巢原理知至少有,6,条边是同色的，,不妨设,是红色边，,再看由 这,6,个点构成的,K,6,，,若这个,K,6,有一条红边，则它的两个端点连同,v,0,便构成一个红色三角形,结论成立；,若这个,K,6,没有一条红边，,则它的边,只能涂于蓝色和黄色，由定理,1,知它一定会出现一个蓝色的三角形，或一个黄色三角形，结论成立,所以定理得证,而且已经证明,n,=,17,是定理结论成立的最小数,为,Ramsey,数记为 ,定理,4,我们还可叙述为：,S,为,n,元集合,当,n,17,时,把,S,的所有,2,元子集放入三个盒子,则或者有,3,个元素其所有,2,元子集全在第一个盒子里，或者有,3,个元素其所有,2,元子集全在第二个盒子里，,或者有,3,个元素其所有,2,元子集全在第三个盒子里,.,当,n,=?,时,对完全图,K,n,的边任涂红、蓝、黄、绿四色,则必存在同色的三角形？,答案：,n,=65.,对,K,66,的边任涂红、蓝、黄、绿四色，必存在同色的三角形。（作业）,作业：,P,22,22,