之前的一篇文章谈到了图论中关系的使用,并举例一个关于人们认识与不认识的有趣问题。这个问题的原型便是拉姆齐定理(Ramsey's Theorem)。
Ramsey's theorem states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph.
拉姆齐定理就是要找一个最小的数,使得n个人中必定有r个人相识或s个人互不相识,这个最小数就是拉姆齐数即R(r, s)。
由于人与人之间存在关系(认识或不认识),因此图论中将人表示为点,人们的关系用线表示,那么这个图就是一个完全图。图论表示法,对于完全图K,共有R(r, s)个点,任意一个2边着色(e1,e2),使得K[e1]中含有一个r边形,K[e2]含有一个s边形,则称满足这个条件的最小的R(r, s)为一个拉姆齐数。
上面所说的那篇文章,介绍了拉姆齐的一个特例,即R(3, 3) = 6。那么,其它的拉姆齐数都是多少呢?很遗憾,目前数学家们还没有找到定理的通用公式,而且世界已经找到的的拉姆齐数也非常少。
可以看到R(4, 4) = 18,而R(5, 5)就只通过证明,找到了一个区间43——49,具体是多少,至今无人知晓。
很多人热爱拉姆齐定理的证明,因为它看上去非常简单,易理解,可是证明却难于上青天,让很多数学家为此痴迷!也许第一次看到R(5, 5)的人会觉得,这么小个数字,怎么还区间呢,实在不行用计算机啊,为何证明不出具体数字。这里就给大家说一下,计算机为什么无法承担拉姆齐定理的证明。
首先,简单科普下什么是完全图:完全图是指所有顶点间两两相连构成的图。
因此,N阶完全图是指由N个顶点,两两相连,构成的具有Cn2条边的简单图。n阶完全图一般使用Kn来表示。下图为1阶到12阶的完全图:
用计算机找R(5, 5)有多困难呢,区间43——49,假设我们很幸运,43就是答案。那么K43,共有43 * 42 / 2 = 903条线。由于每条线有两种颜色可选,共计2903次种情况。对于每种情况,我们还要找出所有5边形C435,并对五边形的所有线路(10条)确认颜色,最终计算次数:
2903 * C435 * 10
这是一个天文数字,就算用计算机存储中间数据,100···00TB(两百多个0)的硬盘存储空间。
正如伟大的数学家Paul Erdős说得:
Aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find R(5,5). We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value.
If the aliens demanded the Ramsey number for R(6,6), however, we would have no choice but to launch a preemptive attack.
想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值,我们要尝试毁灭这帮外星人了。
我喜欢数学,因为数学展现了很多简单与极美的同时,也展现了她的神秘。世界未解难题,期待有生之年,有人找到那个钥匙!
Leave a Reply