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

晋源泉

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


      
      

《用计算法对地图进行４－着色的计算程序》

地图进行４－着色的计算程序：
一、在地图的对偶图中对各个顶点进行编码：
１、在顶点数为Ｑ＋q的地图的对偶图Ｇ中，首先假设围栏顶点≤３的顶点数Ｖ＝q＝０的对偶图是Ｇ＇。其次是对顶点数Ｖ＝Ｑ的Ｇ＇的每一个顶点进行编码：图中心的某个三角形有界面的三个顶点的编码分别是x1、x2、x3，然后依次对剩余的顶点进行一条龙编码分别是x４、x５、………xＱ。
二、在图1３中进行下列计算程序，求解地图的对偶图Ｇ的着色成立：
２、列出由顶点编码表示的Ｑ个顶点的全集合Ｘ＝｛x1，x2，x3……xQ｝。
３、由顶点编码表示的每一个顶点的围栏顶点的集合叫这个顶点的围栏集合，分别表示为x1、x2、x3……XQ。
４、由所有顶点的围栏集合组成的方程组叫n-轮构形方程组。
５、求解Ａx1、Ｂx2、Ｃx3三色锁定后的每一组的顶点的围栏顶点以外的不相邻顶点的集合，这个集合叫组名中的编码顶点的伪同色集。其集合的标称和组名相同，即：Ａx1、Ｂx2、Ｃx3的三个不同的伪同色集。
６、求解真同色集――极大点独立集时，同一个群的极大点独立集的顶点数相同。
７、分别在Ａx1、Ｂx2、Ｃx3的伪同色集中：依据n-轮构形方程组，求解极大点独立集群。群中每个极大点独立集的标称除和编码顶点的颜色相同外，在右下角加序号１、２、３、……m１。（不同的伪同色集产生的极大点独立集分别为m１、m２、m３）。这些极大点独立集叫编码顶点的极大点独立集群，或分别叫Ａ、Ｂ、Ｃ真同色集群。
８、分别在３个不同的极大点独立集群中各取一个极大点独立集进行组合成一个三合一的并集群，群中每一个并集分别表示为Ｘ并1、Ｘ并2……Ｘ并m。（m＝m１×m２×m３）。
９、求每一个并集分别与全集Ｘ的补集，分别表示为Ｘ补１、Ｘ补２、Ｘ补３、……Ｘ补m ，补集的极大点独立集的顶点数由计算结果决定，这一步也叫极大点独立集的筛选。
１０、当一个补集是极大点独立集时，我们称这个补集是第四极大点独立集，在所有补集中的第四极大点独立集分别表示为Ｄ１、Ｄ２、……Ｄk真同色集。
三、求解每个着色方案的集合并作图。
１１、由计算方法解得不同的第四极大点独立集有Ｋ个时：本地图的对偶图Ｇ＇的４着色方案就有Ｋ个，每个着色方案的集合等于4个极大点独立集的并集，每个方案的集合分别是Z1，Z2，……Zk。
１２、对每个方案的集合中围栏顶点≤３的顶点数Ｖ＝q的每个顶点分别命名为△1，△2，△3……△q。列出n－轮形方程组，并根据其围栏顶点的颜色分别选取到Ａ、Ｂ、Ｃ、Ｄ真同色集之一中去。
13列出顶点数为Ｑ＋q的地图的对偶图Ｇ的４－着色方案的各个集合并附图。
14、本计算程序对任何一幅地图的对偶图采取的是一次性完成着色的方法。在计算程序着色的实际过程中，客观的存在着颜色冲突和颜色不冲突两组结果。但是，用计算程序着色完成时，最后通过筛选选择了颜色不冲突的一组结果。



《用计算法对地图进行４－着色的计算程序的应用举例》

如图１６，求Q=12的球面图中的Ｎ和k及每个着色方案的集合和图？
一、在Q=12的球面图的对偶图Ｇ中对各个顶点进行编码：
１、在顶点数为Ｑ＋q的地图的对偶图Ｇ中，围栏顶点≤３的顶点数Ｖ＝q＝０的对偶图是Ｇ。其次是对顶点数Ｖ＝Ｑ的Ｇ的每一个顶点进行编码：
图中心的某个三角形有界面的三个顶点的编码分别是x1、x2、x3，然后依次对剩余的顶点进行一条龙编码分别是x４、x５、………xＱ。
二、在图1６中进行下列计算程序，求解地图的对偶图Ｇ的着色成立：
２、列出由顶点编码表示的Ｑ个顶点的全集合Ｘ＝｛x1，x2，x3……xQ｝。
３、由顶点编码表示的每一个顶点的围栏顶点的集合叫这个顶点的围栏集合，分别表示为x1、x2、x3……XQ。
４、由所有顶点的围栏集合组成的方程组叫n-轮构形方程组。     
Ｘ1＝｛x2，x3，x4，x5，x6｝       Ｘ7｛x2，x6，x8，x11，x12｝
Ｘ2＝｛x1，x3，x6，x7，x8｝       Ｘ8＝｛x2，x3，x7，x9，x12｝
Ｘ3＝｛x1，x2，x4，x8，x9｝       Ｘ9＝｛x3，x4，x8，x10，x12｝
Ｘ4＝｛x1，x3，x5，x9，x10｝       Ｘ10＝｛x4，x5，x9，x11，x12｝
Ｘ5＝｛x1，x4，x6，x10，x11｝        Ｘ11＝｛x5，x6，x7，x10，x12｝
Ｘ6＝｛x1，x2，x5，x7，x11｝         Ｘ12＝｛x7，x8，x9，x10，x11｝
５、求解Ａx1、Ｂx2、Ｃx3三色锁定后的每一组的顶点的围栏顶点以外的不相邻顶点的集合，这个集合叫组名中的编码顶点的伪同色集。其集合的标称和组名相同，即：Ａx1、Ｂx2、Ｃx3的三个不同的伪同色集。
A x1＝Ｘ一Ｘ1＝｛x1：x7，x8，x9，x10，x11x12｝
B x2＝Ｘ一Ｘ2＝｛x2：x4，x5，x9，x10，x11，x12｝
C x3＝Ｘ一Ｘ3＝｛x3：x5，x6，x7，x10，x11，x12｝
６、求解真同色集――极大点独立集时，同一个群的极大点独立集的顶点数相同。极大点独立集的顶点数按Ｑ÷４的大整数进行计算。否则，就按Ｑ÷４－１的大整数进行计算。
７、分别在Ａx1、Ｂx2、Ｃx3的伪同色集中：依据n-轮构形方程组，求解极大点独立集群。群中每个极大点独立集的标称除和编码顶点的颜色相同外，在右下角加序号１、２、３、……m１。（不同的伪同色集产生的极大点独立集分别为m１、m２、m３）。这些极大点独立集叫编码顶点的极大点独立集群，或分别叫Ａ、Ｂ、Ｃ真同色集群。
Ａ真同色集群：
   A1＝｛x1：x7，x9｝    A4＝｛x1：x8，x11｝
A2＝｛x1：x7，x10｝   A５＝｛x1：x9，x11｝
A3＝｛x1：x8，x10｝     m1＝5
Ｂ真同色集群：
B1＝｛x2：x4，x11｝    B4＝｛x2：x5，x12｝
B2＝｛x2：x4，x12｝     B5＝｛x2：x9，x11｝
B3＝｛x2：x5，x9｝          m2＝5
Ｃ真同色集群：
C1＝｛x3：x5，x7｝     C4＝｛x3：x6，x12｝
C2＝｛x3：x5，x12｝     C5＝｛x3：x7，x10｝
C3＝｛x3：x6，x10｝        m3＝5
８、分别在３个不同的极大点独立集群中各取一个极大点独立集进行组合成一个三合一的并集群，群中每一个并集分别表示为Ｘ并1、Ｘ并2……Ｘ并m。（m＝m１×m２×m３）。
   ①　并集Ｘ并n的数量m＝m１×m２×m3＝５×５×５＝１２５
②　Ｘ并1——Ｘ并５如下：
Ｘ并1＝A1＋B1＋C1＝｛x１：x７，x９，x２：x４，x１1，x3：x5，x7｝
Ｘ并２＝A1＋B1＋C2＝｛x１：x7，x9，x２：x4，x11，x3：x5，x１２｝
Ｘ并３＝A1＋B1＋C3＝｛x１：x７，x9，x２：x4，x11，x3：x６，x１0｝
Ｘ并４＝A1＋B1＋C4＝｛x１：x7，x9，x２：x4，x１1，x3：x6，x１2｝
Ｘ并５＝A1＋B1＋C５＝｛x１：x7，x9，x２：x4，x11，x3：x７，x１０｝
（其他的并集Ｘ并m见附表）
９、求每一个并集分别与全集Ｘ的补集，分别表示为Ｘ补１、Ｘ补２、Ｘ补３、……Ｘ补m ，补集的极大点独立集的顶点数由计算结果决定，这一步也叫极大点独立集的筛选。
①补集Ｘ补m的数量＝并集Ｘ并m的数量m＝１２５
②Ｘ补1—Ｘ补5、Ｘ补18、Ｘ补39、Ｘ补54、Ｘ补71、Ｘ补83、Ｘ补90、Ｘ补106、Ｘ补120如下：
Ｘ补１＝Ｘ－Ｘ并１＝｛x6，x８，x12，x10｝
Ｘ补２＝Ｘ－Ｘ并２＝｛x6，x８，x10｝=｛x6：x８，x10｝=D1
Ｘ补３＝Ｘ－Ｘ并３＝｛x5，x８，x12｝
Ｘ补４＝Ｘ－Ｘ并４＝｛x8，x5，x10｝
Ｘ补5＝Ｘ－Ｘ并５＝｛x5，x6，x8，x1２｝
Ｘ补18＝Ｘ－Ｘ并18＝｛x4，x８，x11｝=｛x11：x８，x4｝=D2
Ｘ补39＝Ｘ－Ｘ并39＝｛x4，x8，x11｝=｛x8：x4，x11｝=D3
Ｘ补54＝Ｘ－Ｘ并54＝｛x5，x7，x9｝=｛x5：x7，x9｝=D4
Ｘ补71＝Ｘ－Ｘ并71＝｛x4，x6，x12｝=｛x12：x4，x6｝=D5
Ｘ补83＝Ｘ－Ｘ并83＝｛x5，x7，x9｝=｛x7：x5，x9｝=D6
Ｘ补90＝Ｘ－Ｘ并90＝｛x4，x6，x12｝=｛x4：x6，x12｝=D7
Ｘ补106＝Ｘ－Ｘ并106＝｛x6，x８，x10｝=｛x10：x6，x8｝=D8
Ｘ补1２0＝Ｘ－Ｘ并1２0＝｛x4，x6，x8｝=｛x8：x6，x4｝=D9
１０、当一个补集是极大点独立集时，我们称这个补集是第四极大点独立集，在所有补集中的第四极大点独立集分别表示为Ｄ１、Ｄ２、……Ｄk真同色集。
三、求解每个着色方案的集合并作图。
１１、由计算方法解得不同的第四极大点独立集有Ｋ个时：本地图的对偶图Ｇ的４着色方案就有9个，每个着色方案的集合等于4个极大点独立集的并集，每个方案的集合分别是Z1，Z2，……Z9。
Ｚ１＝Ｘ并２＋D1＝A1＋B1＋C2＋D1＝｛x１：x7，x9↑x２：x4，x11↑x3：x5，x１２↑x6：x８，x10｝。
Ｚ２＝Ｘ并18＋D2＝A1＋B4＋C３＋D2＝｛x１：x７，x9↑x２：x5，x12↑x3：x6，x10↑x4，x８，x11｝。
Ｚ３＝Ｘ并３9＋D3＝A2＋B3＋C４＋D3＝｛x１：x７，x10↑x２：x5，x9↑x3：x6，x12↑x4，x8，x11｝。
Ｚ４＝Ｘ并54＋D4＝A3＋B1＋C4＋D4＝｛x１：x8，x10↑x２：x4，x11↑x3：x6，x12↑x5，x7，x9｝。
Ｚ５＝Ｘ并71＋D５＝A3＋B5＋C1＋D５＝｛x１：x8，x10↑x２：x9，x11↑x3：x5，x7↑x4，x6，x12｝。
Ｚ６＝Ｘ并83＋D6＝A4＋B2＋C3＋D6＝｛x１：x8，x11↑x２：x4，x12↑x3：x6，x10↑x5，x7，x9｝。
Ｚ７＝Ｘ并90＋D7＝A4＋B3＋C5＋D7＝｛x１：x8，x11↑x２：x5，x9↑x3：x7，x10↑x4，x6，x12｝。
Ｚ８＝Ｘ并106＋D8＝A5＋B2＋C1＋D8＝｛x１：x9，x11↑x２：x4，x12↑x3：x5，x7↑x6，x8，x10｝。
Ｚ９＝Ｘ并120＋D９＝A5＋B4＋C5＋D９＝｛x１：x9，x1↑1x２：x5，x12↑x3：x7，x10↑x4，x6，x8｝

※   125个Ｘ补集合中有9个第四极大点独立集， 125个Ｘ并的集合见３８页附表。
１３、列出顶点数为Ｑ＝１２的地图的对偶图Ｇ的４－着色方案的各个集合并附图--------由读者自己操作。
《当前证明“四色猜测”成立的研究课题》
“四色猜测”自产生以来，多少人用了多少心血，甚至一生对球面地图４－着色中的这个够用的N=4色进行证明时，其大部分人所做的仅仅是对球面地图的一种着色。
因此，在证明“四色猜测”成立的过程中，不同的人们用了不同的方法完成了对地图的４－着色。所以，就产生了证明“四色猜测”成立的多个证明方法，发生了多人宣称证明了《四色猜测》成立的景象。对于任何每一种对地图的４－着色方法，都是构思人为人类奉献了自己力所能及的最美好的一份礼物；都是证明“四色猜测”成立的艰辛探索：
人们可以用双色链法、计算法、移动法、六边形网格法等等多种不同的方法对球面地图都能作出４－着色的结论，这是球面地图可４－着色的基本的事实。所以，鉴于这个基本的事实，证明《四色猜测》成立的方法条件已充足。因为，解决地图着色的实际问题是在其对偶图中的一次性着色，解决证明《四色猜测》成立的理论问题是在有颜色冲突的极大图的不可免构形集中的二次着色，只要二次着色数等于一次着色数，则，《四色猜测》成立。但是，现在是那一种方法对地图的《四色猜测》成立的证明是最优的问题，才是人们对《四色猜想》研究的课题。