图论五色问题四色问题.pdf

五色定理的证明以及对四色定理的一些想法 前言：我们必须承认，有很多优美的数学问题都是来自于最日常的生活，比如在 一张世界地图上，最少需要用几种颜色去给每个国家着色，才能使得任何两个相 邻的国家的颜色不同？在学习复杂网络这门课之前，我从来没有思考过这个问 题，更不知道它是一个非常著名的数学难题。所以我想，也许有的人能成为伟大 的数学家不仅依靠天分，更重要的是善于观察和思考生活中蕴涵数学思想的细 节，这恰恰是我们这样的学生所缺少的。 问题背景：四色问题，即每个地图是否能被四种颜色着色，使得相邻的两个国家 着不同的颜色，首先是由FrancisGuthrie在 1852年明确提出的，他把这个问题 交给当时正在剑桥大学读书的哥哥Frederick。Cayley于1878年在伦敦数 会 上介绍了这个问题，它才第一次被公众所了解。一年后，Kempe给出了一个错 误的证明，Heawood在1890年把Kempe 的证明修改后得到了五色定理的证明。 1880年，Tait声称给出了四色猜想的 “进一步证明”，实际上也是一个基于错误 假定的证明。直到197 年美国数学家Appel和Haken采用Kempe 的思路，利用 电子计算机证明了地图四色猜想是正确的，他们将地图四色问题化为将近2000 个特殊地图问题的四色问题，在电子计算机上计算了1200个小时才完成了证明。 尽管目前数学界逐渐接受计算机作为辅助证明的工具，但是仍有许多数学家希望 找到不借助计算机的证明。 通过本学期对复杂网络的学习以及查阅相关教材和论文，我希望总结出前人关于 五色定理的证明，并给出一些关于四色定理证明的想法，正确与否，有待考证。 本文首先将给出一些预备知识，包括平面图的定义及相关定理，图的着色问题等。 预备知识： 一、平面图和Euler公式 定义1.1：设一个无向图 ( 中的元素称为顶点， 中的元素称为边)，如 G(V,E) V E 果能把它画在平面上，且除了 中的顶点外，任意两条边均不相交，则称该图为 V 平面图。如果一个图和一个平面图同构，就称它为可平面图。 一个平面图将平面分成若干个部分，每个部分称为一个区域 （又称面）；一个平 面图所划分的区域中，总有一个区域是无界的，称其为外部区域，其他的称为内 部区域。 定义1.2：任何两个顶点之间总可以通过若干条边相连，这样的图称为连通图。 定理1.3 （Euler公式）：设 是一个连通平面图，具有 个顶点， 条边及 个 G n m l 区域，那么有nml2。 推论1.4：具有n3个顶点的平面图至多有3n 条边。 推论1.5：每个平面图必含有一个度小于或等于5的顶点。 定义1.6：设有平面图G(V,E)，满足下列条件的图G(V,E) 称为图 的对偶图： G G R v G R R e 的任一区域 内有且仅有一点 ；对 的区域 和 的共同边界 ，画一条 i i i j k e (v,v ) e e R v e 边 k i j 且只与 交于一点；若 完全处于 中，则 有一自环 。我们k k i i k 容易知道一个平面图的对偶图还是平面图。下图 是 的对偶图： G G 二、着色问题 定义2.1 （顶点着色）：给图 的每个顶点指定一种颜色，使得任何两个相邻的 G 顶点颜色均不同。如果用 中颜色对图 进行顶点着色，就称对图 进行了 着 k