组合数学(3)教材

中国余数定理是说明：一个整数x与两个互质的整数n,m相除，可以得到两种表示结果：

x=pm+a和x=qn+b，其中a和b

分别是小于除数m和n的余数，例如：19=9×2+1=3×5+4；其中m=2；n=5是互质而选择n=4的话：19=4×4+3=8×2+2=pm+2

只有一种表示形式。1

Ramsey问题可以看成是鸽巢原理的推广下面举例说明Ramsey问题。例1

6个人中至少存在３人相互认识或者相互不认识。证:这个问题与K6的边２着色存在同色三角形等价。假定用红蓝两种颜色对完全图K6着色。第二章鸽巢原理

2.2Ramsey定理2设K6的顶点集为{v1,v2,···,v6}，dr(v)表示与顶点v关联的红色边的条数，db(v)表示与v关联的蓝色边的条数。在K6

中，有：dr(v)＋db(v)＝５，由鸽巢原理将5条边分配成2种颜色，至少有：[(5-1)/2]+1=３条边同色。现将证明过程用判断树表示如下：v1v6v5v4v3v23dr(v1)≥3?db(v1)≥3设(v1v2)(v1v3)(v1v4)为红边设(v1v2)(v1v3)(v1v4)为蓝边△v2v3v4是红△?△v2v3v4是蓝△?设(v2v3)是蓝边设(v2v3)是红边△v1v2v3是蓝△△v1v2v3是红△√√YNNNYY

v6v5v4v3v2v14定理说明：六点够成的完全图中，用红、兰两种颜色对边涂色，总能得到一个红三角形或者是一个兰三角形，注意:6是染两色时出现同色三角形的最小点数。若取5点，则可举出反例(如P22图2.2所示)，图中就没有同色的三角形，即可使K5不存在同色三角形。v5v4v3v2v15

例29人行，或有3人互相认识，或有4人互不认识。例318人行，定有4人或互相认识，或互不认识。上述问题，可用图论的方法予以解决。即将n个人视为n个顶点（设n个顶点中任意3点不共线），并构造n点完全图Kn，对Kn中的边染6以红、蓝两种颜色，2人相识染红色，不相识染蓝色，最后求证图中必存在同色三角形，或同色完全四边形。例2证明第一步：若将K9染色，则其中必存在一点，从这点到其余8点的边中，同色者不等于3。设若不然，K9中每个点与其余8个顶点所成之边都是恰染3条红色（或蓝色），现从每个端点统计各7点引出的这些红色（或蓝色）边的总数应是3×9=27，但这是不可能的，因每条边关联两个端点，对这种统计，所有点引出的红色（或蓝色）连边的总数应为偶数。结论是，必存在一点，从该点到其余各点的边染红色（或蓝色）者一定大于3或小于3。第二步：（1）设从v1向其余8点引出的边中，染红色者多于3条，即至少有4条，不妨设为:8(v1,v2),(v1,v3),(v1,v4),(v1,v5)。再看v2,v3,v4,

v5

所成完全图K4，若有一红色边，则其两端点连同v1已构成红色三角形,否则全为蓝色，这时v2,v3,v4,

v5就构成一蓝色完全四边形。（2）设从v1向其余8点引出的边中，红色边少于3条，即至多有2条，这时从v1引出的蓝色边至少会有6条,不妨设为(v1,v2),(v1,v3),…,(v1,v7)。9再看v1,v2,v3,v4,v5,v6所成完全图K6，由定理1，其中若有红色三角形，则结论已真；若K6中有蓝色三角形，则其3个顶点连同v1即构成一蓝色完全四边形，结论亦真。由（1）及（2），定理得证。注意：当n＞9时，定理2自然成立。但当n=8时，可举出反例(如下图所示)，即可使其既无同色三角形，又无同色完全四边形。10K8二染色11

dr(v1)≥4?db(v1)≥6设(v1v2)(v1v3)(v1v4)(v1v5)是4红边设(v1v2)···(v1v7)是6条蓝边K4(v2v3v4v5)是蓝K4?K6(v2···v7)中有红△?设(v2v3)是红边△v1v2v3是红△设△v2v3v4是蓝△K4(v2v3v4v5)是蓝K4√√YYYNNN用判断树也可以进行证明如下12

∴K9的边红、蓝２两种着色，必有红色三角形或蓝色K4。同理可证K9的红、蓝２着色，必有蓝色三角形或红色K4。(红△∨蓝K4)∧(蓝△∨红K4)＝存在同色K4或红△及蓝△＝同色K4∨(红△∧

蓝△)两个同色三角形同色完全四边形13我们可以用下列形式表示Ramsey定理：

K6

K3,

K3

而K5

K3,

K3

更一般地，

Ramsey定理可叙述为：如果m≥2及n≥2是两个整数，则存在一个正整数p使得Kp

Km,

Kn

,这还不是最一般的形式。

如果Kp

Km,

Kn

,

那么对任何的q≥p成立

Kq

Km,

Kn

，则p是满足要求的最小数。14

Ramsey数，定义为:使得Kp

Km,

Kn成立的最小整数p,称为Ramsey数；记为：r(m,n)=p将上述的问题一般化：给定一对正整数m,n,存在一个最小的正整数p,对p个顶点的完全图的边任意红、蓝２着色，存在m个顶点的红边完全图或n个顶点的蓝边完全图。

Ramsey数是相对完全图Km,

Kn而定义的。

15Ramsey定理则断言了Ramsey数的存在性。例如我们已经证明了：r(3,3)=6等平凡Ramsey数r(2,n)=n和r(m,2)=m证明：假设1:r(2,n)≤n事实上，如果我们把Kn的边涂成红色或者蓝色，那么，或者Kn的某条边是红色(因此我们就得到一个红色的K2)

，或者Kn所有的边都是蓝色的(因此我们就得到一个蓝Kn)16这样我们就得到最小的Ramsey数为n；

假设2:r(2,n)＞n-1事实上，如果我们把Kn-1的边都涂成蓝色，那么，我们既得不到红K2，也得不到蓝Kn。

用类似的方法可以证明另一个平凡Ramsey数

r(m,2)=m一般地，可以交换红色和蓝色的位置得到：

r(m,n)=r(n,m)17例：在K4中，我们用红,蓝两种颜色涂色。要求要么其中一种颜色只涂一条边，例如用红色涂一条边，正好是红K2，要么另一种颜色涂所有的边，正好是蓝K4；

v3v2v4v1v3v2v4v118关于平凡Ramsey数r(m,n)的一些已知结论可列表如下：

r(3,3)=6；用两种颜色涂K6

能得到K3或K3

r(3,4)=r(4,3)=9;用两种颜色涂K9

能得到K3或K4r(3,5)=r(5,3)=14;用两种颜色涂K14

能得到K3或K5r(3,6)=r(6,3)=18;用两种颜色涂K18

能得到K3或K6r(3,7)=r(7,3)=23;用两种颜色涂K23

能得到K3或K719r(3,8)=r(8,3)=28;用两种颜色涂K28

能得到K3或K8r(3,9)=r(9,3)=36;用两种颜色涂K36

能得到K3或K940≤r(3,10)=r(10,3)≤43;r(4,4)=18;用两种颜色涂K18

能得到红K4或蓝K4r(4,5)=r(5,4)=25;用两种颜色涂K25

能得到K4或K543≤r(5,5)≤55;20

Ramsey定理还可以推广到任意多种颜色的情况，如果n1,n2,n3是大于2的三个整数，则存在一个整数p使得:

Kp

Kn1,

Kn2,

Kn3

记为：r(n1,n2,n3)=P就是说，如果Kp的每条边涂上红色、蓝色、或绿色，那么或者存在一个红Kn1或者存在一个蓝Kn2或者存在一个绿Kn3。21使得该结论成立的最小整数p,也称为Ramsey数；

例：若将K17的边染以红、蓝、黄三色，则一定会出现一个同色三角形。证明设V={v0,v1,…,v16}为K17的点集，任取一点v0，在v0与其余16点相连的边中，因染有三色，由鸽巢原理知至少有［16/3］+1=6条边染以同色。不妨设(v0,v1),(v0,v2),…,(v0,v6)这6条边染为红色。考察v1,v2,v3,v4v5,v6组成的完全图K6，分两种情况讨论:22

(1)如果该K6中有一条边为红色,设为(v1,v2),则v0,,v1,v2所成三角形已是同色三角形,定理得证；(2)如果该K6中没有红色边,即只染有黄、蓝两色，则由Ramsey定理这个K6中就有同色三角形,定理得证；特别地，定理中的17点恰是染三色时的最少点数，亦即K16用三色涂染时，可以构造一种图形，使得其中不存在同色三角形。23本结论也可以用判断树来证：证:设三色为r,b,g．则对K17的任一顶点v有dr(v)+db(v)+dg(v)=16；因［16/3］+1=6,故任一顶点与其他顶点的连线中，至少有６条同色．不妨设dr(v1)≥6,(v1v2),(v1v3),…,(v1v7)都是红边。从而可得如下判断树。24K6(v2···v7)中无红边?K6(v2···v7)中有红边K6(v2···v7)中蓝、绿２着色有蓝K3或绿K3设(v2v3)为红边△v1v2v3是红色的原题得证．YN25

若进一步将用两种、三种颜色扩展到用任意有限种颜色涂染完全图的边，则有:

一种颜色：

r(m)=3，两种颜色r(m,n)=6，

三种颜色r(n1,n2,n3)=17；

也有人证明了r(n1,n2,n3

,n4)=65。找出r的准确值是件困难的事情，目前仅知道以上几种。26

Ramsey数的性质：

定理：当a,b≥２时，有r(a,b)≤r(a－1,b)＋r(a,b－1)成立

证：对r(a－1,b)＋r(a,b－1)

个顶点的完全图红蓝２着色．任取其中一点v，有dr(v)+db(v)=r(a－1,b)+r(a,b－1)－1从而可得判断树如下．27

dr(v)≥r(a－1,b)?db(v)≥r(a,b－1)与v以红边相连的r(a－1,b)个顶点的完全图中有一个红Ka－1?有蓝Kb红Ka或蓝Kbv与这a－1个点构成红KaNYYN28推论r(a,b)≤(

)a+b－2a－1证：r(a,b)≤r(a－1,b)＋r(a,b－1)

≤()＋()

＝(

)a+b－2a－1a+b－3a－2a+b－3a－129定理若a≥３，则r(a,a)>2a2证：Kn有()条边，对边红蓝２着色有2种方案．其中同色K