朋友与陌生人

作者: Kevin Hartnett

来源: QuantaMagazine

发布日期: 2017-04-20

本文介绍了弗兰克·拉姆齐及其在1930年提出的拉姆齐定理,该定理是图论中的一个重要概念,解释了在完全图中如何通过颜色线条的连接形成一致的子集。文章通过友谊定理的简单版本和数学家Jonathan Jedwab的图形解释,详细阐述了拉姆齐定理的正确性及其应用。

1903年,弗兰克·拉姆齐出生于英国伦敦,后来进入剑桥大学三一学院学习数学,成为了一名杰出的数学家、哲学家和经济学家。可惜天妒英才,1930年就病逝于伦敦。但是在短短的岁月中,他在数学和其它领域做出了许多贡献。今天所要谈论的是他在1930年发表的论文《形式逻辑上的一个问题》所提出来的拉姆齐定理。

拉姆齐定理是图论中的一个重要概念,它被表述为对于任一具有N个顶点的完全图,所有的顶点之间可以用红色或蓝色的线条连接,图中肯定会呈现出完全一致的大子集——要么全红,要么全蓝。我们也可以先通过确定一致子集的大小,再根据拉姆齐定理反推出能够形成该子集所需的完全图。完全图是指所有顶点间两两相连构成的图。

拉姆齐定理还有一个简单易懂的版本叫“友谊定理”:六个人当中至少有三个人相互认识(朋友)或者相互不认识(陌生人)。但为什么这个定理是正确的?为什么完全图中的这些不同颜色的线条不能被完全打乱?数学家Jonathan Jedwab用一系列图形直观的解释了这个定理为什么是正确的。让我们看一个简单的示例——一个六边形的完全图可以形成最少三条颜色一致的线组成的子集。这是为什么呢?

把这六个点看成六个人,其中任何一人与另一人必定处于认识或者不认识的状态。若认识,我们将二人用红线连接;若不认识,则用蓝线连接。因此在这个社交小圈子中,每个人都辐射出五条线与其他五人相连,并且其中至少三条线的颜色相同。这意味着无论你怎样连接这些人,结果一定会出现一个全红或者全蓝的三角形。首先我们来看1,从他身上发射出的五条线中,像之前说过的至少有三条线颜色相同。

假如他认识2、4、5,则这三条线便是红色。再看2和5,假如2和5相识,则2与5间的连线也是红色,从而得到一个红色的三角形。我们看看是否有方法避免这样的三角形产生,所以假定2与5互不相识,并将2、5之间用蓝色线条标记。接下来再思考4和5的关系,同样的,为了避免1、4、5形成红色三角形,我们假设4、5也互不相识。最后考虑2和4的关系,结果发现不论2月4相识与否,都会形成一个红色或蓝色的三角形。

于是一个单色的小色块集合便会出现,拉姆齐定理得到印证。用这种方法研究更大的集合中样本时,比如数百万、数千万、数亿的人群,能看到组成的单色色团由大量相同颜色的线段组合而成。但究竟这个“大量”有多大呢?数学家们并不能确定,在已知一个单色子集的大小前,我们无法知道形成它所需要的完全图的最小大小。拉姆齐定理也如其他许许多多日常使用的工具一样——它相当有用,但我们却不尽了解其背后所有的工作原理。

UUID: 0ca31c32-05ee-469f-b6ed-644f1c48ea7e

原始文件名: /home/andie/dev/tudou/annot/AI语料库-20240917-V2/AI语料库/原理公众号-pdf2txt/2017年/2017-04-20_朋友与陌生人.txt

是否为广告: 否

处理费用: 0.0031 元