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

1对四色地图问题的一个书面证明张天树[e-mail]摘要两个相邻图形的一处相邻边界只能是两条相邻的边界线.并让我们把任意未着色的平面地图的平面看成是由两种平行且一一交互的直线段组成，且每一种的每一条线段也是由一一交互的两种颜色点组成，于是，整个平面共有四种颜色点.在对平面地图上的图形着色以前，先要对它的图形进行分类和变换，首先依次把每个相邻不到4个图形的图形、或相邻不到4个图形的一片图形与至少有4个相邻图形的一个相邻图形合并，然后，从整体到部分地变换每片图形的每一个的边界封闭曲线成只有横、竖线段组成的矩形框.最后，根据矩形边界线上某些特殊点的颜色或与相邻图形不同的颜色对每个图形着色.关键词平面地图,图形，分类，四色，边界封闭曲线，颜色点，拓扑变换，图形包围圈，矩形.基本概念四色地图问题是说，给任意一个平面或球面地图上的每一个图形染上一种颜色，并使相邻两个图形被染上的颜色不同，那么，只要4种颜色就够了.我们把球面地图上的图形看成是印在橡皮曲面上的图形，只要在任意一个图形中破开一个孔，然后用力伸展球面成平面，那么，这个球面地图就变成了一个平面地图.这个孔的边缘就成了这个平面地图的边缘，但是，它不是图形的一条边界封闭线.显然，被开孔图形的一条边界封闭曲线在平面上向内包围了该地图上除开孔图形本身2和开孔图形其它边界封闭曲线包围的图形外的全部图形，而这条边界封闭曲线向外包围它所在的开孔图形和这开孔图形其它边界封闭曲线向内包围的图形.因此，我们只需要证明来自任意球面地图上的平面地图上的全部图形就行了.因为从球面地图转换来的平面地图包含了每一种局部的平面地图，于是我们只需要证明在存在各种可能情况下的整体平面地图,以下提到的平面地图指的就是这样的整体平面地图，凡是提到的图形指的都是在这种平面地图上的图形.就平面地图而论，存在各式各样形状、各种不同相邻关系的图形.但是，不管怎样，每个图形至少有一条边界封闭曲线.并且,每个图形必须是连成一片，而不能分成至少两个不相连接的部分.另外，任意一个平面地图都必须由图形填满，而不能存在没有图形的任何空隙.大家都知道：我们所说的平面地图的平面都是指的欧几里德几何平面.按照欧几里德几何对点和线的定义，即每个点是不可分的，线是由点组成，和每条线只有长度而没有宽度.我们可把一条边界封闭曲线的一部分称为一段边界线.既然如此，任何两个相邻图形不能共有平面上的若干点、一条或一段边界封闭线.那么，任意两个相邻图形的一处连续的边界，就只能是两条相邻的边界线.3如果还未对一个平面地图上的全部图形着色，我们就称这个平面地图为一个未染色的平面地图.如果一个平面地图上的全部图形都被着上了色，但不是最后着色，尽管某些图形的每一个由至少两个原有图形组成，理所当然，我们称这样的平面地图为一个临时着色的平面地图.让我们把任意一个未着色的平面地图的平面看作由一一交互的两种纵向直线段组成，并且一种的每一条由一个黑色点●交互一个白色点○组成，另一种的每一条由一个红色点®交互一个天蓝色点©组成.另一方面，这个平面也可看作是由一一交互的两种横向直线段组成，并且每一种的每一条横向直线段也是由彼此交互的两种颜色点组成.因此，无论从竖向看，还是从横向去看，相邻的两条直线段的各两种颜色点都完全不同.请看第一图:●®●®●®●®●®●®●®●®●®●®○©○©○©○©○©○©○©○©○©○©●®●®●®●®●®●®●®●®●®●®○©○©○©○©○©○©○©○©○©○©●®●®●®●®●®●®●®●®●®●®○©○©○©○©○©○©○©○©○©○©●®●®●®●®●®●®●®●®●®●®○©○©○©○©○©○©○©○©○©○©●®●®●®●®●®●®●®●®●®●®○©○©○©○©○©○©○©○©○©○©●®●®●®●®●®●®●®●®●®●®○©○©○©○©○©○©○©○©○©○©●®●®●®●®●®●®●®●®●®●®○©○©○©○©○©○©○©○©○©○©●®●®●®●®●®●®●®●®●®●®○©○©○©○©○©○©○©○©○©○©第一图在此，我们需要强调一点：这里所指的点是允许看得见和划得出4的，不管它是否有面积，但是它是不可分割的；当然，由这样的点组成的线也是能看得见和划得出的，不管它是否有宽度.如此地放大点和线，并不影响我们对平面由点、线组成的理解，也不影响我们对本命题证明的严密性.如果有人对这样放大点和线提出质疑，是否可以看作是为了证明该命题，而在平面上设计的一种模式呢？在这样的平面上的任意一个图形的一条边界封闭曲线不是由三种颜色点、就是由四种颜色点组成.对于由三种颜色点组成的任意一条边界封闭曲线，不仅它是一个矩形的四条边，而且它的四个直角的顶点共有一种颜色.因为任何一个国家或地区的版图都是在星球上，于是任何一个平面地图都只能来源于球面地图，因此，任何平面地图都总有这样一个图形，它的一条边界封闭曲线向内包围了除它本身和它本身其它的边界封闭曲线包围的图形外的全部图形.在一个未染色的平面地图上，无论对其图形变换与否，如果每一个图形都相邻至少四个图形，并有由至多三个图形向内包围的一片图形，我们就把直接包围这片图形的、由至多三段边界线组成的一条边界封闭曲线称为一条图形包围圈，简称为一条包围圈，并用符号“⊙”表示,另外符号“◎”表示至少有两条包围圈.很多图形没有包围圈，但有的图形确有若干整个或∕和部分的包围圈.5在任意一个平面地图上，根据从外向内包围圈所在不同层次的顺序，给全部包围圈初步划分等级，而根据拓扑变换的需要，它们的编号也是会改变的.首先，把含有开孔图形的边界封闭曲线编为第一◎或⊙，把由每一条第一⊙向内直接包围的◎或⊙编为第二◎或⊙…把由第k◎或⊙向内直接包围的◎或⊙编为第(k+1)◎或⊙，这里k≧1.也就是说，在一条第k⊙与这条第k⊙内的每一条第(k+1)⊙之间没有任何⊙.显然，同一级的◎是并列的，不存在包围与被包围的关系.并且，同一级的◎，它们可以在同一条包围圈中，也可以在不同的包围圈中，另一方面，对于一条⊙，它可为一个图形的边界封闭曲线，也可为不同图形的边界封闭曲线段的连接.在一条⊙被变换成一条由横向和竖向线段组成的矩形封闭曲线后，或者它本来就是这样的一条矩形封闭曲线，那么，用符号“”表示它,并且用符号“”表示至少两条矩形封闭曲线.在一个未染色的平面地图上，我们把任意一个图形的一条矩形封闭边界线看作是一个矩形的四条边，并且，除第一外，把这矩形封闭边界线和它向内包围的平面作为一个矩形.如果一个矩形的两条相对的边共由两种颜色点组成，那么，我们把这样的一条横边称为“一条横向的A边”或简称为“一条TA边”;又6把这样的一条竖边称为“一条竖向的A边”或简称为“一条LA边”.如果一个矩形有两条TA边和两条LA边,那么这个矩形被称为一个ΑA矩形，参看第三图(1).一个ΑA矩形的4个直角的顶点共有一种颜色.如果一个矩形的两条相对的边共由4种颜色点组成，那么，我们把这样的一条横边称为“一条横向的B边”或简称为“一条TB边”;又把这样的一条竖边称为“一条竖向的B边”或简称为“一条LB边”.如果一个矩形有两条TB边和两条LB边,那么这个矩形被称为一个BB矩形，参看第三图(3).一个BB矩形的4个直角的顶点有4种颜色.我们用符号“X”代替符号“T”和符号“L”,如果一个矩形有两条XA边和两条XB边,那么这个矩形被称为一个ΑB矩形，参看第三图(2).一个ΑB矩形的4个直角的顶点共有两种颜色.如果一整条XB边只相邻矩形的一条边的整个或部分，那么，这整条XB边被称为“一条单一的XB边”，或简称为“一条S边”.如果一整条XB边相邻至少两条矩形边的整个或部分，那么这整条XB边被称为“一条多邻的XB边”或简称为“一条M边”.7如果一条含有XB边的直线段与另一条直线段完全地相邻，且这两条直线段分别都是由整个的矩形边组成，那么，满足这样条件的最短两条相邻直线段，我们称含有XB边的一条为“α线段”,和另一条则被称为“β线段”，自然，β线段也可含有XB边.一条β线段和一条α线段总是孪生的,并且彼此相等.例如,下图中CD是一条含有M边κ的α线段，和GH是与CD相邻的一条β线段.GT边T边HCT边M边κT边D第二图对于一个BB矩形:如果它有4条S边,那么，它被称为一个B2SB2S矩形，见下图(4).如果它仅有一条M边,那么，它被称为一个B2SB1S矩形，见下图(5).如果它有两条相对的S边和两条相对的M边，那么，它被称为一个B2SB2M矩形，见下图(6).如果它有两条互相垂直的S边和两条互相垂直的M边,那么，它被称为一个B1SB1S矩形，见下图(7).如果它仅有一条S边,那么，它被称为一B1SB2M矩形，见下图(8).如果它有4条M边,那么，它被称为一个B2MB2M矩形，见下图(9).对于一个AB矩形:如果它有两条相对的S边,那么它被称为一个ΑB2S矩形，见下图(10).如果它仅有一条S边,那么，它被称为一个ΑB1S矩形，见下图(11).如果它有两条相对的M边,那么，它被称为一个ΑB2M矩形，见下8图(12).©○©○©○©○©○©○….©○©○©○©○©○…..©○©○©○©○©○®●®●®●®●®●®●….®●®●®●®●®●…..®●®●®●®●®●©○©○©○©○©○©○….©○©○©○©○©○…..©○©○©○©○©○…(1)anAArectangle……(2)anABrectangle………(3)aBBrectangle…©○©○©○©○©○©○….©○©○©○©○©○…..©○©○©○©○©○®●®●®●®●®●®●….®●®●®●®●®●…..®●®●®●®●®●©○©○©○©○©○©○….©○©○©○©○©○…..©○©○©○©○©○……®●®●®●®●…®●®●®●®●®●®●®●.®●®●®●®●®●®●©○©○©○©○…©○©○©○©○©○©○©○.©○©○©○.©○©○©○®●®●®●®●…®●®●®●®●®●®●®●.®●®●®●.®●®●®●…(4)aB2SB2Srectangle…(5)aB2SB1Srectangle……(6)aB2SB2Mrectangle…©○©○©○©○…©○©○©○©○©○©○©○.©○©○©○.©○©○©○®●®●®●®●…®●®●®●®●®●®●®●.®●®●®●.®●®●®●©○©○©○©○…©○©○©○©○©○©○©○.©○©○©○.©○©○©○®●®●®●®●…®●®●®●®●®●®●®●.®●®●®●.®●®●®●……©○©○©○©○©○…©○©○©○©○©○©…○.©○©○©○©.○©○®●®●®●®●®●…®●®●®●®●®●®…●.®●®●®●®.●®●©○©○©○©○©○…©○©○©○©○©○©…○.©○©○©○©.○©○…(7)aB1SB1Srectangle……(8)aB1SB2Mrectangle……(9)aB2MB2Mrectangle…©○©○©○©○©○…©○©○©○©○©○©…○.©○©○©○©.○©○®●®●®●®●®●…®●®●®●®●®●®…●.®●®●®●®.●®●©○©○©○©○©○…©○©○©○©○©○©…○.©○©○©○©.○©○®●®●®●®●®●…®●®●®●®●®●®…●.®●®●®●.®●®●©○©○©○©○©○…©○©○©○©○©○©…○.©○©○©○©.○©○®●®●®●®●®●…®●®●®●®●®●®…●.®●®●®●®.●®●……®.●®●®●®●®●…®●®●®●®●®●®●®●…®●®●®●®●®©.○©○©○©○©○…©○©○©○©○©○©○©○…©○©○©○©○®.●®●®●®●®●…®●®●®●®●®●®●®●…®●®●®●..®●©.○©○©○©○©○…©○©○©○©○©○©○©○…©○©○©○..©○…(10)anAB2Srectangle……(11)anAB1Srectangle………(12)anAB2Mrectangle©.○©○©○©○©○…©○©○©○©○©○©○©○…©○©○©○..