PDF《图论中的经典问题简介》

50 国.后来这种 推进仍然十分缓慢. 电子计算机问世以后,大大加快了对四色猜想证明 的进程.1976 年,美国数学家阿佩尔与哈肯在美国伊利 诺斯大学的两台不同的电子计算机上, 用了

1200 个小时, 四色地图示意图 orld of Mathematics 数学烟云 W 数学文化/第3卷第2期69 作了

100 亿次判断,终于完成了四色定理的证明.为了 纪念这一历史性的时刻,两位数学家所在的伊利诺伊大 学邮局在每个邮件上盖上了这样的邮戳 Four Colors Suffice (四种颜色足够了) . 四色猜想的计算机证明轰动了世界.它不仅解决了 一个历时

100 多年的难题,而且有可能成为数学史上一 系列新思维的起点.1997 年罗伯逊、桑德斯、西摩和托 马斯简化了阿佩尔和哈肯的证明,但是证明的过程仍需 借助于计算机.直到现在,数学家们仍在寻求一个纯粹 数学的更简洁的证明. 3. 拉姆齐问题 假如要求在组合数学中举出一个而且仅仅一个精美的 定理,那么大多数组合数学家会提名 Ramsey 定理 ,这是 美国数学家 Gian-Carlo Rota 对Ramsey 定理的评价,也是对 Ramsey 定理在组合数学中地位的评价. 世界上完全的无序 是不可能存在的 、 任一个足够大的结构中必定包含一个 给定大小的规则的子结构 ,这富有哲理的格言恰是 Ramsey 理论的主导精神. 创立了Ramsey 数和Ramsey 理论的拉姆齐(F. P. Ramsey, 1903-1930) ,堪称旷世奇才.在如下领域都做出了 相当有影响的成就: 逻辑学、经济学、概率论、认知心理学、 科学方法论等. 1930年去世时只有26岁, 《图论杂志》 (Journal of Graph Theory)在1983 年7卷1期为纪念其

80 诞辰的专 刊里, 全面地介绍了他的生平、 贡献以及Ramsey理论的发展.

1958 年, 《美国数学月刊》 (The American Mathematical Monthly)上登载着这样一个有趣的问题 : 任何

6 个人的 聚会,其中总会有

3 个人相互认识,或3个人相互不认 识 .对Ramsey 理论作出重大贡献的组合数学家 Spencer 在1983 年描写了他第一次得知这个问题――也是他第一次接 触Ramsey 理论时的情形 : 当时我正在中学读书,得知这 个问题后,回家花了很长时间才费劲地搞出了一个分很多种 情况来讨论的冗长证明,我把我的证明带给老师,老师就给 我看下面的简单明了的标准证明.此论证的简单扼要当时 使我非常欣喜. 这个证明描述如下 : 用A,B,C,D,E, F 分别表示聚会的

6 个人,若两个人相识,则在代表这两人 的点之间用红边相连,否则连一条蓝边.这样把每对点都用 红边和蓝边连好之后,原来的问题就等价于证明图中有红边 三角形或者蓝边三角形.考虑从某一点(设为 A)连出

5 条边,根据抽屉原理,其中必有三条同色,不妨设它们是三条 红边 AD, AE, AF.再考虑三角形 DEF,如果它有一........