图论图着色.pdfVIP

图着色 四色猜想 顶点着色 边着色 v 3 v 2 独立集 v 1 v 0 v 4 v 5 图的着色 图的着色是指对图的每个结点(或边或平面图 的面)指定一种颜色，使相邻的结点(边或面) 不同色。 四色猜想：在一个平面上的任何地图，是否 可以最多只用四种颜色就能使相邻国家着不 同的颜色。(两个国家相邻是指它们有一段 公共的边界线，而两个国家只有一个或有限 的点相遇，它们就相邻，同样颜色也不会引 起混淆)。 1852年，格思里(Francis Guthrie)注意到美国地 图可以用4种颜色染色, 使得相邻区域(有一段公 共边界,不只是有一个公共点)有不同颜色;提出四 色猜想 1878年，德.莫尔根(De.Morgan)凯莱(Cayley)把 它提到伦敦数学学会上，“四色猜想”公诸于世， 引起了各国数学界的注意和兴趣。 1879年，开姆玻(Kempe)发表了第一个“证明” 1890年，希伍德(Heawood)发现了开姆玻的一个推 理错误，对其证明加以修改，提出并证明了“五色 定理” 1969年，奥尔(Ore)和斯坦普尔(Stemple)对少于 40个国家的所有地图，证明了“四色猜想”的正确 性。然而对任意多个国家，“四色猜想”的正确性 仍然没有证明出来。 1976年，美国数学家阿佩尔(K.Appel)和黑肯 (W.Hakan)首次应用计算机证明了这一难题，使 “四色猜想”成为“四色定理”。他们从1976年1月至 6月在三部计算机上用了1200小时，作了近百亿次 逻辑判断才得出结果，证明的正确性如果不借助 计算机也无法检验。 至今还没有找到能用“纸和笔”给出的证明。但人 们已经知道沿着上述方向是不可能使证明得到实 质性的简化。 任一平面图都有一个对偶图，平面图的面 和它的对偶图的结点有着一一对应的关 系，所以对平面图面的着色，可归化为对 其对偶图点的着色，显然研究平面图点的 着色要比研究图的着色更为方便. 所以对地图面的着色都是归化为点的着色 进行研究的。 对图G＝(V，E)的每个结点都指定一种 颜色，使得任意两个相邻的结点都被指 定不同色，如果颜色选自于一个有 k 种 颜色的集合，而不管 k 种颜色是否都用 到，则称这种结点k －顶点着色是正常 的，简称 着色。若图G有一个 着 k k 色，则称图G k－可着色的。 对图G的结点正常着色需要最少颜色的 种数，称为图G的点色数，记作 ψ (G) v 若 ψ (G) = k 这称G是 －色图。 v k 定理6.2