第1个回答 2016-06-02
拉姆齐数，用图论的语言有两种描述：
对于所有的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)=s R(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r) （将li的顺序改变并不改变拉姆齐的数值）
相似回答