四色猜测证明中的专用术语——兼论四色猜测的证明

雷明85639720

四色猜测证明中的专用术语
——兼论四色猜测的证明
雷  明
（二○一八年八月二十六日）
（图发不上来，请到《中国博士网》的《数学论坛》栏中去看吧。由于这里也不能发别的网的网址，所以也不能给读者网址，只是在《中国博士网》中的文章题目与这里的相同，读者去自已找吧）

我在网上看到一些热心研究四色问题的爱好者朋友，可能是对图论学得很少，或是根本不懂图论，所以就出现了在图论中本来就已有的术语，他们却不去使用，而是用了自已另外定义的新术语，但又定义得不明不白的，使人看他们的文章很是吃力，很费劲。这样交流起来就很困难，所以我就以我自已对图论的了解，把有些术语、名词，解释如下，以供爱好者朋友们参考。
一、图与着色
1、1  图与图的三大要素：
图：图是由若干个顶点（用小园点表示）和顶点与顶点间的连线（即边）构成的集合。或者更直观的说，图是由顶点与边构成的网络。
图的三大要素：
顶点：这是第一位的。没有顶点，就不可能成其为图。也没有无顶点的图。
边：有时也叫线或弧。边是顶点与顶点间的连线。没有顶点，也就没有边。
面：一个由顶点—边—顶点构成的封闭的序列，就是一个圈，该圈所围成的部分就是面。或者说面就是网络中的网眼。
图中三大要素间的相邻关系：有相同要素间的相邻和不同要素间的相邻。相同要素间的相邻叫“相邻”或“邻接”，不同要素间的相邻叫“相关”或“关联”，这些相邻关系统称为“相伴”。
两顶点相邻：是因为它们之间有一条边。
两条边相邻：是因为它们都连接着同一个顶点。
两个面相邻：是因为它们之间有一条共同的边界线。
顶点与边相邻：是因为它们有一个共同的顶点。
顶点与面相邻：也是因为它们也有一个共同的顶点。
边与面相邻：也是因为它们有一条共同的线段（边）。
1、2  图的亏格：
平面图与非平面图：图中除了在顶点处有边与边相邻外，其他任何地方再没有边与边相交叉情况的图，就是平面图。否则就是非平面图。
图的亏格：图的亏格就是图所能嵌入的曲面的最小亏格。任何一个图都可以画在不同亏格的曲面上，且边与边在顶点以外不交叉，这就叫嵌入。这些不同亏格的曲面中，总有一个曲面的亏格是最小的，这个最小亏格的曲面的亏格，也就是嵌入其上的这个图的亏格。
曲面的亏格：球面的亏格是0，轮胎面（环面）的亏格是1，“8”字形面包圈曲面（眼镜匡面）的亏格是2，等等。
平面的亏格：在拓朴学中，球面与平面是可以相互转化的，所以球面和平面的亏格都是0。
平面图和非平面图的亏格：平面图可嵌入的曲面的最小亏格是0，即球面或平面。所以平面图的亏格是0；其他的非平面图都不能嵌入在平面或球面上，所以非平面图的亏格都是大于0的。
1、3  各种各样的图：
平面图的对偶图：把平面图中的面的中心点作为新的顶点，把有边界线相邻的两个面中的新顶点（中心点）用边连接起来所得到的新图，也是一个平面图。这个新图就是原来平面图的对偶图。
度：图中的顶点所连接的边数。
正则图：各顶点的度都相同的图，叫正则图。
极大图：各个面都是三边形面的图，叫极大图。
完全图：各顶点的度都相同，且各个面都是三边形面的图，叫完全图。即图的顶点数是n，则各顶点的度都是n－1的图。
地图：地图也是一种平面图。地图中的各个顶点都连有三条边（即3—度顶点），所以地图是一种3—正则的平面图。所以地图的对偶图是一个所有面都是三边形面的极大平面图。
1、4  图的着色：
着色：给图的一种元素或几种元素进行染色，使得相邻的各元素都具有不同的颜色。
单元素着色：如只给顶点着色，只给面着色和只给边着色。
多元素着色：如给顶点和边都着色，叫全着色；给顶点、边和面都着色时，叫整着色。
着色数：给某个图着色时，最少要用的颜色数。
n—着色或n—色图：对某个图而言，其色数是n时，就说该图是n—着色的或n—色图。
可n—着色，对一个图或一系列的图来说，其色数都不大于n，则说这些图是可n—着色的。
地图的着色：地图的着色是对地图的面的染色，即对3—正则平面图的面染色。也可以看成是对地图的对偶图的顶点着色，即对极大平面图的顶点着色。
    1、5  四色猜测：
地图四色猜测：任何地图着色，最多四种颜色就够用了。或者说，任何地图的色数都不大于4。
平面图四色猜测：由于地图的面着色可以转化成极大平面图的顶点着色，所以地图的四色猜测也可以转化成极大平面图的四色猜测。极大平面图中的各元素间的相邻关系是最复杂的，边数也是最多的。所以，如果极大平面图的四色猜测正确，那么由极大平面图经去顶和减边所得到的任意平面图的着色数就只会减少，而不会再增加。所以也就有任意平面图的四色猜测也是正确的。因此，只要证明了任意平面图的四色猜测是正确的，也就等于证明了任何地图的四色猜测也是正确的。
林格尔公式是求顶点数是n的完全图的亏格的公式。
赫渥特公式是求可嵌入某亏格的曲面上的图的色数的公式。也可以说是求可嵌入某亏格的曲面上的图的完全图的顶点数的公式，因为图的色数就是其最小完全同态的顶点数（哈拉里语）。
其实这两个公式是互为反函数的，是可以相互推导的。
2、构形、色链与交换
因为平面图的种类有无穷多个，所以也就决定了四色问题所研究的对象是一个无穷的集合。无穷多的图，且没有一定的规律可循，是不可能用数学归纳法或穷举法完成证明的。如何把研究对象是一个无穷的集合转变成一个有穷的集合，这是证明四色猜测中的一种技巧。
2、1  构形：
设一个只有一个顶点没有着色，其他顶点都已用四种颜色着了色的并且符合着色的要求——相邻的顶点不用同一颜色——的图，把这样的图就叫做构形。没有着色的顶点叫待着色顶点，与待着色顶点相邻的顶点叫围栏顶点。构形在图论中表示时，只显示待着色顶点和围栏顶点，以及它们之间的相邻关系，其他的顶点一律不显示出来。这样的图（构形）在图论中就叫轮图，其所对应的构形就是轮构形。在轮构形的围栏顶点已占用完了四种颜色的情况下，我们只要能把所有轮构形的待着色顶点着上图中已用过的四种颜色之一，也就证明了四色猜测是正确的。
轮图的种类也是无穷多的，因为任何一个顶点的度都可以是无穷的。但是，可以证明在任何一个平面图中，至少都存在着一个顶点的度是小于等于5的。这就是说，度是大于5的顶点在平面图中是可以避免的，而度小于等于5的顶点在图中是不可避免的。有了不可避免度和不可避免顶点，就有不可避免的轮构形。不可避免的轮构形的轮沿顶点数是决不会大于5的。这就把无穷多的轮构形变成了只有轮沿顶点数小于等于5的六种轮构形。即：0—轮构形（即K1图），1—轮构形（即K2图），2—轮构形（即2—重K3图），3—轮构形（即K4图），4—轮构形和5—轮构形。2—轮构形，3—轮构形，4—轮构形和5—轮构形分别对应的就是坎泊提出的“一国与两国”相邻，“一国与三国”相邻，“一国与四国相邻”和“一国与五国相邻”的构形。
0—轮构形，1—轮构形，2—轮构形，3—轮构形，由于其围栏顶点数都不大于3，不可能占用完四种颜色，所以其待着色顶点是一定还有至少一种颜色可着，这是不言而喻的。但4—轮构形和5—轮构形的围栏顶点数是大于等于4的，若围栏顶点已经占用完了四种颜色时，就得要想办法使围栏顶点所占的颜色数由四种减少到三种，空出一种颜色来，给待着色顶点着上。
对于4—轮构形，坎泊已给出了证明，任何4—轮构形都是可约的，即是可4—着色的。但坎泊在证明5—轮构形时，却漏掉了一种情况，而在坎泊宣布他证明了四色猜测后十一年的1890年，因赫渥特构造了赫渥特图而指出了坎泊的证明存在着漏洞。一个半世纪以来，不用说对具有赫渥特图特征的5—轮构形，没有得到证明是否可约，就是连赫渥特图这一个具体的图，也是在1990年前后才进行了4—着色的。所以证明具有赫渥特图特征的构形是否可约，就是证明四色猜测的关键。
2、2  5—轮构形：
把5—轮构形的五个围栏顶点分别用1、2、3、4、5表示，待着色顶点用V表示，其着色分别是1B、2A、3B、4D、5C，V不着色。如图1所示。
坎泊构形（K—构形）：坎泊已证明了是可约的构形叫坎泊构形（K—构形），其中包括0—轮构形，1—轮构形，2—轮构形，3—轮构形，4—轮构形和5—轮构形中具有非赫渥特图特征的构形。
赫渥特构形（H—构形）：具有赫渥特图特征的构形叫赫渥特构形（H—构形），其中只有5—轮构形才具有赫渥特图特征的构形。

H—构形的定义：在5—轮构形中，不但含有从2A到5C的A—C连通链以及含有从2A到4D的A—D连通链，而且两链在中途还有相交叉（交叉点着A色）的情况，也不能通过换色交换（换色交换见下面2、3中）连续的移去两个同色B（1B和3B）的构形，才是H—构形（如图２）。这种构形实质上是不能通过换色交换空出任何颜色给待着色顶点的构形。
2、3  色链与交换：
色链：在已着过色的图中，由两种颜色的顶点交替出现的一条道路，就叫色链，简称链。
对角链和邻角链：轮构形中，由围栏顶点的对角顶点的颜色所构成的链，叫对角链；由围栏顶点的相邻顶点的颜色所构成的链，叫邻角链。在5—轮构形中，A—C链和A—D链都只是对角链，A—B链和C—D链也都只是邻角链，而B—C链和B—D链既都是对角链，也又都是邻角链。
相反链和相邻链：把两条链的颜色都不同的两条链叫相反链；而把两条链中有一种相同颜色的两条链叫相邻链。在5—轮构形中，A—B链和C—D链是一对相反链；而A—B链，A—C链和 A—D链；B—A链，B—C链和B—D链；C—A链，C—C链和C—D链；D—A链，D—B链和D—C链则是四组不同的相邻链。
交换：也叫颜色交换。把色链中着两种不同颜色的顶点的颜色相互交换的过程就叫交换。以达到改变链中某一顶点颜色的目的。
颜色交换的三种作用：
换色交换：该交换后，可以达到使构形中围栏的某一顶点颜色改变的目的。为达到这种交换的目的，只能从5—轮构形的某一围栏顶点开始，交换5—轮构形的围栏顶点的某一条不连通的对角链。
断链交换：该交换后，可以达到使构形中连通的A—C链和A—D链至少一条断开的目的。为达到这种交换的目的，只能从5—轮构形的某一围栏顶点开始，交换5—轮构形围栏顶点的某一邻角链，或者从5—轮构形非围栏顶点开始，交换5—轮构形围栏顶点的某一邻角链，都可以达到目的。可见，断链交换的起始顶点比换色交换要灵活一些。
转型交换：我们这里所举的例子是BAB型（峰点是A）的H—构形，通过这种转型交换后，可以达到使构形的类型改变的目的。如从顶点1B开始交换B—D对角链后，构形变成DCD型（峰点是C）的H—构形，而从顶点3B开始交换B—C对角链后，构形变成CDC型（峰点是D）的H—构形。同样也可以看出，转型交换的灵活性最差，只能交换两条关于两个同色B的链对角链。
坎泊交换（K—交换）：以上的“换色交换”可以直接空出颜色给待着色顶点，这种交换就是坎泊交换（K—交换）。
坎泊链法（K—链法）：解决K—构形的交换方法，就是坎泊链法（K—链法）。
坎泊链（K—链）：5—轮构形的对角链就是坎泊链（K—链）。
３、H—构形的不可免集及其可约性
上面我们已经看到了平面图的六种不可避免的轮构形，由这些轮构形构成的集合就是平面图的不可免构形集，即不可免集。5—轮构形不但有K—构形，还有H—构形。已知K—构形都是可约的，那么H—构形是否可约，H—构形有哪几类，都是必须要对其进行研究的问题，只有这样，才能确定四色猜测是否正确的问题。
3、1  H—构形的不可免集：
已知H—构形是不能通过换色交换空出任何一种颜色给待着色顶点V的，所以其中的A—C链，A—D链，B—C链B—D链四种链都是不能交换的，四种颜色可能构成的六种链中，四种链已不可能进行交换了，而可以进行交换的链就只有A—B链和C—D链了。这两条链是相反的色链，是不可能相交叉的。所以这两种链在构形中的相互关系只能是：
要么只有一条经过5—轮的4D和5C的环形的C—D链，另一条A—B链不是环形的（如图3），我们称之为A类H—构形；要么就只有一条经过5—轮的1B、2A和3B的环形的A—B链，另一条C—D链不是环形的（如图4），我们称之为B类H—构形；要么两条链A—Ｂ和Ｃ—Ｄ都不是环形的，而都是直链（如图5），我们称之为C类H—构形（图5中的两个构形只是左右分别不同，实质上同一个构形）；要么两条链A—B和C—D都是环形的，但不相交叉（如图6）。除此四种情况外，再无其他的情况。这就是H—构形的不可免集。从图6中可以看出，A—B环形链与C—D环形链是没有相交叉情况的。



由于图6是两种环形链A—B和C—D都有的构形，又均含有A类H—构形和B类H—构形的特征，可以分别属于A类H—构形或B类H—构形，不必要单独作为一种构形类别列出。这样，实际上H—构形就只有三种类形的不可免构形。而这三种H—构形都是可约的。所以四色猜测也就是正确的。
3、2  构形的可约性
构形的可约性：若某构形是可以4—着色的，即可以给待着色顶点V着上图中已用过的四种颜色之一，就说该构形是可约的，否则就是不可约的。

三种不可免的H—构形的可约性：
A类H—构形（如图3）的可约性：由于该构形中有一条经过4D和5C的环形的C—D链，分A—B链于环内、环外互不连通的两部分，交换其任一部分A—B链都可以使连通的A—C链和A—D链断开，成为K—构形而可约。至少图中有一条经过1B，2A和3B的A—B链是一定可以交换的。
B类H—构形（如图4）的可约性：由于该构形中有一条经过1B，2A和3B的环形的A—B链，分C—D链于环内、环外互不连通的两部分，交换其任一部分C—D链都可以使连通的A—C链和A—D链断开，成为K—构形而可约。至少图中有一条经过4D和5C 的C—D链是一定可以交换的。
C类H—构形（如图5）的可约性：由于该构形中没有任何环形链，A—B链和C—D链也都成了不可交换的链了。所以也就只能进行“转型交换”，先移去一个同色B，使构形转型了。再根据转型后的构形再进行解决。“转型交换”后有两种结果，一是转型成DCD（或CDC）型的，峰点是C（或D）的，可以连续的移去两个同色D（或C）的K—构形；一是转型成DCD（或CDC）型的，峰点是C（或D）的，有经过5—轮两个轮沿顶点的环形A—B链的A类H—构形。按A类H—构形的解决办法去解决就行了。

从图３，图４和图５可以看出，有环形链的Ａ类和Ｂ类Ｈ—构形都是左右对称的，而只有C类H—构形是不对称的。但还有一种C类H—构形也是对称的（如图7，a），图中以A—B链的一段或一支作为构形的对称轴。这个图经过两次同方向（逆时针方向或顺时针方向）的转型交换后，图就都会变成不对称的C类H—构形。再用解决不对称的C类H—构形的办法去解决即可。
赫渥特图：图中有一条经过4D和5C的环形的C—D链，所以是A类H—构形的代表。该图可以简写成“H—图”。
敢峰的终极图（也就是米勒图）：图中有一条经过1B，2A和3B的环形的A—B链，所以是B类H—构形的代表。该图可以简写成“GM—图”。
张彧典的第八构形：图中既没有经过1B，2A和3B的环形的A—B链，又没有经过4D和5C的环形的C—D链，所以是C类H—构形的代表。该图可以简写成“Z—图”。

“九点形”构形的可约性：以上的各类H—构形当顶点数减少到“九点形构形”时（如图8，图9），A类H—构形所对应的“九点形”图8，a仍是A类H—构形；B类H—构形所对应的“九点形”图8，b，以及C类H—构形所对应的“九点形”图9的两个构形和图7，a的对称的C类H—构形所对应的“九点形”图7，b，都是可以连续的移去两个同色B的K—构形。也都是可约的。
    4、各类构形的相互转化
4、1  H—构形与K—构形的相互转化：一个BAB型的有经过5—轮的4D和5C两个轮沿顶点的环形的C—D链的A类H—构形的图，应该用交换A—B链的“断链交换”来解决。如果没有用“断链交换”，而是用了“转型交换”，图就会转化成一个DCD（或CDC）型的，需要选择先后次序的交换关于两个同色D（或C）的链，并可以连续的移去两个同色D（或C）的K—构形；但若对这个可以连续的移去两个同色D（或C）的K—构形，选择交换关于两个同色D（或C）的链的先后次序选择错了，图又会转化成一个ABA型的，有经过5—轮两个轮沿顶点的C—D链的H—构形。赫渥特图着色时，就容易出现这样的问题。但如果都交换对了，都可以是可以空出颜色给待着色顶点的。
4、2  A类H—构形与B类H—构形的相互转化：一个BAB型的有经过1B，2A和3B的环形的A—B链的B类H—构形的图，应该用交换C—D链的“断链交换”来解决。如果没有用“断链交换”，而是用了“转型交换”，图就会转化成一个DCD（或CDC）型的，有经过5—轮两个轮沿顶点的环型的A—B链的A类H—构形。如果再不按解决A类H—构形的“断链交换”去解决，图就会又转化成一个ABA型的，有经过5—轮三个轮沿顶点的A—B环型链的A类H—构形。米勒在给他的图着色时就出现了这样的问题，所以米勒认为他的图是一个是无法解决的构形。
5、四色猜测是正确的
现在，不管是坎泊证明过的K—构形，还是以后赫渥特指出的坎泊漏掉了的H—构形，都已经证明是可约的了，那么四色猜测也就是正确的了。


雷  明
二○一八年八月二十六日于长安

注：此文已于二○一八年八月二十六日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，

wangyangke

定理：在四色方面，任在深——申一言比雷明——雷明85639720稍胜一筹。
论证：在四色方面，任在深——申一言轻而易举的拿出两幅四色图，其后任人评说；而两幅四色图的四色水准与雷明——雷明85639720研究四色N多年、四色著述四色著作篇幅宏富浩繁所说的那个四色东东不相上下；任在深——申一言在费时和精力投入上明显占优了。刘忠友——申一言的论坛主业单位论，你雷明————雷明85639720的论坛主业四色；任在深——申一言轻而易举的拿出两幅四色图，任人评说，一副踌躇满志、岿然不动的单位论创始人的姿态；而雷明——雷明85639720在触及其要害难点疑点时，在四色濒临向五色缴械投降或在四色雷明——雷明85639720向五色投降的前后每每摆谱、卖派头、恼羞成怒；没有底气，多的是怒气、怨气。
由此有定理：在四色方面，任在深——申一言比雷明——雷明85639720稍胜一筹。

由上定理引申出定理：在雷明解决了四色问题的前提下，刘忠友也解决了四色问题。

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

wangyangke

雷明85639720说得对：wangyangke 你真无耻！