三角剖分图染色与换色通道-arXiv.PDF

三角剖分图与换色通道 三角剖分图染色与换色通道 甘润东 南开大学 ynztgrd@163.com 摘要 三角剖分图染色，是平面图染色的充分情况。本文将重点研究三 角剖分图，以及染色工具换色通道的性质。通过构造，将原来顶点的 4 染色，变换为边的3 染色，和三角形的2 染色，从而将等价的染色 方案合并。换色通道利用边染色的可传递性，体现出三角剖分图的整 体性。根据换色通道的性质得到两条约束条件，让换色有规律可以遵 循。最终使得在处理约化5 次顶结构上获得突破，证明了该结构的可 约性，从而否定了五色图最小反例的存在。 关键词：三角剖分图；肯普换色链；换色通道；不友好情况 MR(2000)分类号：05 C 15 （平面图染色） 1 三角剖分图与换色通道 目录 第一章、定理的阐述与历史 第二章、前期准备与新工具 第三章、特殊情况与证明 第四章、总结 参考文献 2 三角剖分图与换色通道 第一章、定理的阐述与历史 1.1 四色定理的阐述 四色定理，又称为四色猜想，四色问题。（可称为4CT：4 color theory ）。 4CT 是指，任意的一个平面图，都可以用4 种颜色区分开来，使 得相邻的两个区域颜色不同。 进一步的，我们可以将平面图作对偶化处理，添加更多的连接边， 使得所有顶点尽可能的相互连接。这样使得其成为一个三角剖分图。 那么显然的，如果任意的三角剖分图都是四色的，则它的任意子图也 是四色的。 因此，我们的研究，就以三角剖分图作为对象，不再从其他图作 为研究的切入点。 1.2 四色定理的发展历史 1.2.1 早期发展 4CT 于1852 年由Francis Guthrie 提出。 1878 年，Alfred Kempe 提出肯普链，宣布证明成功。 11 年后，希伍德P.J.Heawood 提出反例，指出肯普证明的漏洞。 1880 年，Peter Guthrie Tait 以边染色为切入点，借助哈密顿路径， 宣称证明4CT 。 1946 年，Tuttle 提出反例，Tait 的证明不成立。 3 三角剖分图与换色通道 尽管肯普和希伍德均未能破解四色问题,但是,他们二人均为四色 问题的最终获证乃至图论的发展做出了早期贡献。尤其是肯普所带来 的不可约集和不可避免集的概念。 1.2.2 计算机证明 1976 年，4CT 由阿佩尔K.Appel 与哈肯W.Haken 以机器方法证明。 1944 年，西缪尔P.Seymour 等人优化了证明。缩短了时间和证明 篇幅。 2005 年，贡蒂埃Georges Gonthier 给出形式证明（formal proof ）。 1.3 研究意义 时至今日，尚未出现四色定理的人工证明。某种意义上，四色定 理体现的是二维平面的一个固有属性，但更深入的，却是和NP 完全 问题有一定的相关性。解决四色定理的人工证明，有助于理解平面的 性质，有助于处理NP 问题。这个过程中产生的新工具，有助于图论 中染色理论的发展。 4 三角剖分图与换色通道 第二章、前期准备与新工具 2.1 准备工作 在证明工作开始之前，我们先做一些前期的准备工作。解决和定 义顶点染色与边染色。 2.1.1 定义 在三角剖分图的染色中，顶点染色用“1、2、3、 4 、5 ”来指代五