四色问题证明的历史（一）

雷明85639720

四色问题证明的历史（一）
雷  明
（二○二一年十二月十二日）

一、追溯到最早期：
四色问题是一个属于拓扑学的问题，如果追根溯源，它的粗略描述可以追溯到1840 年。
1840年：
德国数学家莫比乌斯（August Mobius,1790—1868）在给学生的讲课中提到：在平面上很容易指出四个区域，其中每两个区域都有一个公共的边界线，并要求学生证明：在平面上决不可能指出五个区域都具有上述的性质。从这个论断的证明中，可得出莫比乌斯假设：平面或球面上的每张地图都可以用四种颜色来着色。
这就是有名的“5个王子问题”和“5座宫殿问题”。“5个王子问题”说的是曾有一位国王，有5个儿子。他在遗嘱中说：在他死后，把他的国家划分成5个区域，每个王子可以分得一个区域，并且还要求每个区域都和其他的4个区域有共同的边界。该如何来完成这件事呢？如果这个问题的解不很明显，那么Heinrich Tietze（1880—1964）针对这一问题提出的“5座宫殿问题”就容易知到“5 个王子问题”是无解的。“5座宫殿问题”是说国王另外又要求每位王子都要在自已的领域内修建一座宫殿，并且还要修建道路连接每座宫殿，使得任何两条道路都不会交叉。这又如何来完成呢？
虽然这些问题看起来与四色问题是格格不入、毫无关系的，但却说明了在平面上是不可能有5个区域是两两相邻的。也说明了给地图染色时是用不到五种以上的颜色的，或者说四种颜色就够用了。但这还只能也是一个猜测，绝不等于说四色猜测就是正确的。
二、四色猜测早期提出和传播的阶段：
1852年：
明确提出四色问题的是在1852年由英图的绘图员法郞西斯·古特里（Ftancis Guthrie,1831—1899）首先提出了地图四色问题。他在给地图染色时发现，如果给任意相邻的地区染上不同的颜色，那么任何地图只要四种颜色就足够使用了。
因为他无法证明自已的猜测是否正确，就把这一问题向他正在伦敦大学读书的弟弟弗内德里·古特里（Frederick Guthrie）提了出来，希望能给以解释其中的道理。
弗内德里认真的研究之后，既不能证明这个猜测是正确的，也不能给以否定。
1852年10月23日弟弟在征得哥哥的同意之后，弗内德里就把这个问题写信向他的老师——伦敦大学的教授、著名的数学家古斯特·德·莫根（Augustus de Morgan,1806—1871）进行请教。
莫根也无法解释，但他认为这是一个崭新的东西。于是就在当天写信给他在剑桥大学三一学院任教的好友——著名数学家和物理学家威廉·哈密顿（William Hamilton）教授，希望能给以解决。信中在叙述了四色猜测之后并自问道“难道不可以构造出一个需要五种或者是更多种颜色的图吗？”但又说“我怀凝五种或更多种颜色是不必要的。”于是，莫根给哈密顿的这封信就成了四色问题用文记载的第一个文件。时间是1852年10月23日。
莫根虽然对四色猜测有怀凝，但他却希望聪明的哈密顿给以解决。可惜，哈密顿并没有重视它。三日后的10月26日，哈密顿给莫根回了信，说“我可能不能很快就考虑你的‘4元组’问题。”以后也就没有再见到下文。
虽然莫根起初对这个问题很感兴趣，但由于没有得到朋友的支持，时间一长，他的兴趣也就淡化了。尽管如此，但莫根还是以各种方式继续的对四色猜测进行着传播。现在已经发现的有文字记录的是莫根在四色猜测提出已经过去了8年之后的1860年4月14日所写的一篇书评，其中就对四色问题进行着传播。
正是在莫根的努力下，后来四色问题才得以传播到数学界，也才引起了数学界的关注。
三、四色猜测得到数学界重视的阶段：
1878年：
自猜测提出后，已过去了26年后的1878年6月13日，在伦敦的数学会上，人们对四色猜测的兴趣又复燃了起来。6月17日著名的英国数学家凯莱（Cayley·A,1821—1895）正式询问地图四色问题是否得到解决，并呼吁与会者去解决这一问题。与会的代表中就有1872年从英国剑桥大学三一学院毕业的，十分聪明的业余数学家，后来对猜测提出第一个证明的坎泊（Alfred  Bray Kempe,1849—1922）也在其中。第二年（1879年）在英国皇家地理学会上凯莱再次提出了这个问题，并在该会创办的第一卷会刊《皇家地理学会会报》上发表。一时间，这个问题开始吸引了一批有才华的人去研究它，四色问题才引起了数学界的专家学者和一些非数学界人士的重视。1879年的7月13日，律师出身的坎泊在《自然》杂志上宣布他已经解决了四色问题，并在凯莱的建议下，当年坎泊就把它发表在《美国数学杂志》的第二卷上。
1880年，从猜测提出之日起，时间已经过去了28年。当四色问题已经引起了大家的极大兴趣之后，已成为一名物理学家的弗内德里才在爱丁堡皇家学会的刊物上发表了一篇短文。文中说大约在三十年前，他还是莫根班里的一个学生时，是他的哥哥法朗西斯首先告诉他地图四色问题的。因为他也无法解决，他才去请教他的老师莫根的。
28年过去了，总算弄清楚了首先提出四色猜测的第一人是法郞西斯，时间是1852年。后来法郞西斯也成为一名数学教授，任教于南非的开普勒大学，可惜直到1899年他去逝时，对自已提出的地图四色猜测却无任何建树，但他却是提出猜测的第一人。
四、把一个无穷的地理学问题转化成一个有限的数学问题：
由于四色猜测是因给地图的染色而提出的，所以早期的研究与证明工作都是直接的给地图的面上的染色，比较复杂一些。因为地图是一个所有顶点都是3度的3—正则平面图，其对偶图则是一个各面都是三边形的极大平面图。对极大平面图的顶点着色，也就相当于给地图的面上的染色。所以后来人们在研究和证明四色猜测时，都用了对极大平面图的顶点着色，比较的方便一些。又由于任何平面图中至少都含有一个顶点的度是小于等于5的，所以度是小于等于5的顶点就是平面图的不可避免顶点。由度是小于等于5的六种顶点为待着色顶点的一种叫做“构形”的图所构成的集合，就是平面图的不可避免构形集。只要研究和证明了这六种待着色顶点的度是小于等于5的构形都是可约的（即可4—着色的），平面图的四色问题就可以得到证明是正确的。这就把一个研究对象是无穷多的地图的地理学问题，转化成了一个研究对象是有限的平面图的不可避免构形的数学问题了。
这里的“构形”就是指还有一个顶点未着色的平面图。未着色的顶点就是待着色顶点，与待着色顶点相邻的顶点是围栏顶点。“构形”中除了待着色顶点外，围栏顶点和其他顶点都是已用4种颜色着了色的且符合四色要求的顶点。由于在极大平面图中，每一个顶点都是处在一个轮的中心位置，所以这样的构形也就叫作轮构形。平面图不可避免的轮构形，就相当于坎泊所说的任何地图中都一定含有“一图与两国相邻”、 “一图与三国相邻”、 “一图与四国相邻”、 “一图与五国相邻”四种情况的“构形”中的一种。但实际地图中还有一种是 “一图与一国相邻”的“国中之国”的情况，其对偶图则是一个平面图K2（只有一个轮沿顶点），而平面图中也还有一个只有一个顶点的K1图（无轮沿顶点），所以平面图的不可避免构形集中就是六种轮构形。
“构形”、“不可避免构形”，“不可避免构形集”、“构形可约”等都是早期坎泊提出的术语，一直沿用至今已有一百四十多年了。
只要证明了平面图不可避免的构形都是可约的，也就证明了任何极大平面图的四色猜测是正确的；同时也就证明了任何地图的四色猜测也是正确的。由于已4—着色的极大平面图经去顶或减边后所得到的任意平面图的色数只会比极大平面图的色数减少，而不会再增大，所以这也就证明了任意平面图的四色猜测也是正确的。这样才可以得到四色猜测是正确的最终结论。
五、四色猜测的证明阶段：
1879年：
英国人律师兼数学家坎泊是在1879年7月提出对四色猜测证明的第一人，用了他创建的“颜色交换技术”在“色链”中进行颜色交换，只证明了不含有共同的起始顶点的双环交叉链的构形和虽然是含有共同的起始顶点的双环交叉链，但可以连续的移去两个同色的K—构形（坎泊构形）都是可约的，而遗漏了对含有共同的起始顶点的双环交叉链，并且是不可连续的移去两个同色的H—构形（赫渥特构形）的研究。
这里需要介绍一下坎泊使用的、且至今仍在使用的专业术语。除了以上的“构形”、“可约”以外，还有以下多个：
色链：用两种颜色交替着色的一个序列（或一条道路）叫色链，简称“链”。
由此便产生了以下诸多术语：
对角链和非对角链：由两个相邻围栏顶点的颜色构成的链叫邻角链；而由两个对角围栏顶点的颜色构成的链叫对角链。
连通链和非连通链：链的两端分别是两个对角围栏顶点的链叫连通链；只有一端与围栏顶点连接的链是非连通链。对角链是可以连通的；而邻角链是不存在连通不连通问题的。
交叉链和非交叉链：可以相互穿过的两条链叫交叉链；否则就是非交叉链。
相反链和相邻链：链中两种颜色完全不同的两条链是相反链；而有一种颜色相同的两条链是相邻链。相反是不能相互交叉的；而相邻链却是可以相互交叉的。
颜色交换：把一条链中的所有顶点的颜色都进行交换一次，就叫颜色交换，用这一交换方法可以改变链中的任何一个顶点的颜色。
环形链与非环形链：一条链的首尾是相接的偶圈就是环形链；否则就是非环形链。
非连通的对角链的交换是可以改变或空出围栏顶点上的某一顶点的颜色的链；而交换连通的对角链只能改变某两个围栏顶点的颜色，而办不到从围栏顶点中空出颜色的目的。邻角链的交换可以断开双环交叉链；对角链和邻角链的交换都可以使构形转型。
1880年：
1880年，在坎泊证明之后的第二年，泰特（Tait）根据另外一个错误的猜想：“每个平面三次图都有哈密顿圈”，也给出了四色猜测的另外一个错误的证明。
这里的所谓平面三次图就是各个顶点都是3—度的平面图，即3—正则的平面图，也就是地图。
1890年：
1890年，在牛津大学就读的年仅29岁的赫渥特（Heawood）构造了一个含有双环交叉链的构形，是第一个与坎泊的证明不相符合的反例。大家都叫它H—图。该图中除了含有双环交叉链外，还含有经过了构形中的双环交叉链的两个末端顶点（关键顶点）的环形链。当时，赫渥特和坎泊本人也都解决不了这个H—图的4—着色的问题。虽然赫渥特没有能够解决他所构造的图的4—着色问题，但他却利用坎泊的颜色交换技术证明了一个比四色猜测弱一点的所谓的“五色定理”。
但是赫渥特的H—图只是反映了一种有经过了构形的关键顶点的环形链的情况的构形，还有另一种经过了构形中的双环交叉链的共同的起始顶点或交叉顶点的环形链的情况的构形没有反映出来。这两种情况也不可能在同一个图中同时表现出来，因为这两种环形链正好是一对相反链，不可能相互交叉，要求这两种环形链同时都经过同一个构形的关键顶点是不可能的。
看来，今后研究四色问题，主要就是研究含有双环交叉链的H—构形的可约性的问题了。要解决H—构形的可约性问题，就得使双环交叉链断开，使构形转化成可约的K—构形。而要断开双环交叉链，就只有要用到在后面我们还要讲到的“断链交换法”和“转型交换法”了。
这里需要顺便的介绍一下关键顶点：这里所说的关键顶点是指构形中的双环交叉链的共同的起始顶点和交叉顶点，以及双环交叉链的两个末端顶点，共四个。为什么说这四个顶点是关键顶点呢？因为含有双环交叉链是构成H—构形的必要条件。没有双环交叉链的构形一定不会是H—构形，但有了双环交叉链，却不一定都是H—构形，而只有可以连续的移去两个同色的构形才是H—构形。在这四个关键顶点中，只要有一个顶点的颜色发生了改变，构形就不会再是H—构形了。就可以把H—构形转化成K—构形而可约。
为了改变关键顶点的颜色，就得进行链的交换，为了防止交换时整个图中的所有着有某两种颜色的顶点的颜色都发生改变，就得要有与所交换的链呈相反链的另一条环形链，把所要交换的链分隔在环形链的内、外两侧，交换了该环形链一侧的相反链，另一侧的相反链仍然不变。而这条环形链则也必须是经过了构型的关键顶点的环形链。
赫渥特虽然没有能够改正坎泊证明中的错误，但他却对四色问题的研究仍然非常的投入，一致于在他生命的后60年里，一直都在研究它。虽然他没有直接的解决四色问题，但他却给出了一个多阶曲面上地图的着色公式γ≤＜（7＋√（1＋48n））/2＞（式中n是图或曲面的亏格，用＜ ＞表示其中的值向下取整）。图论大师哈拉里在他的《图论》（北京机械工业出版社，2006年中文翻译本）一书中说：当上式中曲面的亏格n为0时，其色数γ≤4就是平面（或球面）上地图的四色问题和四色猜测（这是因为平面和球面，以及平面图和球面地图的亏格都是0）。赫渥特是如何得到这个公式的，我们已无从知道。但我们现在是可以通过数学推导和解一元二次不等式的方法得到它（略）。
1921年：
1921年，埃雷拉（A Errera）又构造了一个含有经过了构形中的双环交叉链的共同的起始顶点（关键顶点）的环形链的构形，即E—图。该图与H—图一样，都是含有经过了构形的关键顶点的环形链的构形。这是对坎泊证明的第二个反例。
1935年：
1935年，美国人欧文•基特尔（Irving Kittell）在其论文《对已部分染色地图一组操作》中专门的研究了E—图，他已经看到了在使用α（或β）操作20次后（α操作和β操作实际上就是我们现在所说的转型交换法），产生了无穷的周期循环，构形却仍然是一个染色困局。但另外又用了交换一种叫做顶切链的方法（即ε操作）（也即我们现在所说的断链交换法）断开了双环交叉链，解决了E—图的4—着色（可约性）的问题。这是第一个给出E—图的4—着色的例子。
但欧文并没有给出结论说四色猜测就是正确的。因为他在文章最后又给出了三个他也不能解决的构形图。这三个图都是我们现在所说的不含有经过了构形的关键顶点的环形链的构形。其实这三个图都是很好4—着色的，用我们现在所说的转型交换法就可以解决问题。
现在，H—构形的各种类型都已经全部出现：H—图和E—图都属于含有经过了构形的关键顶点的环形链的构形；H—图和E—图又分别是该类构形中的不同的两个次一级类别的代表。而欧文给出的三个图都是一般的不含有经过了构形的关键顶点的环形链的构形。
笔者在从1985年开始的36年里对四色问题的研究中，对H—构形的研究表明：H—构形可以分为含有经过了构形的关键顶点的环形链的构形和不含有经过了构形的关键顶点的环形链的构形。前者用断链交换法解决，后者用转型交换法解决。前者中的两个次一级的类别，在使用断链交换法时，只是所交换的链是互相相反的。后者的转型交换次数从理论上讲一定是在有限的15次或20次之内，但从着色实践上看，一般都是不会超过5次的。这就是几十年来，笔者对四色问题的研究结果。证明了四色猜测是正确的。
1939年：
从1939年以后到1975年的36年里，四色猜测的证明主要是针对“假想地图”进行的4—着色，“地图”中的“国家”数由22个（美国数学家福兰克林（Philip Frankiln）1939年的研究）增加到52个（奥雷（Ore）1975年的研究），虽然都是只用了四种颜色，但都不能说明四色猜测就是正确的。
1946年：
泰特的证明提出后的66年之后，1946年著名的图论大师塔特（Tutte）构造出了一个没有哈密顿圈的平面三次图（即D—图），大家才知道泰特的证明又是错的。因为并不是所有的平面三次图都是有哈密顿圈的（D—图是泰特证明的一个反例）。虽然泰特的证明是错误的，但现在仍然还有另一个泰特猜想在存在：即平面三次图的可3—边着色，等价于平面三次图的可4—面着色。如果这个猜想是正确的，那么只要证明了任意的平面三次图（地图）都是可3—边着色的，四色猜测也就被证明是正确的了。
此后，对四色猜测的研究基本上就从对地图（无割边的3—正则的平面图）过渡到了对地图的对偶图——极大平面图的研究了。
1976年：
1976年，美国的阿贝尔（Appel）和哈根（Haesch）等人宣称他们用电子计算机证明了四色猜测，但没有得到数学界的一致公认。由于坎泊的证明中没有解决5—轮构形的可约性问题，所以阿贝尔他们就试图想用（5，5）构形和（5，6）构形（这两个构形都是有两个待着色顶点的构形）来替代5—轮构形，并认为这两个构形也都是不可避免的。但证明的结果却又说这两个构形又是不可约的。这是一个相互矛盾的现象，既然都是不可避免的构形，又都是不可约的构形，那怎么能说明四色猜测得到了证明是正确的呢？所以阿贝尔的《四色地图问题的解决》一文中只是说他们“解决了四色问题”和“四色定理得到证明”，而不说明他们“证明”的结论是什么，四色猜测道底是正确，还是不正确。
由于着色是一个顶点一个顶点的去着，当对一个待着色顶点着色后，剩下的另一个待着色顶点不也还是一个5—轮构形吗？所以说5—轮构形是不可以用别的构形替代的，也是替代不了的。
1990年：
1990年，英国的弗雷德·霍罗伊德（Holroyd F C）和罗伯特·格兰丁·米勒（Miller R C）等人的团队对H—图和E—图进行了研究。
因为H—图（构形）不能连续的移去两个同色，所以米勒他们就先移去一个同色，使构形转型。在连续两次转型后，H—图（构形）就转化成了一个可约的K—构形（见米勒等人1992年所写的，于1992年发表的《应该知道的赫伍德范例》（或《理应已知的赫伍德范例》）一文）。他们所用的方法就是我们现在所说的转型交换法。
由于他们自认为解决了H—图的着色问题，所以就产生了想用同样的方法解决四色问题的企图。但当他们遇到M—图（M—图是与E—相同的一个图。他们用的M—图是自已构造的，还是直接引用埃雷拉的E—图，我们无从知道，只知道M—图与E—图是一模一样的，着色也是相同的，应该是同一个图）时，便产生了20次转型为一个周期的无穷循环，永远也得不出结果来。于是他们就放弃了企图用这一方法解决四色问题的想法。而没有看到H—图和E—图中都含有经过了构形的关键顶点的环形链，也都可以用断链交换的方法去解决的这一共同特征。

（未完，接下一贴）

时空伴随者

二〇二一年？！

雷明85639720

是二○二一年呀！

雷明85639720

我的文章是二○二一年十二月十二日完成的呀！

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，