不可避免构形可约法证明四色猜测

雷明85639720

不可避免构形可约法证明四色猜测
雷    明
（二〇二三年四月十五日）

【摘  要】：四色猜测也叫四色问题。是专门研究关于对地图中区划的染色问题的。由于地图是属于图论中的“无割边的3—正则的平面图”，所以给地图的面（区划）上的染色也就是对地图的对偶图——极大平面图的顶点着色。极大平面图的四色问题解决了，不仅只是证明了地图四色猜测是正确的，同时还可说明任意平面图的四色猜测也是正确的。因为能够可4—着色的极大平面图，经去顶和减边后，所得到的任意平面图的色数只会减少而不会再增加。
【关键词】 四色猜测  四色问题  待着色顶点  构形  不可避免顶点    颜色交换技术  坎泊链法  构形可约  可约构形  关键顶点  双环交叉链  转型交换法  着色  平面图  度

     1，待着色顶点与构形，以及解决四色问题的关键。
    ①待着色顶点与构形。在给任何平面图着色时，都一定要遇到最后一个要着色的顶点，这就是待着色顶点，用Ⅴ0表示。与V0相邻的顶点都叫做围栏顶点。把这样的只有一个顶点未着色的图就叫做构形。平面图中的任何一个顶点都可成为待着色顶点。
    ②解决四色问题的关键。待着色顶点V0能否着上图中已用过的四种颜色之一，是解决四色问题的关键。想办法把V0着上四种颜色之一的过程，也就是证明四色猜测成立的过程。
     2，终局构形与困局构形。
     ①条件。若围栏的顶点数（即待着色顶点Ⅴ0的度）为d，则有d≥0。又若围栏顶点所占用的颜色数为c，则有c≤4。
     ②终局构形。当d＜4或c＜4时的构形，就是终局构形。Ⅴ0是一定能够直接着上四种颜色之一的。这样的Ⅴ0就是终局顶点。
     ③困局构形。当d≥4和c＝4时的构形，则是困局构形。其困局顶点Ⅴ0只是暂时还不能着上四种颜色之一的。这样的着色困局必须经过待着色顶点的移动，把度为d≥6的困局顶点Ⅴ0转化成度为d≤5的困局顶点V0，然后再通过坎泊的颜色交换技术，才能着上四种颜色之一。
    3，不可避免顶点与待着色顶点移动。
    ①不可避免顶点。任何平面图中都一定存在着至少一个度是d≤5的顶点，这就是平面图的不可避免顶点。这就是说，平面图中可以不含有度是d≥6的顶点，而不可能不含有度是d≤5的顶点。待着色顶点落在不可避免顶点上的构形也就叫不可避免构形。度是d＜4的着色终局构形的终局顶点V0，是可以直接着上四种颜色之一的。有了不可避免顶点，着色时总是可以把待着色顶点放在不可避免顶点之上的。
    ②待着色顶点移动。把围栏顶点中使用次数最少的那种颜色给V0着上，就会在围栏顶点中新产生一个或多个待着色顶点V0，这就是待着色顶点的移动。不断重复这一操作过程，就可以把度是d≥6的着色困局构形的困局顶点Ⅴ0移动到图中的任何一个顶点上，也包括不可避免顶点在内。待着色顶点移动的目的，就是想把着色困局构形中围栏顶点占用的颜色数由c＝4的困局顶点变成围栏顶点占用颜色数是c＜4的终局顶点，再直接进行着色。
4，颜色交换技术与构形可约。
①颜色交换技术。把用两种颜色交替着色的道路叫做色链，简称链。交换链中两种颜色所着的位置，可以达到改变链中任一顶点颜色的目的，这就是颜色交换技术。是坎泊于1879年提出并首先开始使用的。
     ②不可避免构形的可约。运用该颜色交换技术，想办法从度是4或5的着色困局构形的围栏顶点中，空出一种颜色来给待着色顶点着上，是一定可以办到的（见下面各节的内容）。这就是构形可约的过程，这种构形就叫做可约构形。这种使构形可约的方法就是坎泊链法，或叫可空出颜色的交换方法。只要不可避免构形都能可约，四色问题就解决了，四色猜测也就是正确的。因为其他d≥6的构形都是可以避免的。
     5，关于链的有关概念。
    ①对角链与邻角链。由构形围栏两对角顶点的两种颜色构成的链叫对角链。由围栏的两邻角顶点的颜色构成的链叫邻角链。这两种链都可以使用颜色交换技朮。对角链交换以空出颜色，邻角链交换以改变围栏顶点的着色顺序，从而改变构形的类型。
    ②连通链与非连通链。两对角顶点的对角链在围栏顶点外相连通时叫连通链。否则是不连通链。连通链与待着色顶点构成了一个环（圈）。不连通的对角链是可以使用颜色交换技术的，并使该链位于围栏上的那个顶点的颜色发生改变，与其对角顶点成为相同的颜色，使围栏顶点占用的颜色减少一种，给待着色顶点着上。这就是交换不连通链可从围栏顶点中空出一种颜色的原理。而连通链则是不能交换的，因为它不能从围栏顶点中空出颜色来。
    ③相反链与相邻链。两条链总共占有四种颜色时，叫做相反链，即两链没有共同的颜色。两条链总共占有三种颜色时，叫做相邻链，两链有一种共同的颜色。相反链只能单独存在，不能相互交叉，一条是连通链时，另一条交换后可以空出颜色。相邻链中有共同的颜色，所以可以互相穿过（即交叉）。两相邻链的起点是同一顶点，且只有一条是连通链时，另一条交换后也可空出颜色。由于相邻链既可以同起点，又可以再交叉，所以就有后面将要讲到的双环交叉链。
     6，K—构形与H—构形。
    ①坎泊的K—构形都是可约构形。用A，B，C，D代表四种颜色，把不含有A—C和A—D双环交叉链的不可避免构形统统叫做K—构形（即坎泊1879年研究过的构形），它们经过对角链的交换，都是可约的。但是坎泊的研究中却漏掉了含有A—C和A—D双环交叉链的这种不可避免的构形。
    ②赫渥特的H—构形也都是可约的。坎泊证明中所遗漏的构形在1890年由赫渥特发现并构造了出来。但当时却并沒有解决对其应如何4—着色的问题。把与赫渥特构造的同样都有双环交叉链的5度着色困局构形统一叫做H—构形。这种构形也都是可以转化成可约的K—构形的，也都是可约的（见以下的证明）。
    ③构成H一构形的必要条件。有没有双环交叉链，是H—构形与K—构形的最大区别。有双环交叉链是构成H—构形的必要条件。沒有双环交叉链不能构成H—构形，但有了双环交叉链却不一定都是真正的H—构形。
    7，H一构形的特点。
    ①H—构形。由于双环交叉链是不可能出现在4度构形中的，所以H—构形就只有5度的不可避免构形一种。设H—构形围栏顶点的着色顺序是1B—2A—3B—4D—5C—1B，2A是峰点顶点。由于A—C和A—D是双环交叉链，所以都是不能交换的，也就空不出A，C，D三色之一。
    ②真正的H—构形。在H—构形中，有些构形是可以通过可空出颜色的颜色交换技术，连续的交换关于B的两条对角链，移去两个同色B，给待着色顶点着上的，是具有K—构形的可约性的。但还有一些构形仍是不能移去两个同色B的。这种构形才是真正的H—构形，似乎是待着色顶点无色可着了。
    ③关键顶点。要解决H—构形的可约性，就必须把H—构形转化成可约的K—构形，断开双环交叉链，排除掉构成H—构形的必要条件。但要断开双环交叉链，就必须改变双环交叉链的共同起始顶点2A（或交叉顶点A）或者两链各自的末端顶点4D和5C的颜色。看来这四个顶点都是关键的顶点。
8，用断链交换法把有环形链的H—构形转化成可约的K—构形。
②链交换法。上面已经谈到了H—构形的四个关键顶点，只要攺变了其中任何一个顶点的颜色，都会使双环交叉链断开，构形转化成K—构形。改变两链的共同起点2A和交叉顶点A的颜色，需要交换的链是A—B链，而改变两链的末端顶点的颜色需要交换的则是C—D链。A—B链和C—D链是一对相反链，是不能相互穿过的，而对于围栏顶点来说都是邻角链。如果这两条链有一条是环形链时，则另一条一定是被分隔在环的两侧，互不连通。交换环内一侧的另一条邻角链，就可使双环交叉链断开，成为K—构形。有环形的C—D链时，就交换A—B链。有环形的A—B链时，就交换C—D链。这种方法就叫断链交换法，因为它把双环交叉链断开了。
    ②赫渥特H—图的4—着色。1890年赫渥特构造的H—图中，有经过了A—C和A—D两链的末端顶点的环形的C—D链，把两链的共同起始顶点2A和交叉顶点A分隔在了C—D环的两侧。1992年前后，雷明与董德周分别就是用交换A—B链的办法解决了该图的4—着色问题的。
    ③埃雷拉E—图的4—着色。而1921年埃雷拉构造的E—图中，却有经过了A—C和A—D两链的共同起始顶点2A的环形的A—B链，把经过了两链的末端顶点的C—D链与其他的C—D链分隔在了A—B环的两侧。1935年欧文则是用交换C—D链的办法解决了该图的4—着色问题的。在1992年敢峰也用同样的方法解决了E—图的4—着色问题。
    9，用转型交换法把无环形链的H—构形转化成可约的K—构形。
    ①转型交换法。在5度的着色困局构形的围栏顶点中，一定有两个顶点是用了相同颜色的，叫做两个同色顶点。两个同色顶点之间的单色顶点就是构形的峰点顶点。如果交换了关于两个同色的任一条链，构形峰点的位置和颜色就会发生变化，这种变化就叫构形转型，造成这种转型的交换就是转型交换，这样的交换方法就叫转型交换法。
    ②无环形链的H—构形。真正的H一构形中，除去有环形链的构形，就是无环形链的H一构型了。这种构形，由A，B，C，D四种颜色可能构成的六种链中，已有A—C链和A—D链因是连通链而不能交换，A—B链和C—D链又因均不是环形链而都不可对其相反链进行交换，而B—C链和B—D链又不能两条链连续的交换，似乎就是无法再交换了。有办法。既然不能连续交换，那就先只交换一条，使构形转型，看转型后的构型是什么构形。这就是无环形链的H—构形能够进行转型交换的条件。
    ③无环形链的H—构形的转型次数必须是有限的。若转型交换后的构形是可约的K—构型，或者是有环形链的H—构形时，问题都就得到了解决。否则，就继续进行同方向的转型，直到可约为止。什么时候结束转形呢？必须要有一个转型次数的上界值。只有这样才能彻底的证明四色猜测是否证确。由于这个原因，就必须再寻找最大转型次数的上界值。
    10，无环形链的H—构形转型时最大转型次数的上界值。
    ①着色实践所得出的结论。通过对大量的无环形链的H—构形（但仍是有限的，个别的）进行的转形交换，都总是在有限次的，甚至是极少次数的转型次数内，都可以对其进行4—着色。但无环形链的H一构形却也是有无穷多的，永远也是无法着色完的。无法着色完就不能说明四色猜测是正确的。要证明无环形链的H—构形的转型次数都是有限的，还必须利用逆否命题与其原命题是“同真同假”的逻辑关系，进行从个别到一般的推理证明。
    ②无环形链的H—构形的转型次数有限性的证明。从着色实践中得出的原命题是“任何无环形链的H—构形转型时的转形次数都是有限的”。其逆否命题则是“一个经无穷多次转型始终都仍然是H—构形的构形，一定是一个不是无环形链的H—构形”，也即一定是一个“有环形链的H—构形”。这个逆否命题是真的。的确是有这样的一个图——埃雷拉构造的E—图，就是经无穷次周期循环转型后，仍然是一个H—构型的构形，其中的确也有环形的A—B链。依据逆否命题与其原命题是“同真同假”的逻辑关系，则原命题“任何无环形链的H—构形转型时的转型次数都是有限的”结论是正确的。
    ③H一构形转型时的固有周期。H—构形对角链转形时的构形类型是在BAB型，ABA型，DCD型和CDC型四种类型间变化的，峰点是在五个顶点间变化的，某个顶点从转型开始时的BAB型的峰点A，经转型又返回到BAB型的峰点A时，总共是转型了4×5＝20次，这就是H—构形对角链转型时的固有周期。H—构形邻角链转型是在BAB型，BDB型和BCB型三种类型间变化的，峰点仍是在五个顶点间变化的，这种转型的固有周期则是3×5＝15次。
    ④无环形链的H—构形转型时最大转型次数的上界值。对无环形链的H—构形无论进行对角链转型还是邻角链转型，每一次转型都有三种可能的结果。一是得到一个可以连续的移去两个同色的K—构形，再进行两次可空出颜色的交换，即可进行4—着色。二是得到一个有环形链的H—构形，再进行一次断链交换和一次可空出颜色的交换，也就可以4—着色了。三是得到的仍是一个H—构形，需要继续进行转型。研究最大转型次数的上界值，就得假设每次转型所得的构形都是H—构形。当转型次数达到了H—构形转型的固有周期后，所得构形各顶点的着色全部都反回到转型前的初始状态时，转型再经过一个固有周期后，构形再次反回到初始状态，这时才能确定所转型的构形是无穷周期循环转型的构形（如埃雷拉E—图那样）。当转型次数达到了H—构型的固有周期后，所有顶点的着色并沒有都反回到初始状态时，转型再经过一个固有周期后，构形同样也就不可能反回到第一个固有周期时的状态。同样，也只有这时也才能确定所转型的构形是一个无穷不循环转型的构形。但上述这两种结果都不是我们所期望的，也是不应出现的。因为我们已经证明了无环形链的H—构形的转型次数是有限的，而不是无穷的。所以无环形链的H—构形的转型必须在第二个固有周期来临之前结束。即无环形链的H—构形转型时的最大转型次数的上界值是：在用对角链转型时是40次，在用邻角链转型时是30次。
    11，四色猜测是正确的。
现在已证明了在各种情况下的不可避免构形中的待着色顶点都是可着上四种颜色之一的。所以四色猜测也就是正确的。

雷    明
二〇二三年月十五日于长安

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，