用计算法证明四色猜测和着色之一

晋源泉

用计算法证明四色猜测和着色之一


前　　言
在本论文发表的今天，作者需要说的是：本论文在起草到现在定稿发表的过程中，从资料、书籍、理论等各个方面都得到了雷明和张域典两位前辈的大力支持和帮助，作者在此表示衷心的感谢。并恳请雷明和张域典两位前辈和同行们，对本文能提出批评指导的宝贵意见。
本论文《用计算法证明“四色猜测”成立的方法》由于篇幅较长，出于各种因素的考虑，作者将其分为九篇小论文发表，所有附图按总论文连续编号。又因网上文件大了不能发,所以,分为文件之一、二、三、四。附表和所有图按之五发出。
目　　　　　录
文件之一
《用计算法证明“四色猜测”成立的基础理论》………………………第０３页
《证明“四色猜测”成立的5－轮构形的属性》………………………第０５页
《用计算法证明“四色猜测”成立的计算程序》………………………第０７页
文件之二（１）
《用计算法证明“四色猜测”成立的应用举例1》……………………第１３页
《用计算法证明“四色猜测”成立的应用举例２》……………………第１９页
文件之二（２）
《用计算法证明“四色猜测”成立的应用举例３》……………………第２４页
《用计算法对地图进行４－着色的计算程序》…………………………第３１页
文件之三
《用计算法对地图进行４－着色的计算程序应用举例》………………第３３页
《当前证明“四色猜测”成立的研究课题》……………………………第３７页
文件之四
附表：例４附表…………………………………………………………………第３８页
附：图１、图２、图３、图４、图５、图６……………………………第４２页
附：图７、图８、图９……………………………………………………第４３页
附：图１０、图１１、图１２……………………………………………第４４页
附：图１３、图１４、图１５……………………………………………第４５页
附：图１６…………………………………………………………………第４６页

《用计算法证明“四色猜测”成立的方法》

《用计算法证明“四色猜测”成立的基础理论》

一、点独立集：
设无向图为G（V，E）,顶点集合Ｖ＇属于等于Ｖ，若Ｖ＇中的任何两个顶点均不相邻，则称Ｖ＇为G的点独立集。
1、极大点独立集：若在Ｖ＇中加入任何顶点的集合都不再是独立集，则称Ｖ＇是极大点独立集。
2、最大点独立集：顶点数最多的点独立集。
3、点独立数：最大点独立集的顶点数。
二、极大平面图：
一个平面图G（V、E），若G中不存在任意两个顶点之间可发生相邻关系而未发生相邻关系的顶点，则称为极大平面图或三角剖分图。
三、        极大平面图的可约构形F：
一个构形F称为可约的是指：对任何极大平面图G（V、E），若G中包含F，则存在Ｇ的一个子图Ｇ＇（通常Ｇ＇是从Ｇ中去掉F内部的一个顶点而得到的），使Ｇ中的不同的极大点独立集个数N（给Ｇ的每一个顶点的命名和一个极大点独立集的名称相同，使相邻顶点具有不同的名称。并且，使用的不同名称的极大点独立集数量最少）
四、        不可免完备集F：
　　　一个由有限个构形组成的集合，若具有下述性质，则称为一个不可免的完备集：极大平面图中任何顶点的度数至少包含不可免的有限完备集中的一个F－轮构形。
即：一个F度的顶点，0≤F≤５的轮构形的集合叫不可免的完备集F。

















《证明“四色猜测”成立的5－轮构形的属性》

一、        用计算法求解F=5的F－轮构形的可约，证明《四色猜测》成立的方法：
（一）、关于使用双色链求解0≤F≤5的F－轮构形的可约，证明《四色猜测》成立的方法，已经在雷明和张域典的有关文章书籍中讲解的很清楚了。
（二）、这里主要是以求解F=5的F－轮构形的可约为例，介绍使用计算法求解0≤F≤5的F－轮构形的可约，证明《四色猜测》成立的方法。
（三）、构形的选择：雷明和张域典的L、H构形中的一个F=5的F－轮构形。
（四）、在待着色顶点Ｖ的５个围栏顶点的环中，４色冲突的种类和4色同位性及３色同位性：
1、 4色同位性：因为任何一个顶点的着色可能是A或B或C或D。所以，在两个同色顶点的位置不变的条件下，4色中的任何一种颜色都可以和另外的任何一种颜色交换，颜色交换前后的着色效果及数学性质不会改变的属性叫4色的同位性。
2、 4色同位条件下的4色冲突的种类：因为，4色的同位性，在待着色顶点Ｖ的５个围栏顶点的环中，就一个种类：“位置不变的两个同色顶点之间分别夹着，除其以外的三个不同色的顶点中的一个顶点和二个顶点。”
3、３色的同位性：尽管任何一个顶点的着色可能是A或B或C或D。但是，两个同色顶点的位置变化不能通过颜色交换转换过来。其余的３色具有同位性叫３色的同位性。
4、３色同位条件下的4色冲突的的种类：在待着色顶点Ｖ的５个围栏顶点的环中，在不同的位置上两个同色顶点之间分别夹着除其以外的三个不同色的同位性的顶点中的一个顶点和二个顶点。所以，其种类=两个同色顶点的位置5种×其余的顶点是同位的色点位置只能算１种＝５种。
５、所以，在待着色顶点Ｖ的５个围栏顶点的环中，由两个同色顶点在不同的位置上，求得４颜色冲突的种类只有５种。












《用计算法证明“四色猜测”成立的计算程序》

求解0≤F≤5的F－轮构形的可约，证明《四色猜测》成立的计算程序：
计算程序运行过程 ：
以张域典《四色问题探秘》的H构形中的一个F=5的F－轮构形图7•3-4为例，如图１。
一、在构形图中对各个顶点进行编码：
１、在顶点Ｖ外还有Ｑ个顶点的构形图Ｇ中，如图1，Ｑ=11。Ｇ的顶点数等于Ｑ＋Ｖ，Ｇ＇的顶点数等于Ｑ。对图Ｇ＇的每一个顶点进行编码：待着色顶点Ｖ的５个围栏顶点的编码分别是x1、x2、x3、x4、x5，然后依次对剩余的顶点进行编码分别是x６、x７、………xＱ。如图２。
二、在图２中求解不同极大点独立集的数量N＇：
２、求Ｇ＇的不同的极大点独立集个数N＇，N＇＝４。在构形中同色顶点的编码为同一个极大点独立集，这个极大点独立集的标称和顶点颜色的标称（Ａ、Ｂ、Ｃ、Ｄ）相同。
Ａ＝｛x1,x9,x11｝、Ｂ＝｛x2,x5,x7｝、Ｃ＝｛x4,x8｝、Ｄ＝｛x3,x6,x10｝。
三、在图2中进行x1、x2、x3、x4、x5颜色冲突4转3：
３、用x1、x2、x3、x4、x5中两个同色顶点所夹的两个单色顶点的颜色，取代这两个同色顶点的颜色，并且符合相邻顶点不同色的规则，这一步叫x1、x2、x3、x4、x5颜色冲突4转3。Ｂ１转Ｄ，Ｂ２转Ｃ，如图3。
四、在图３中进行下列计算程序：
４、列出由顶点编码表示的Ｑ个顶点的全集合Ｘ＝｛x1，x2，x3……xQ｝。
５、由顶点编码表示的每一个顶点的围栏顶点的集合叫这个顶点的围栏集合，分别表示为x1、x2、x3……XQ。
６、由所有顶点的围栏集合组成的方程组叫n-轮构形方程组。如图３中：
x1＝｛x2、x5、x6、x7、x8｝, x2＝｛x1、x3、x8、x9｝, x3＝｛x2、x4、x9｝, x4＝｛x3、x5、x9、x10、x11｝, x5＝｛x1、x4、x6、x11｝, x6＝｛x1、x5、x7、x11｝, x7＝｛x1、x6、x8、x10、x11｝, x8＝｛x1、x2、x7、x9、x10｝, x9＝｛x2、x3、x4、x8、x10｝, x10＝｛x4、x7、x8、x9、x11｝, x11＝｛x4、x5、x6、x7、x10｝。
７、在x1、x2、x3、x4、x5颜色冲突4转3后，再加原先被两个同色顶点所夹的一个顶点的同色顶点，然后将其顶点颜色标称相同的为同一个集合，每一个集合的标称除和其所含的顶点颜色标称相同外，右下角再加其顶点编码，这一步叫五加一3色锁定（还有4转3后的3色锁定，其将在例1中讲解）。在构形中将五加一3色锁定时没有锁定的顶点的原着色全部解除只留编码。如图４
五、如图４中进行下列计算程序：
８、真同色集和伪同色集：顶点相互间是互不相邻的同色顶点的极大点独立集叫右下角顶点编码的真同色集或右下角顶点编码的极大点独立集。顶点相互间可能是互不相邻的同色顶点的集合叫右下角顶点编码的伪同色集。
五加一3色锁定后，含有原先被两个同色顶点所夹的一个顶点的同色顶点的集合是真同色集，另外的两个集合是伪同色集。其集合的标称或A（顶点编码）或B（顶点编码）或C（顶点编码）或D（顶点编码）。真同色集中的顶点颜色已全部确定，伪同色集中的顶点颜色没有全部确定。
如图４中：Ａx1,x9,x11的真同色集极大点独立集是Ａx1,x9,x11＝｛x1,x9,x11：｝，　Ｃx2,x4的伪同色集是Ｃx2,x4＝｛x２,x４：……｝，Ｄx３,x５的伪同色集是Dx３,x５＝｛x３,x５：……｝。‘：’表示其前的顶点是确定的为互不相邻的顶点，其后的顶点是没有确定为互不相邻的顶点。，
９、在各个伪同色集中，依据n-轮构形方程组，求解极大点独立集群，群中每个极大点独立集的标称除和编码顶点的颜色相同外，在右下角加序号１、２、３、……m１。（不同的伪同色集产生的极大点独立集分别为m１、m２、m３）。这些极大点独立集叫编码顶点的极大点独立集群。
如图４中：伪同色集Ｃx2,x4＝｛x２,x４：……｝，伪同色集Dx３,x５＝｛x３,x５：……｝中‘……’的求法:
①先求在所有顶点中减去已经锁定的顶点后的Y集合：
Y=x－Ａx1,x9,x11－Ｃx2,x4－Dx３,x５=x－｛x1,x9,x11：｝－｛x２,x４：｝－｛x３,x５：｝=｛x6、x7、x8、x10｝
伪同色集中的‘……’等于 Y中和其‘：’前没有相邻关系的顶点。
②依据：x6＝｛x1、x5、x7、x11｝, x7＝｛x1、x6、x8、x10、x11｝, x8＝｛x1、x2、x7、x9、x10｝, x10＝｛x4、x7、x8、x9、x11｝。
③伪同色集Ｃx2,x4＝｛x２,x４：x6,x7｝，伪同色集Dx３,x５＝｛x３,x５：x７,x８,x10｝。
④伪同色集Ｃx2,x4＝｛x２,x４：x6,x7｝，依据x6＝｛x1、x5、x7、x11｝、x7＝｛x1、x6、x8、x10、x11｝中没有x２,x４，但x6,x7是相邻的。
∴Ｃ１＝｛x２,x４,x6：｝，Ｃ２＝｛x２,x４,x７：｝。
⑤伪同色集Dx３,x５＝｛x３,x５：x７,x８,x10｝，依据x7＝｛x1、x6、x8、x10、x11｝、x8＝｛x1、x2、x7、x9、x10｝、x10＝｛x4、x7、x8、x9、x11｝。中没有x３,x５，但x７,x８,x10是互为相邻的。∴Ｄ１＝｛x3,x5,x7：｝，Ｄ２＝｛x3,x5,x8：｝，Ｄ３＝｛x3,x5,x１０：｝。
⑥极大点独立集群：
Ａ的极大点独立集群：∵Ａx1,x9,x11＝｛x1,x9,x11：｝，∴Ａ１＝｛x1,x9,x11：｝。
Ｃ的极大点独立集群：Ｃ１＝｛x２,x４,x6：｝，Ｃ２＝｛x２,x４,x７：｝。
Ｄ的极大点独立集群：Ｄ１＝｛x3,x5,x7：｝，Ｄ２＝｛x3,x5,x8：｝，Ｄ３＝｛x3,x5,x１０：｝。
１０、分别在３个不同的极大点独立集群中各取一个极大点独立集进行组合成一个三合一的并集群，群中每一个并集分别表示为Ｘ并1、Ｘ并2……Ｘ并m。（m＝m１×m２×m３）。
m＝m１×m２×m３＝１×２×３＝６
Ｘ并1＝Ａ１＋Ｃ１＋Ｄ１＝｛x1,x9,x11：｝＋｛x２,x４,x6：｝＋｛x3,x5,x7：｝
Ｘ并２＝Ａ１＋Ｃ１＋Ｄ２＝｛x1,x9,x11：｝＋｛x２,x４,x6：｝＋｛x3,x5,x8：｝
Ｘ并３＝Ａ１＋Ｃ１＋Ｄ３＝｛x1,x9,x11：｝＋｛x２,x４,x6：｝＋｛x3,x5,x１０：｝
Ｘ并４＝Ａ１＋Ｃ２＋Ｄ１＝｛x1,x9,x11：｝＋｛x２,x４,x７：｝＋｛x3,x5,x7：｝
Ｘ并５＝Ａ１＋Ｃ２＋Ｄ２＝｛x1,x9,x11：｝＋｛x２,x４,x７：｝＋｛x3,x5,x8：｝
Ｘ并６＝Ａ１＋Ｃ２＋Ｄ３＝｛x1,x9,x11：｝＋｛x２,x４,x７：｝＋｛x3,x5,x１０：｝
１１、求每一个并集分别与全集Ｘ的补集，分别表示为Ｘ补１、Ｘ补２、Ｘ补３、……Ｘ补m ，补集的极大点独立集的顶点数由计算结果决定，这一步也叫极大点独立集的筛选。m＝６
Ｘ补1＝Ｘ－Ｘ并1＝Ｘ－【｛x1,x9,x11：｝＋｛x２,x４,x6：｝＋｛x3,x5,x7：｝】＝｛x８,x１０｝
Ｘ补２＝Ｘ－Ｘ并２＝Ｘ－【｛x1,x9,x11：｝＋｛x２,x４,x6：｝＋｛x3,x5,x8：｝】＝｛x７,x１０｝
Ｘ补３＝Ｘ－Ｘ并３＝Ｘ－【｛x1,x9,x11：｝＋｛x２,x４,x6：｝＋｛x3,x5,x１０：｝】＝｛x７,x８｝
Ｘ补４＝Ｘ－Ｘ并４＝Ｘ－【｛x1,x9,x11：｝＋｛x２,x４,x７：｝＋｛x3,x5,x7：｝】＝｛x６，x８,x１０｝
Ｘ补５＝Ｘ－Ｘ并５＝Ｘ－【｛x1,x9,x11：｝＋｛x２,x４,x７：｝＋｛x3,x5,x8：｝】＝｛x６,x１０：｝＝Ｓ１
Ｘ补６＝Ｘ－Ｘ并６＝Ｘ－【｛x1,x9,x11：｝＋｛x２,x４,x７：｝＋｛x3,x5,x１０：｝】＝｛x６,x８：｝＝Ｓ２
依据：x8＝｛x1、x2、x7、x9、x10｝、x10＝｛x4、x7、x8、x9、x11｝，只有Ｘ补５＝｛x６,x１０｝＝｛x６,x１０：｝和Ｘ补６＝｛x６,x８｝＝｛x６,x８：｝成立。
１２、当一个补集是极大点独立集时，我们称这个补集是第四极大点独立集，在所有补集中的第四极大点独立集分别表示为Ｓ１、Ｓ２……Ｓk。第四极大点独立集的颜色标称是A,B,C,D中除三色被锁定后剩余的一色。本题剩余的一色是Ｂ色，并且，待着色顶点v可着Ｂ色。所以：
Ｘ补５＝Ｘ－Ｘ并５＝Ｘ－【｛x1,x9,x11：｝＋｛x２,x４,x７：｝＋｛x3,x5,x8：｝】＝｛x６,x１０，v：｝
Ｘ补６＝Ｘ－Ｘ并６＝Ｘ－【｛x1,x9,x11：｝＋｛x２,x４,x７：｝＋｛x3,x5,x10：｝】＝｛x６,x8，v：｝
Ａ色　　　Ｃ色　　　Ｄ色　　　　Ｂ色
Q＋V个的顶点着色如图５和图６。
１３、由三个极大点独立集组成Ｘ并m能对应产生二个第四极大点独立集。并且，待着色顶点Ｖ可含在各个第四极大点独立集中时：Ｇ的不同的极大点独立集个数N＝４。
１４、∵ Ｇ的不同的极大点独立集个数N等于Ｇ＇的不同的极大点独立集个数N＇，即：N＝N＇＝４。　∴　张域典的Ｈ构形中的这个F=5的F－轮构形可约。
∴《四色猜测》成立。

六、求解每个可约方案的集合并作图。
１５、由计算方法解得F=5的F－轮构形可约，总有Ｋ≥1个不同的第四极大点独立集。在含有不同的第四极大点独立集的构形中，除待着色顶点及其围栏顶点的着色不变外，K值不同时：其他顶点的着色有部分不同。
１６、由计算方法解得这个F=5的F－轮构形可约，不同的第四极大点独立集有Ｋ个时：张域典的Ｈ构形中的这个F=5的F－轮构形可约的方案就有Ｋ个，每个可约方案的集合等于4个极大点独立集的并集。
本题的可约方案的集合分别是Z1，Z2。分别如图５和图６所示。
Z1＝｛x1,x9,x11：↑x６,x１０，v：↑｛x２,x４,x７：↑｛x3,x5,x8：｝。
Z2＝｛x1,x9,x11：↑x６,x8，v：↑｛x２,x４,x７：↑｛x3,x5,x10：｝。
‘↑’表示其两边是不同的极大点独立集。

※　本计算程序的有关说明:
1、在编码顶点的伪同色集和极大点独立集）的集合中，所谓的这个‘编码顶点’必须作为集合的前列顶点（锁定的着色顶点），用‘：’表示其前的顶点颜色和互不相邻属性已确定或已锁定，其后的顶点颜色和互不相邻属性未确定或未锁定；在可约方案的集合中，不同的极大点独立集之间用‘↑’隔开。
2、本论文的Q、N 、n、k、m１、m２、m３、m除特别标注外全部是正整数。