简单的染色问题.pdf

简单的染色问题 在我们美丽的地球上，有 60 多亿人口，任何六个人聚在一起，或者有三个人彼此相识，或者有三个 人彼此不相识。你相信吗？那就先让我们来作个游戏！规则：正六边形的六个顶点，两游戏者每次可 随意 ．． 选用红或蓝色的笔， 轮流 选择其中的两点连线，谁第一个被迫画成一个同色的三角形（红色或白色） ，他 ．． 就是失败者．这个游戏是否一定能分出胜负呢？与先下后下是否有关？ 抽象数学问题：把六个点（任意三点不共线）的连线染两色，至少会出现一个同色三角形． 证明： 任取一点 A ，那么由点 A 引出的 5 条边中，由抽屉原理， 至少有 A 三条是同色的，不妨设 AB 、AC 、AD 是蓝色的，如图所示．考察 BC 、BD 、 CD 三条边，若这三条边中有一条是蓝色的，则与 A 形成一个蓝色三角形； 若这三条边都是红色的，则三角形 BCD 为一个红色三角形． D C 任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相“ B 识 ”这样一个著名的实际问题也就迎刃而解． 1928 年，在英国伦敦数学会的一次学术会议上， 年仅 24 岁的年轻数学家弗兰克 普拉东· 拉姆赛· （Frank Plumpton Ramsey ）证明了一个定理：如果某一集合（如点集）中事物的数量足够多，且每对事物间都 存在一定数量的关系（如各种颜色的边）中的一种，那么必定存在一个包含若干数目事物的子集（如三点 集），其中每对事物间也存在同样的关系（如同色三角形） ．这个定理称为拉姆赛定理，告诉我们：如果平 面上的点数足够多，且每对点间的线（边）或染红色或染蓝色，那么必定存在一个包含 3 个点的子集，他 们之间的边同色，即包含一个同色三角形． 如果我们将刚才的六点染色游戏继续下去，染完所有的线段，同色三角形最少出现了几个？这是偶然 吗？恭喜你！答对了， 2 个！在六点（任意三点不共线）染色游戏中，必有两个同色三角形． 证明：方法一：为方便叙述， 我们把平面上有 n 个点，每两点都有连线的图称为 n 阶完全图，记作 K n ．由 拉姆赛定理知把 K 6 边染红、蓝两色，必出现一个同色三角形，不妨设这个三角形是红色的