对四色地图问题的一个书面证明

1、对四色地图问题的一个书面证明 张 天 树 tianshu_摘 要两个相邻图形的一处相邻边界只能是两条相邻的边界线. 并让我们把任意未着色的平面地图的平面看成是由两种平行且一一交互的直线段组成，且每一种的每一条线段也是由一一交互的两种颜色点组成，于是，整个平面共有四种颜色点. 在对平面地图上的图形着色以前，先要对它的图形进行分类和变换，首先依次把每个相邻不到4个图形的图形、或相邻不到4个图形的一片图形与至少有4个相邻图形的一个相邻图形合并，然后，从整体到部分地变换每片图形的每一个的边界封闭曲线成只有横、竖线段组成的矩形框. 最后，根据矩形边界线上某些特殊点的颜

2、色或与相邻图形不同的颜色对每个图形着色. 关键词平面地图, 图形，分类，四色，边界封闭曲线，颜色点，拓扑变换，图形包围圈，矩形. 基本概念四色地图问题是说，给任意一个平面或球面地图上的每一个图形染上一种颜色，并使相邻两个图形被染上的颜色不同，那么，只要4种颜色就够了.我们把球面地图上的图形看成是印在橡皮曲面上的图形，只要在任意一个图形中破开一个孔，然后用力伸展球面成平面，那么，这个球面地图就变成了一个平面地图. 这个孔的边缘就成了这个平面地图的边缘，但是，它不是图形的一条边界封闭线.显然，被开孔图形的一条边界封闭曲线在平面上向内包围了该地图上除开孔图形本身和开孔图形其它边界封闭曲线包围的图形外

3、的全部图形，而这条边界封闭曲线向外包围它所在的开孔图形和这开孔图形其它边界封闭曲线向内包围的图形.因此，我们只需要证明来自任意球面地图上的平面地图上的全部图形就行了. 因为从球面地图转换来的平面地图包含了每一种局部的平面地图，于是我们只需要证明在存在各种可能情况下的整体平面地图, 以下提到的平面地图指的就是这样的整体平面地图，凡是提到的图形指的都是在这种平面地图上的图形.就平面地图而论，存在各式各样形状、各种不同相邻关系的图形.但是，不管怎样，每个图形至少有一条边界封闭曲线.并且,每个图形必须是连成一片，而不能分成至少两个不相连接的部分.另外，任意一个平面地图都必须由图形填满，而不能存在没有图

4、形的任何空隙.大家都知道：我们所说的平面地图的平面都是指的欧几里德几何平面.按照欧几里德几何对点和线的定义，即每个点是不可分的，线是由点组成，和每条线只有长度而没有宽度. 我们可把一条边界封闭曲线的一部分称为一段边界线. 既然如此，任何两个相邻图形不能共有平面上的若干点、一条或一段边界封闭线. 那么，任意两个相邻图形的一处连续的边界，就只能是两条相邻的边界线. 如果还未对一个平面地图上的全部图形着色，我们就称这个平面地图为一个未染色的平面地图. 如果一个平面地图上的全部图形都被着上了色，但不是最后着色，尽管某些图形的每一个由至少两个原有图形组成，理所当然，我们称这样的平面地图为一个临时着色的平

5、面地图. 让我们把任意一个未着色的平面地图的平面看作由一一交互的两种纵向直线段组成，并且一种的每一条由一个黑色点交互一个白色点组成，另一种的每一条由一个红色点交互一个天蓝色点组成. 另一方面，这个平面也可看作是由一一交互的两种横向直线段组成，并且每一种的每一条横向直线段也是由彼此交互的两种颜色点组成.因此，无论从竖向看，还是从横向去看，相邻的两条直线段的各两种颜色点都完全不同. 请看第一图: 第一图在此，我们需要强调一点：这里所指的点是允许看得见和划得出的，不管它是否有面积，但是它是不可分割的；当然，由这样的点组成的线也是能看得见和划得出的，不管它是否有宽度. 如此地放大点和线，并不影响我们对

6、平面由点、线组成的理解，也不影响我们对本命题证明的严密性. 如果有人对这样放大点和线提出质疑，是否可以看作是为了证明该命题，而在平面上设计的一种模式呢？在这样的平面上的任意一个图形的一条边界封闭曲线不是由三种颜色点、就是由四种颜色点组成. 对于由三种颜色点组成的任意一条边界封闭曲线，不仅它是一个矩形的四条边，而且它的四个直角的顶点共有一种颜色. 因为任何一个国家或地区的版图都是在星球上，于是任何一个平面地图都只能来源于球面地图，因此，任何平面地图都总有这样一个图形，它的一条边界封闭曲线向内包围了除它本身和它本身其它的边界封闭曲线包围的图形外的全部图形. 在一个未染色的平面地图上，无论对其图形变

7、换与否，如果每一个图形都相邻至少四个图形，并有由至多三个图形向内包围的一片图形，我们就把直接包围这片图形的、由至多三段边界线组成的一条边界封闭曲线称为一条图形包围圈，简称为一条包围圈，并用符号“”表示, 另外符号“”表示至少有两条包围圈. 很多图形没有包围圈，但有的图形确有若干整个或和部分的包围圈. 在任意一个平面地图上，根据从外向内包围圈所在不同层次的顺序，给全部包围圈初步划分等级，而根据拓扑变换的需要，它们的编号也是会改变的. 首先，把含有开孔图形的边界封闭曲线编为第一或，把由每一条第一向内直接包围的或编为第二或把由第k或向内直接包围的或编为第(k+1)或，这里 k1.也就是说，在一条第k

8、与这条第k内的每一条第(k+1)之间没有任何. 显然，同一级的是并列的，不存在包围与被包围的关系.并且，同一级的，它们可以在同一条包围圈中，也可以在不同的包围圈中，另一方面，对于一条，它可为一个图形的边界封闭曲线，也可为不同图形的边界封闭曲线段的连接. 在一条被变换成一条由横向和竖向线段组成的矩形封闭曲线后，或者它本来就是这样的一条矩形封闭曲线，那么，用符号“1”表示它, 并且用符号“ 2 ”表示至少两条矩形封闭曲线. 在一个未染色的平面地图上，我们把任意一个图形的一条矩形封闭边界线看作是一个矩形的四条边，并且，除第一2外，把这矩形封闭边界线和它向内包围的平面作为一个矩形. 如果一个矩形的两条

9、相对的边共由两种颜色点组成，那么，我们把这样的一条横边称为 “一条横向的A 边”或简称为 “一条 TA 边”; 又把这样的一条竖边称为 “一条竖向的A 边”或简称为 “一条 LA 边”. 如果一个矩形有两条 TA 边和两条 LA 边, 那么这个矩形被称为一个 A 矩形，参看第三图 (1). 一个 A 矩形的4个直角的顶点共有一种颜色.如果一个矩形的两条相对的边共由4种颜色点组成，那么，我们把这样的一条横边称为 “一条横向的B 边”或简称为 “一条TB边”; 又把这样的一条竖边称为 “一条竖向的B边”或简称为 “一条 LB 边”. 如果一个矩形有两条 TB 边和两条 LB 边, 那么这个矩形被称

10、为一个 BB 矩形，参看第三图 (3). 一个 BB 矩形的4个直角的顶点有4种颜色. 我们用符号 “X ” 代替符号 “T” 和符号 “L”, 如果一个矩形有两条 XA 边和两条XB 边, 那么这个矩形被称为一个 B 矩形，参看第三图 (2). 一个B 矩形的4个直角的顶点共有两种颜色. 如果一整条 XB 边只相邻矩形的一条边的整个或部分，那么，这整条XB 边被称为“一条单一的XB边” ，或简称为 “一条S 边”.如果一整条 XB 边相邻至少两条矩形边的整个或部分，那么这整条XB边被称为 “一条多邻的XB边” 或简称为“一条 M 边” . 如果一条含有XB 边的直线段与另一条直线段完全地相邻

11、，且这两条直线段分别都是由整个的矩形边组成， 那么，满足这样条件的最短两条相邻直线段，我们称含有 XB 边的一条为 “ 线段”, 和另一条则被称为“线段”，自然，线段也可含有 XB 边. 一条 线段和一条 线段总是孪生的, 并且彼此相等. 例如, 下图中 CD 是一条含有M边的 线段，和GH 是与CD相邻的一条 线段. G T 边 T 边 H CT 边 M 边 T边 D 第二图对于一个 BB 矩形: 如果它有4条S边, 那么，它被称为一个B2SB2S 矩形，见下图 (4).如果它仅有一条M边, 那么，它被称为一个B2SB1S 矩形，见下图(5).如果它有两条相对的 S 边和两条相对的 M 边，

12、那么，它被称为一个 B2SB2M 矩形，见下图 (6).如果它有两条互相垂直的 S 边和两条互相垂直的 M 边, 那么，它被称为一个 B1SB1S 矩形，见下图 (7).如果它仅有一条 S边, 那么，它被称为一B1SB2M 矩形，见下图 (8).如果它有4条M边, 那么，它被称为一个B2MB2M矩形，见下图(9).对于一个 AB 矩形: 如果它有两条相对的S边, 那么它被称为一个B2S矩形，见下图(10). 如果它仅有一条 S 边, 那么，它被称为一个 B1S 矩形，见下图 (11). 如果它有两条相对的 M 边, 那么，它被称为一个 B2M 矩形，见下图 (12). . . . . . .

13、(1) an AA rectangle (2) an AB rectangle (3) a BB rectangle . . . . . . . . . . . (4) a B2SB2S rectangle (5) a B2SB1S rectangle (6) a B2SB2M rectangle . . . . . . . . . . . . . . (7) a B1SB1S rectangle (8) a B1SB2M rectangle (9) a B2MB2M rectangle . . . . . . . . . . . . . . . . . . . . (10)an AB2S r

14、ectangle (11)an AB1S rectangle (12)an AB2M rectangle . . . . . . . . . . . . . . . 第三图证 明首先，让我们解决掉这样的平面或球面地图，就是它的全部图形都是每个相邻至多三个图形. 对于这样的平面地图，只需将它的每个图形依次染上与它相邻图形颜色不同的一种颜色即可，那么四种颜色是足够的.除此之外的平面地图，我们将对其上面的图形先进行变换后，然后才能分别给它们着色，有些成片图形相邻不到四个图形，还需要经过变换、着色交替进行后，才能最终确定每个图形应该着上的颜色. 其具体步骤顺序如下：第一步. 在一个未染色的平面地图上，

15、如果既有每个图形相邻至少四个图形的图形，又有每个图形相邻至多三个图形的图形，那么，就依次将每个相邻至多三个图形的图形与它相邻、且相邻至少四个图形的一个图形合并成为一个图形，使合并后的这个图形也相邻至少四个图形. 第二步. 分别对每一条第一及它向内包围的图形进行变换.如果一条第一仅仅与一个图形的一条边界封闭曲线相邻，即一条第一仅仅直接包围一个图形，那么就将开孔图形与该图形合并成一个图形，并把原两个图形所属的都称为第一，然后，从外向内的的编号照样减去1. 然后，在一条第一直接包围的图形中，如果仍然存在着与上述相同的相邻情况，那么，继续照此处理；在一条第一包围的图形中，如果存在着第二或，那么，就把每

16、一条第二向内包围的全部图形与一个含有这条第二整个或部分的图形合并为一个图形,这样，原第二已不存在，就把与合并后图形的边界封闭曲线相邻的一条边界封闭曲线作为一条第二.第三步. 通过拓扑变换，把每一条第一及各条第一向内包围的图形的每一条边界封闭曲线，包括第二，变换成只有横向边和竖向边的矩形框. 另外，我们规定：相邻两个相邻图形的相邻边界必须为两条相邻的直线段，第一1也不例外，因为第一1所在的图形也向内相邻至少四个图形. 那么，每一条第一就变成了一条第一1. 总的说来，拓扑变换每个第一1向内包围的全部图形成为矩形，其类型至多有10种：即A 矩形、B2SB2S 矩形、B2SB1S矩形、B2SB2M矩形

17、、B1SB1S矩形、B1SB2M矩形、B2MB2M 矩形、B2S 矩形、B1S 矩形和B2M 矩形. 第四步. 变换每一条第一1成为一个A 矩形框，那么，全部这样的A 矩形框共由三种颜色点组成. 并且，同步地变换向外相邻每一条第一1的一条图形的矩形边界封闭曲线成为另一个A 矩形框，则每一条这样的A 矩形框与变换第一1所得的A 矩形框有不同的三种颜色点，但这两个A 矩形框仍然是完全相邻的. 第五步. 将每一条第一1包围的每列矩形、从左到右依次地、尽量将每个矩形的两条竖向边变换成两条LA边，那么，或者矩形的竖向边保持不动，或者向右依次移动整条的矩形竖边或由整条竖边组成且相邻相等的和线段到各自相邻的

18、竖向直线段. 最后，对于最右一列矩形：当每一行的矩形数目是奇数时，则全是仅有两条LA边的矩形，当每一行的矩形数目是偶数时，则全是仅有两条LB 边的矩形，当有的行的矩形数目是奇数、而另外行的矩形数目是偶数时，则既有两条LA边的矩形，又有两条LB 边的矩形.再将每一条第一1包围的每行矩形、从上到下依次地、尽量将每个矩形的两条横向边变换成两条TA 边，那么，或者矩形的横向边保持不动，或者向下依次移动整条的矩形横边或由整条横边组成且相邻相等的和线段到各自相邻的横向直线段. 最后，对于最下一行矩形：当每一列的矩形数目是奇数时，则全是仅有两条TA边的矩形，当每一列的矩形数目是偶数时，则全是仅有两条TB 边

19、的矩形，当有的列的矩形数目是奇数、而另外列的矩形数目是偶数时，则既有两条TA边的矩形，又有两条TB 边的矩形.于是，在每一条第一1包围的矩形中，除最右边的一列矩形和最下边的一行矩形外，全部都是A 矩形. 在一条第一1包围的矩形中，就最右边的一列矩形而言：如果每个都有两条LA 边，那么，除了最下面的一个外，全部都是A 矩形；如果每个都有两条LB 边，那么，除了最下面一个外，全部都是B 矩形；如果既有两条LA 边的矩形，又有两条LB 边的矩形，那么，除最下面一个外，这列矩形既有A 矩形又有B 矩形.在一条第一1包围的矩形中，就最下边的一列矩形而言：如果每个都有两条TA 边，那么，除了最右面一个外，

20、全部都是A 矩形. 如果最右面一个有两条LA 边，那么，这最右面一个是A矩形；如果最右面一个有两条LB 边，那么，这最右面一个是AB矩形.如果每个都是有两条TB 边，那么，除了最右面一个外，全部是B 矩形. 如果最右面一个有两条LA 边，那么，这最右面一个是B矩形；如果最右面一个有两条LB 边，那么，这最右面一个是BB矩形. 如果既有两条TA 边的矩形，又有两条TB 边的矩形, 那么，这一行矩形既有A 矩形，又有B 矩形, 并且， 最右面一个或者是A 矩形，或者是B 矩形，或者是BB矩形.第六步. 我们首先需要判断这个未染色的平面地图上的各种图形应该染上什么样的颜色，然后才能正确地给每个图形染

21、上一种颜色. 除全部第一2外，可给每一个A矩形染上与它的四个直角顶点相同的一种颜色，那么，两个相邻的A矩形被染上了不同的颜色. 如果在一条第一1包围的图形中有B矩形，那么，B矩形一定是在最右一列或和最下一行矩形上. 而且，如果最右一列和最下一行仅除相邻第一1右下角两边的一个矩形外全部是B矩形，那么根据前面的作法，相邻这条第一1右下角两边的这个矩形一定是BB矩形.于是，给在最右一列上的每个B矩形染上与各自左边两个直角顶点相同的一种颜色；给最下一行上的每个B矩形染上与各自上边两个直角顶点相同的一种颜色；给相邻第一1右下角两边的这个BB矩形染上与它左上角顶点相同的一种颜色. 现在，恢复含有整个和部分

22、最后确定的第一的图形的边界封闭曲线，而不论他们的形状如何. 根据上面的作法，我们知道，每一个这样的图形相邻至少四个原来的图形.如果一个图形的每一条第一1内的矩形都是A矩形，没有B矩形和BB矩形，并且，这些第一2总共都是由三种颜色点组成，那么，就给这个图形染上与任意这样一个第一1直角顶点相同的一种颜色.如果在一条第一1内既有A矩形，又有B矩形，那么，按照一图一色、两色交替的原则，依次染含有这第一1上边的整个或部分的每个图形为这第一1上边点的两种颜色之一，和依次染含有这第一1左边的整个或部分的每个图形为这第一1左边点的两种颜色之一，但在第一1的左、上角相邻的两个图形所染颜色不同. 假使第一1内最右

23、一列有B矩形，就依次染含有这第一1右边的整个或部分的每个图形为相邻第一1右边的直线段的点的两种颜色之一，但在第一1的右、上角相邻的两个图形所染颜色不同. 假使第一1内最下一行有B矩形，就依次染含有这第一1下边的整个或部分的每个图形为相邻第一1下边的直线段的点的两种颜色之一，但 在第一1的左、下角相邻的两个图形所染颜色不同，在第一1的右、下角相邻的两个图形所染颜色也不同.如果一个图形含有至少两个第一2的整个和或部分，那么，分别从各条第一1去确定这个图形应该染上的颜色，无论如何，从每一条第一1去确定的颜色必须是一样的. 假如不一样，就需要把有同一颜色的一种图形的每一个与它相邻图形去交换颜色，使含第

24、一2的图形能染上一种颜色; 假如不能交换颜色，就要重新变换部分的第一2和它们每一条向内包围的图形的边界封闭曲线. 即，首先变换每条这样的第一1为与原先不同三种颜色点的A矩形框，并同步地变换向外与它全部相邻的一条边界封闭曲线. 再变换每条这样的第一1向内包围的图形.根据上述的作法，这样是完全能够让含有至少两个第一1的整个和或部分的图形被染上同一种颜色的.总而言之，经过前面的作法，我们已达到：给每个图形着上了一种颜色，且相邻两个图形着上的颜色是不同的. 第七步. 在各条第一1内，首先恢复每条第二1和相邻至少四个图形的每个图形的边界封闭曲线，并消除这些图形被染上的一种颜色，再恢复这些图形的平面上原先的四种颜色点. 然后，根据前面的作法，变换这些图形成矩形，并给每一个图形着上一种颜色.在一个未着色的平面地图上，假设有n 个等级的，这儿n1，那么，根据前面的作法，在依次变换n 个等级的和各个向内包围的图形、以及给每一个图形着上一种颜色后，在这个临时