赫渥特H—构形的分类及解决办法

雷明85639720

赫渥特H—构形的分类及解决办法
雷  明
（二○二二年三月十四日）

什么是构形？在给平面图着色时，是一个顶点一个顶点的去着。也总存在着一个最后要着色的顶点。把这种还有一个顶点未着色的平面图就叫做构形。未着色的顶点叫待着色顶点，一般情况下用大写的英文字母V表示。把与待着色顶点V相邻且与待着色顶点构成了轮（这种构形又叫轮构形）的顶点叫围栏顶点（简称围栏）。。
构形的分类：构形分类的原则是各级分类一定只能是分成非此即彼的两类，以防止有遗漏。
一级分类：依据是平面图中总是存在着至少一个顶点的度是小于等于5为理论根据，把轮构形分为可避免的构形和不可避免的构形。待着色顶点的度是大于等于6的构形是可以避免的，可以不再去研究它的着色方法（因为着色时总可以把最后一个要着色的待着色顶点V放在度是小于等于5的顶点之上），集中力量去研究度是小于等于5的待着色顶点的构形的着色方法的问题。
二级分类：根据构形中的待着色顶点能不能直接着色，把不可避免的构形分为可直接着色的构形和不可直接着色的构形。围栏顶点占用颜色数小于等于3的（包括待着色顶点的度是小于等于3）的构形，待着色顶点是可直接着色的；而围栏顶点占用颜色数等于4的构形，待着色顶点是不可直接着色的。
三级分类：根据构形能不能从围栏顶点中直接空出颜色给待着色顶点V着上，把不可直接给待着色顶点着色的构形分为可从围栏顶点中直接空出颜色的坎泊K—构形（空出的颜色就可直接给待着色顶点着上）和不可直接从围栏顶点中空出任何一种颜色的赫渥特H—构形。可从围栏顶点中直接空出颜色的坎泊K—构形坎泊早已进行了解决，是可以4—着色的。现在主要就是解决不可直接从围栏顶点中空出任何颜色的赫渥特H—构形的着色问题了。
赫渥特H—构形虽然从表面上看是空不出任何一种颜色给待着色顶点V的，而实际上是双环交叉链在“作怪”。在BAB型的H—构形中，存在A—C和A—D连通的、并且与待着色顶点V各自构成了“环”的双环交叉链。因为连通链是不能交换的，所以A、C、D三色是不能空出来的。剩下来就只能是B了，但当从任一个B进行了交换并移去了一个B后，就会新生成从另一个B到其对角顶点的连通链，而不能连续的移去两个同色B。所以H—构形是不能直接从围栏顶点中空出任何一种颜色的构形，名符其实。
H—构形中，A、B、C、D四种颜色所能构成的6种链已有A—C、A—D、B—C、B—D 4种链都是不能交换的，剩下的只能是看A—B链和C—D链了。这两种链又是相反链（即两条链中的两种颜色各不相同），是不可能交叉的。这两种链中如果有一条是环形链，则另一条一定是被该环形链分隔在环内、环外两侧的，互不连通。这就为我们研究H—构形的着色方法创造了条件。
H—构形中，双环交叉链的共同起始顶点A和相交叉顶点A，以及两链的两个相邻的末端顶点C和D，是4个关键的顶点（其中有3个是围栏顶点，一个是非围栏顶点）。这4个顶点，其中只要有一个顶点的颜色发生了变化，构形就转化成了不含双环交叉链的K—构形了。而要改变这4个顶点中任何一个顶点的颜色，交换的必定不是A—B链就是C—D链。为了防止交换了一种链而使构形中所有着有该链的两种颜色的顶点的颜色都全部改变而起不到作用，就必须要有与其相反的另一条链C—D或A—B呈环形链，把交换的链分隔成不连通的两部分。
四级分类：可根据构形中有没有经过了关键顶点的环形链把H—构形分为有环形链的构形和无环形链的构形两类。
有环形链的构形可以交换能改变关键顶点颜色的链，把双环交叉链断开（断链法），使H—构形转化成K—构形。
无环形链的构形，构形中没有环形链，没有可改变关键顶点颜色的链进行交换。但在H—构形中，虽然B—C链和B—D链不能同时交换，但可以只交换一个，使构形转型（转型法）。由BAB型转化成DCD型（逆时针方向转型）或CDC型（顺时针方向转型）。然后再根据转型后的构形的具体情况进行解决。可以证明最大的转型次数是不会超过5次的（且在转型过程中还可以转化成有环形链的构形，可以改用断链法，提前结束转型，我们叫转型法＋断链法）。
五级分类：根据环形链的种类，可以把有环形链的构形再分成两类：有环形链A—B的构形和有环形链C—D的构形。
在有A—B环形链的构形中，A—B环形链一定把C—D链分隔成了环内、环外互不连通的两部分。交换任一部分的C—D链，双环交叉的A—C链和A—D链一定断开（这就是断链法），图转化成坎泊的K—构形。
但有C—D环形链的构形，还可以再分类。
六级分类：有C—D环形链的又可分为两种：可以把双环交叉链A—C和A—D的共同起始顶点A和交叉顶点A分隔在C—D环形链两侧的构形和不能把这两个关键顶点A分隔在C—D环形链两侧的构形。
可以把双环交叉链A—C和A—D的共同起始顶点A和交叉顶点A分隔在C—D环的两侧的构形，仍然是可以使用断法的。可以交换任一部分的A—B链，双环交叉的A—C链和A—D链也一定断开，图转化成坎泊的K—构形。

但不可以把双环交叉链A—C和A—D的共同起始顶点A和交叉顶点A分隔在C—D环的两侧的构形，则不能使用断链法。也不能交换任一条A—B链，因为这样的交换后，构形中仍然会有新的双环交叉链产生。所以也就只能用转型法进行解决了。在转型的过程中也会转化成有环形链的构形，可以改用断链法，提前结束转型。如图1中虽有环形的C—D链，但不能使用断链法交换A—B链，只能用转型法，一次转型后就是一个有环形链A—B的构形（如图2），可以改用断链法。
由于有埃雷拉E—图构形的存在，它是一个无穷周期循环转型的构形。从而得到E—图是每次转形所得构形（包括原构形在内）都是可以用改变有关关键顶点颜色的断链法而转化成K—构形的构形。E—图就有这种性质。根据原命题的逆否命题与原命题有“同真同假”的逻辑关系，则有“每步转型（也包括原构形在内）都是不可以用改变有关关键顶点颜色的断链法转化成K—构形的构形，一定不是无穷周期循环转型的E—图构形。即一定是一个有限次转型的非E—图构形”的结论是成立的。那么“有限次转型”的“上限值”是多少呢？
因为5—轮构形，有5个轮沿顶点，每个轮沿顶点都作一次峰点时，就是五次转型。转型次数大于五次时，显然就会出现循环现象。所以最大在五次转型后就应该是只有一条连通链的可约的K—构形了。而在最后一次转型的前一次转型后，得到的就一定是一个可以连续的移去两个同色的可约的K—构形了。这就证明了最大转型次数的上限值是四，或者说是五也可以。

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，