四色问题讲座 （第二期）

雷明85639720

四色问题讲座
（第二期）
雷  明
（二○二三年元月二十八日）


第一讲    什么是四色问题
1，四色问题，也叫四色猜测。四色问题研究的是有关对地图染色的问题。这是在一八五二年时，英国的绘图员法朗西斯在对英国地图染色时提出来的一个猜想。猜测是这样说的：把一个平面（或球面）任意的分成若干个区域，并对各区域染以不同的颜色，使得有共同边界线的两个区域都不用同一种颜色，最多四种颜色就可以够用了。猜测的提出至今已有一百七十多年的历史了，但仍没有从理论上证明其是否正确。
2，地图本身就是数学图论中的一种平面图。数学中把客观存在的事物用小圆点来表示（图论中叫顶点），把相互间有联系的事物用线（图论中叫边）联结起来，这样就构成了图论中所要研究的对象——图。即图是由顶点和边组成的。图中由若干条边和顶点交替相邻接所围成的区域叫面。显然，地图也是由顶点（三界点）和边（各个国家，省，县间的边界线）所构成的。若干条边界线所围成的区域就是地图中的不同的国家，省，县等。图论中，把各顶点所连结边的条数叫“度”，把除了在顶点以外，再在别的任何地方都再没有边与边相交叉情况的图叫平面图。地图中也有这种除在“三界点”以外再也没有边界与边界相交叉情况的性质，所以地图也是平面图。
3，地理学问题转化成了数学问题。在图论中，平面图还有其对偶图的说法。所谓的对偶图是指把原图中面的中心点作为新的顶点，把有边相邻的两个面所对应的新顶点，用边（该边一定要从两面之间的边上穿过去）连结起来所得到的新图就是原图的对偶图。这个对偶图也一定是一个平面图。同样的，地图的对偶图也一定是一个平靣图。看来，给地图中区域的染色也就是对其对偶图（平面图）的顶点的着色。当然，研究平面图的顶点着色，一定是比研究地图中面的染色要容易且方便得多。这就把一个地理学的问题转化成了一个数学问题了。
4，正规地图是一个连通的无割边的3一正则平面图。实际地图中的区划（区域）有一种是“一国多地”型的，即有“飞地”的区划（如美国和阿塞拜疆都是有飞地或是一国多地型的区划）。这种区划，其本身就是由多个互不相邻的区域构成的，完全是可以着上相同颜色的（同一区划的互不相邻的不同区域是应着上同一颜色的）。实际地图中，也有的顶点并不都是3度的“三界点”。在一般自然的情况（条件）下，一个顶点（三界点）都是只连有3条边界线的，但也有多于3条边界线的个别情况（如非洲有些国家，以及美国国内的有些州的边界线，并不是以自然地形地物来划分，而是以经纬度座标线来划分的，这就出现了有4条边界线相交于一点的情况。另外，若把“里海”看成是陆地上的一个“内陆湖”时，里海的中心点所连的边数（度）就是大于4的）。但这两种情况都是可以很容易的处理成只有＂三界点＂的地图的。把所连边数大于3的顶点附近的“一小片区域”，可以看成是一个边界数是等于4的“小区域”，而把里海也看成是海洋的1块飞地时，就都会产生等于或多于4个的新的“三界点”。另外地图中还有“国中之国”（如非洲的莱索托完全位于南非境内，只与南非一个国家相邻）的情况，其边界线是一个没有三界点的封闭环。世界地图中欧亚非大陆的地图，南北美洲大陆的地图，以及一个岛上有两个以上国家的地图；澳洲大陆的地图和南极洲大陆的地图，以及其他海岛国家的地图，都是各自呈现连通的，各个顶点都是连有3条不同边界线的地图，或是只是一条无三界顶点的封闭环的国中之国的地图。在着色时，把各个呈单连通的，相互间并不连通的部分，可以单独的分开来处理，并可以做到互不影响。在图论中，还把各顶点的度都相同的图又叫做正则图，所以在研究四色问题时，就规定把不含“国中之国”和不含“一国多地”的地图，以及不含大于3度顶点的连通地图叫正规地图。所以说正规地图就是无割边的3—正则的平面图。
5，四色问题的拓展。地图是一种特殊的各顶点都是3—度的无割边的平面图，其对偶图也是一种特珠的各面都是3—边形面的极大平面图。只有在证明了地图的对偶图——极大图平面图——的顶点着色时四种颜色就一定够用了的情况下，地图的四色猜测才是正确的。而对于一个只用了不大于四种颜色着色的极大平面图来说，通过”去顶”或“减边”等手段转化成的任意非极大平面图和非连通平面图的色数一定只会减小，而不会再增大。这也就把一个只针对地图中面的染色的四色猜测，拓展到了对任意的平面图的顶点着色中去了。即对任意平面图的顶点着色时，最多四种颜色也就够用了。
6，为什么要对地图中的面进行染色。本讲最后一个问题，再讲一下地图为什么要染色，以及实际的地球地图的色数问题。应该说地图染色与不染色，对地图的使用都是沒有什么影响的。地球上的国与国，省与省之间本来就是沒有可以看得见的边界线的。地图上的边界线也都是人为的在地图中加上的。本来加上去的边界线就很细，再加上地球地图上还要显示出地球上的山川河流等地形地物，以及显示出人为的建筑物（如长城，公路，铁路，水库等），再加上用文字进行标注后，就使得国与国，省与省等区域之间的边界线不可能清楚的看出。特别是边界线犬牙交错的复杂地段，可以说根本就不可能看清楚各国，各省间的相互关系了。如果把各国，各省所在区域用较浅的不同颜色染上色，又不影响地形地物及文字标注的清晰，各国，各省间的相邻关系一定可以变得很清晰，这不就更好了吗。于是就产生了对地图的染色这一项工作，也就有了坎泊对四色猜测的提出一亊。我们在研究四色问题时一般用的虽然都是正规地图，但它还是与实际的地球地图有差别的。最大的差别就是地球上有一个特殊的区域是“海洋”，是水域，与其他的陆地区域是有着明显的本质区别的。总不能把陆地上的某些区域与海洋的“水”域区域染成同一种颜色吧！这样，实际地球地图的色数就比理论上的正规地图的色数至少就要大1。月球上沒有海洋，全是陆地，无论怎么划分月球表面，月图最多四种颜色就一定够用了。

第二讲   平面图的不可避免构形
1，平面图构形的定义。研究解决四色猜测的第一位学者是英国的坎泊，他在一八七九年提出并证明了任何地图中至少都一定存在着一国与两国相邻，一国与三国相邻，一国与四国相邻和一国与五国相邻这四种情况中的一种。坎泊把这四种情况叫做地图的不可避免构形。而我则认为，从平面图来讲，说得更具体点，构形的定义应该是“还剩下一个顶点未进行4一着色的图”。构形中未着色的顶点叫待着色顶点，与待着色顶点有边相邻的顶点叫围栏顶点。只要把该构形中的待着色顶点着上了图中已用过的四种颜色之一，这个图的4—着色问题也就解决了。这两个关于构形的定义基上是相同的，只是后者比前者更具体，更明确一些。
2，平面图的不可避免构形。坎泊是直接就定义了地图的不可避免构形。而我则是先定义了平面图的构形（见上面），再在这里才将进一步定义什么是平面图的不可避兔构形的。可以看出，在这里坎泊是把不可避免构形与构形混为一谈了。在图论中，可以证明任何平面图中都一定至少存在着一个顶点的度是小于等于5的。这也就说明了所有顶点的度都是大于等于6的平面图是不存在的。这样，我们在给任何平面图着色时，就总是可以把最后要着色的待着色顶点放在度是小于等于5的顶点之上。只要研究度是小于等于5的构形的4—着色问题就可以了，而不需要再研究度是大于等于6以至于无穷大时的构形的4—着色问题了。把度小于等于5的构形就叫平面图的不可避免构形。这与坎泊定义的地图的不可避免构形是一致的。这也就把一个研究对象是无穷多的问题转化成了一个有穷的问题了。
3，构形的多级分类。有不可避免的构形，相应的也就应有可以避免的构形。上一问题实际上就是把构形分成了这样的两类了。可以说这就是对构形的一级分类。可以避免的构形就可以不再去研究它的解决方法了。
4，构形多级分类的原则。多级分类，各级都只分两类。非此即彼，以防遗漏。两类中有一类的4—着色问题，在本级分类中就可以解决，另一类留待下一级分类时继续分类。等到哪一级分类中的两类都可以在本级分类中得到解决时，多级分类就宣告结束。这时，平面图中的各类不可避免构形也就都是可约的了，四色猜测也就证明是正确的了。
5，构形的二级分类。把不可避免构形分成可以给待着色顶点直接着色的构形（度小于等于3的构形以及围拦顶点占用颜色数小于等于3的构形）和不可直接着色的构形（围拦顶点已占用完了四种颜色的构形）。前者是可约的构形，都可直接着色。后者中就只有4—度的和5—度的构形了。再进一步去分类。
6，构形的三级分类。把不可直接着色的构形再分成坎泊已证明过是可以直接从围栏顶点中空出颜色给待着色顶着上的可约的K—构形和不可直接从围栏顶点中空出颜色给待着色顶点着上的H—构形（该构形是一八九〇年由赫渥特构造出来的）两类。前者用坎泊链法（即坎泊用过的可以从围栏顶点中空出颜色的颜色交换技术）进行解决。后者等下一级再分类。
7，坎泊的颜色交换技术简介。由两种颜色交替的进行着色所构成的顶点一边一顶点的序列叫做“色链”（简称“链”）。把围栏顶点的两个对角顶点的颜所构成的链叫对角链。对角链对于两个对角是连通的时，称为连通链，否则就是不连通的对角链。坎泊链法中所交换的链一定是不连通的对角链。只有这样，才能空出该两个对角顶点的一种颜色来。连通链是不可交换的，即就是交换了，也是不可能空出颜色来的。

第三讲    H一构形的分类与一着色
1,H—构形中链的特点。若一个H—构形的峰点顶点是A色，其两边的两个同色顶点是B色，那么，其他的两个顶点分别就只能是C色和D色了。既然是H—构形，那么构形中必有连通的A—C链和连通的A—D链，且两链在中途又有相交叉的顶点A。两链可相交叉的原因是因为该两链中有一种共同的颜色A。把这样的有一种颜色相同的两条链就叫做相邻链。相邻链是可以相互穿过（交叉）的。同样的把没有相同颜色的两条链叫相反链。而相反链却是不能相互穿过（交叉）的。H—构形就是因为有了连通的A—C链和A—D链，所以两链都是不能进行交换的，也是空不出A，C，D三色之一的。又由于B—C链和B—D链又是不能连续进行交换的，所以也就不能连续的空出两个同色B。由A，B，C，D四种颜色可能构成的A—B，A—C，A—D，B—C，B—D和C—D六种色链中，现在己有A—C，A—D，B—C和B—D四种链不能交换了，可交换的就只剩下经过围栏邻角顶点的邻角链A—B链和C—D链了。这是两条相反的色链。从H—构形中还可以看出，A—C链和A—D链两条连通链的共同起始顶点A（即峰点顶点A）以及这两条连通链的交叉顶点A，还有这两条连通链的末端顶点C和D这四个顶点都是关键的顶点。其中只要有任何一个顶点的颜色发生了改变，图中就不再存在双环交叉链了。因为没有了构成H—构形的必要条件，所以H—构形就转化成了可约的K—构形了。正好这四个关键顶点也都是分布在可以交换的邻角链A—B链和C—D链之上的。需要交换的也正好就是这两条链。只要交换了这两条链中的任何一条，以上四个关键顶点至少就会有一个顶点的颜色就会发生变化。双环交叉链就会断开，H—构形就会转化成可约的K—构形。但这种交换是要有条件的，即交换一条邻角链时，必须要有另一条邻角链是呈环形的，且把要交换的邻角链分隔在环内和环外，成为互不连通的两部分。只有这样，交换后才能保证双环交叉链断开。
2，构形的四级分类。把H一构形再分成有经过了围栏邻角顶点的环形链，且该环形链能够把另外两种颜色构成的邻角链分隔在环内和环外，成为互不连通的两部分的有环形链的H—构形和无经过围栏邻角顶点的环形链的构形。前者——有环形链的H—构形解决的办法是交换环形链内,外的另一对条邻角链的断链方法，使H—构形转化成可约的K—构形。有A—B环形链者交换C—D链进行断链，有C—D环行链者交换A—B链进行断链。然而后者——无环形链的H—构形，既沒有可交换的邻角链A—B或C—D和可提供交换条件的环形链，也没有再进行更细化的分类的条件。怎么办呢？既然B—C链和B—D链不能连续的交换，也不能空出两个B来。那我们就先交换其中的一条，先空出一个B来，使构形进行转型。然后再在新的构形中寻求解决的办法。这就是转型交换法。若新的构形还不能解决问题时，就继续的转型下去。
3，断链交换法简介。断链交换法是相对于可从围栏顶点中空出颜色的坎泊链法而言的。交換的是围栏顶点的邻角链，交換的路径可以经过围栏顶点，也可以不经过围栏顶点。但交换后并不会空出颜色来给待着色顶点，而只是把H—构形转化成了可约的K—构形。还需要进行一步坎泊链法的交换，才能空出颜色来给待着色顶点。断链法是解决有环形链的H—构形的专用方法。而坎泊链法所交换的链全都是不连通的对角链，且所交换的链的起始顶点还必须是该对角链上的一个围栏顶点。
4，转型交换法简介。不能直接给待着色顶点着色的5—度构形，围栏顶点一定是占用完了四种颜色的，且有一种颜色是用了两次的。用了两次相同颜的顶点中间所夹的顶点就是不可直接着色的5—度构形的峰点顶点。每一个不可直接着色的5—度构形都有自已的峰点顶点和两个同色顶点。所谓的转型交换，就是能使构形峰点的位置和颜色都发生变化的交换。转型交换所交换的链只能是有关两个同色顶点的链中的一条。转型交换可以交换对角链，也可以交换邻角链。由于不可直接着色的5—度构形有两个围栏顶点的颜色是相同的，所以，先从那一个同色顶点开始交换，所得到的结果不但是不同的，而且在连续转型的中途也是不能逆转的。因为逆转后，又会按原路返了回去，就又回到了本次转型之前的构形状态。因此又有逆时针方向转型与顺时针方向转型的两个方向转型之分。交换对角链进行转型时，峰点和两个同色顶点的位置和颜色都在发生变化。峰点的颜色可以在四种颜色之间变化，峰点的位置可以在五个围栏顶点之间变化。需要连续转型20次（4×5＝20）时，峰点的颜色与位置才能同时返回到转形开始时的初始状态。后面再继续转型时，每隔20次转型就会出现一次与初始构形相同的构形。因此，这个20次转型就是交换对角链进行转型时的固有循环周期。而交换邻角链进行转型时，虽然峰点和两个同色顶点的位置也都在发生变化，但两个同色顶点的颜色却是不变的。而只有峰点的颜色是在三种颜色间进行变化的，峰点的位置仍然是在五个围栏顶点之间变化的。所以交换邻角链进行转型时的固有循环周期是3×5＝15次转型。
5，无环形链的H—构形转型着色的实践。我们虽然对大量的无环形链的H—构形用连续转型的方法进行了转型，且一般都是在极有限的转型次数内得到了可4—着色的结果，但由于该类构形也是无穷多的，也不可能对其全部进行着色，也就不能直接下结论说该类构型就一定都是可以在有限的转型次数之内解决问题的。四色猜测是否正确，还是不能最终定论。还必须用原命题的逆否命题与原命题是同真同假的逻辑关系进行绝对的理论上的证明，才能得到四色猜测是否是正确的最后结论。（下一讲专门讲这一问题）。

第四讲    无环形链的H一构形最大转型次数上界值的确定
1,无环形链的H—构形的转型次数一定是有限的。由于该类构形也是有穷多的，所以也是无法一个一个的着色完毕的。还必须用原命题的逆否命题与原命题是“同真同假”的逻辑关系进行推理证明。着色实践中得出的原命题是“无环形链的H一构形一定都是可以通过有限次转型就可以解决问题的”。根据逆否命题的条件是原命题的结论的否定，以及逆否命题的结论又是原命题的条件的否定的关系，这里的逆否命题应该是“无穷次转型也不能解决问题的构形一定不是无环形链的H一构形”，那么这就应该是有环形链的H—构形或是可约的K—构形。这个逆否命题是假是真呢？是否成立呢？回答是真的，是成立的。一九二一年埃雷拉构造的E—图构形就是一个无穷次转型也解决不了问题的构形（但因E—图构形又是一个有环形链的H—构形，还是可以通过断链法解决问题的。一九三五年欧文已给出了E—图构形的断链法解决方法。只是当时欧文把这一方法叫做正切链法）。逆否命题是真的，其原命题“无环形链的H一构形一定都是可以通过有限次转型就可以解决问题的”命题也就是真的了。这就证明了任何无环形链的H一构形都是有限次转形就可解决问题的构形了。
2，无环形链的H—构形最大转型次数的上界值。只证明了转型次数的有限性，还是不够的。还必须明确指出最大转型次数的上界值。因为无上界值的有限仍可能是无限的，所以还必须证明这个上界值具体是多少。任何一个不可直接着色的5—度构形在转型着色时，在其固有循环周期（20次转型）之内若能解决问题，则该构形一定是有限次转型的构形。否则，转型次数大于20次，还不能解决问题时，无论第20次转型所得的构形是否与初始构形相同（目前构形的围栏顶点与初始构形的围栏顶点的颜色和位置一定是完全相同的，但目前构形的其他顶点的颜色却不一定与初始构形完全相同），只要能在40次转型之内能解决问题的，该构形也一定是有限次转型的构形。但若在40次转型之内仍解决不了问题时，该构形就成了无穷次转型也解决不了问题的构形了。第20次转型所得构形与初始构形相同者是无穷周期循环转型的构形（象E—图构形那样的构形一样。一个不可直接着色的单纯5—轮构形，也是这样的无穷周期循环转型的构形）。第20次转型所得构形与初始构形不同者则是无穷不循环转型的构形（如在一个不可直接着色的单纯5—轮构形的某些围栏顶点上，还悬挂有其他顶点的构形，就是这种无穷不循环转型的构型）。但这两种结果都是无穷转型的构形，是与无环形链的H—构形都是有限次转型的构形的结论是矛盾的。所以任何一个无环形链的H—构形的转型，一定都会在第40次转型前结束转型的。转型结束了，该构形的可—4着色问题也就解决了。这个40次转型就是无环形链的H—构形最大转型次数的上界值。到此也才真正的证明了无环形链的H—构形是可约的或者说是可4—着色的。
3，平面图的各种不可避免构型都是可约的。以前我们证明四色猜时用的方法是对平面图的不可避免构形的多级分类法，把不可直接着色的5—度构形分成K—构形和H—构形，H—构形再分成有环形链的H—构形和无环形链的H—构形两类，共三大类。而这里我们又从另一个角度出发，把不可直接着色的5—度构形分为了有限转型的构形和无穷转型的构形两类。这两种分类方法共同的把不可直接着色的5—度构形又分成了6个部分。属于有限转型的三部分分别是：第①部分既是有限转型的构型又是K—构形。可以用转型法解决，也可以用坎泊链法解决。但用坎泊链法要快一些。第②部分既是有限转型的构形又是有环形链的H一构形。可以用转型法解决，也可以用断链法解决。但用断链法快一些。第③部分既是有限转型的构形又是无环形链的H一构形。只能用转型法解决。属于无穷转型的另外三部分分别是：第④部分既是无穷转型的构形又是K—构形。只能用坎泊链法解决。第⑤部分既是无穷转型的构形又是有环形链的H—构型。只能用断链法解决。第⑥部分应该既是无穷转型的构形又是无环形链的H—构形。但由于无环形链的H—构形已经都是有限转型的构形了，根本就不存在无穷转型的情况。所以这一部分中就不存在无穷转型的构形了。这第⑥部分实际上就是一个没有任何元素（构形）的空集。现在，平面图的任何不可避免构形都已经是可约的了。四色猜测是正确的。
4,四色猜测的最简单证明。能用逻缉推理的方法证明无穷多的无环形链的H一构形都是有限次转型的构形，也就能用同样的方法证明无穷多的平面图的色数都是小于等于4的。从大量的着色实践中得出的原命题是“任何平面图的着色数都不会大于4”，其逆否命题应是“色数大于4的图一定不是平面图”。这个逆否命题是真的。的确，完全图K5和含有K5团作分子图的图着色时，必须用5种颜色，色数是5。但这些图均不是平面图而是非平面图。库拉图斯基定理说的就是“含在K5和K3，3作分子图的图一定都是非平面图”。既然逆否命题是真的，那么原命题“任何平面图的着色数都不会大于4”也就应该是真的了。四色猜测也就证明是正确的了。

第五讲    最后的总结
1，四色问题因对地图染色而引起。又因为地图本身就是数学图论中的3一正则平面图，所以地图的对偶图就是一个极大的平面图。因此对地图面上的染色就转化成了对极大平面图的顶点着色。一个地理学中的问题也就转化成了一个数学问题。如果证明了地图四色猜测是正确的，那么一个用了不大于4种颜色着色的极大平面图，在经过了去顶或减边等运算后所得到的任意平面图的色数就只会减少，而不会再增加。这也就产生了平面图的四色问题。
2，给任何平面图着色时，总存在着最后要着色的一个顶点。这就引出了“构形”的概念。把只剩一个顶点未进行4—着色的平面图就叫构形。由于任何平面图中总存在着至少一个顶点的度是小于等于5的，所以总可以把最后要着色的待着色顶点放在度是小于等于5的顶点之上。这样构形就可分成可以避免的构形（度是大于等于6的构形）和不可避免的构形（度是小于等于5的构形）两类。另外再根据构形围栏顶点所占用的颜色数是否等于4，构形还可再分成可直接着色的构形（围栏顶点占用颜色数小于4）和不可直接着色的构形（围栏顶点占用颜色数等于4）两类。这就把构形的度由可以是无穷大转化成了只研究小于等于5的个别构形了。无穷的问题就转化成有穷的问题了。
3,既是不可避免的构形又是不可直接着色的构形，还可分成K—构形（即可直接从围栏顶点中空出颜色给待着色顶点的构形。坎泊一八七九年已用坎泊链法证明了K—构形都是可约的）和H—构形（即不可直接从围栏顶点中空出颜色给待着色顶点的构形。这种构形是被坎泊证明时所遗漏掉了的不可避免的构形，是赫渥特在一八九〇年构造的，但至今又一直没有解决能否可4—着色的构形）。
4，我们现在研究四色问题时，又把H—构形分成有环形链的构形和无环形链的构形两类。前者用断链法解决，后者用有限次的连续转型法解决。至此，所有平面图不可避免的构形都是可约的了，四色猜测也就可用着色实践的方法证明是正确的了。
5，不但用着色方法能证明任意平面图的色数都不大于4，也可用逻辑推理的方法证明任意平靣图的色数也不大于4。这就从实践和理论两个方面都证明了四色猜测是正确的。

雷  明
二○二三年元月二十八日于长安

bieopi

xxxxxxxxxxxx！