拉姆齐数

函数术语

拉姆齐数(Ramsey number)是图论的重要函数之一，它是一个以两个正整数作为变量的函数。拉姆齐数是拉姆齐定理的重要参数。

简介

拉姆齐数(Ramsey number)是图论的重要函数之一。它是一个以两个正整数作为变量的函数。设m和n为正整数。所谓拉姆齐数，常用r(m ,n)表示，是指符合一定条件的p(图的阶数)的最小值。任何一个p阶的图G，若不含完全图Km作为一个子图，则必有一个含n个节点的独立集。一个(m,n)拉姆齐图是指阶为r(m,n)-1，既不含m个节点的完全图作为子图，也不含n个节点的独立集的图。设k1,k2,...,kq是q个正整数，所谓广义拉姆齐数r(k1,k2,.. ,kq)，是指符合下列条件的p的最小值：对于p阶完全图Kp，用q种色(cl,c2,...cq)对Kp的边任意着色，则存在某一色ci，所有着这一种色的边的导出子图包含Kki作为一子图。对于正整数m,n，所谓边拉姆齐数rl(m,n)，就是指符合如下条件的p的最小值：对于任何一个p阶的图，其上必有m条边两两互不相邻，或有n条边以同一节点为端点。关于r(m,n)的存在性，是由拉姆齐(Ramsey , F. P.)首先给出的。

图论

图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认V∩B=Ø。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。

定义

拉姆齐数，用图论的语言有两种描述：

对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；

在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn[e2]中含有一个k边形，Kn[e1]含有一个l边形，则称满足这个条件的最小的n为一个拉姆齐数。（注意：Ki按照图论的记法表示i阶完全图）

拉姆齐证明，对与给定的正整数数k及l，R(k,l)的答案是唯一和有限的。

拉姆齐数亦可推广到多于两个数：

对于完全图Kn的每条边都任意涂上r种颜色之一，分别记为 e1,e2,e3,...,er ，在Kn中，必定有个颜色为e1的l1边形，或有个颜色为e2的l2边形……或有个颜色为er的lr边形。符合条件又最少的数n则记为R(l1,l2,l3,...,lr;r)。

拉姆齐数的数值或上下界

已知的拉姆齐数非常少，保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”

显然易见的公式：

1°R(1,s)=1

2°R(2,s)=sR(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r) （将li的顺序改变并不改变拉姆齐的数值）

R(3,3)等于6的证明

证明：在一个K6的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。

一个图集对完全图的拉姆齐数

本文中的图都是指简单图。用G表示一个图，Kn表示一个n阶完全图。拉姆齐数r（G，Kn）表示满足如下条件的最小正整数N：当用红蓝两种颜色给N阶完全图着色时，要么红色图中含有G，要么蓝色图中含有Kn。设C表示一个圈图集，拉姆齐数r（C，Kn）表示满足如下条件的最小正整数N：若图F是一个N阶图，则图F至少含有C的一个元素，或者F含有Kn。图Kk+C是指：顶点集由Kk和C的顶点组成，边集由Kk和C的所有边，另外还有连接Kk和C的顶点之间的所有边组成。

拉姆齐定理定义

在组合数学上，拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。

拉姆齐定理的通俗表述：

6 个人中至少存在3人相互认识或者相互不认识。

该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。

注：这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic[2]（《形式逻辑上的一个问题》）证明了R(3,3)=6。

全国各地天气预报查询

上海市

市辖区

云南省

临沧市

云南省