用计算法证明四色猜测和着色之二（１）

晋源泉

用计算法证明四色猜测和着色之二（１）



《用计算法证明“四色猜测”成立的应用举例1》

例1、        构形选择：张域典《四色问题探秘》的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：
３、在图2中，用x1、x2、x3、x4、x5中两个同色顶点B1,B2所夹的两个单色顶点Ｃ１、Ｄ１的颜色，取代这两个同色顶点的颜色，并且符合相邻顶点不同色的规则，这一步叫x1、x2、x3、x4、x5颜色冲突4转3。即：x5由B1→Ｄ。　x２由B2→Ｃ。如图３。
四、在图３中进行下列计算程序：
4、列出由顶点编码表示的Ｑ个顶点的全集合Ｘ＝｛x1，x2，x3……x11｝。
5、由顶点编码表示的每一个顶点的围栏顶点的集合叫这个顶点的围栏集合，分别表示为x1、x2、x3……X11。
6、由所有顶点的围栏集合组成的方程组叫n-轮构形方程组。
x1＝｛x2，x5，x6，x7,x8｝。x5＝｛x1，x4，x6,x11｝。x9＝｛x2，x3，x4，x8,x10｝。
x2＝｛x1，x3，x8,x9｝。    x6＝｛x1，x5，x7,x11｝。x10＝｛x4，x7，x8，x9,x11｝。
x3＝｛x2，x4，x9｝。x7＝｛x1，x6，x8，x10,x11｝。 x11＝｛x4，x5，x6，x7，x10｝。
x4＝｛x3，x9，x10,x11｝。 x8＝｛x1，x2，x7，x9,x10｝。
７、在x1、x2、x3、x4、x5颜色冲突4转3后，这一例不进行五加一3色锁定，而是只做x1、x2、x3、x4、x5中的3色锁定。然后将其顶点颜色标称相同的为同一个集合，每一个集合的标称除和其所含的顶点颜色标称相同外，右下角再加其顶点编码，这一步叫4转3后的3色锁定。在构形中将4转3后3色锁定时没有锁定的顶点的原着色全部解除只留编码。如图７。
五、如图７中进行下列计算程序：
８、真同色集和伪同色集：顶点相互间是互不相邻的同色顶点的极大点独立集叫右下角顶点编码的真同色集或右下角顶点编码的极大点独立集。顶点相互间可能是互不相邻的同色顶点的集合叫右下角顶点编码的伪同色集。
4转3后3色锁定后，三个集合都是伪同色集。其集合的标称或A（顶点编码）或B（顶点编码）或C（顶点编码）或D（顶点编码）。伪同色集中的顶点没有全部确定为是互不相邻的顶点。
如图７中：Ａx1的伪同色集是Ａx1＝｛x1：……｝，　Ｃx2,x4的伪同色集是Ｃx2,x4＝｛x２,x４：……｝，Ｄx３,x５的伪同色集是Ｃx３,x５＝｛x３,x５：……｝，‘：’表示其前的顶点是互不相邻的顶点，其后的顶点是没有确定为互不相邻的顶点。
９、在各个伪同色集中，依据n-轮构形方程组，求解极大点独立集群，群中每个极大点独立集的标称除和编码顶点的颜色相同外，在右下角加序号１、２、３、……m１。（不同的伪同色集产生的极大点独立集分别为m１、m２、m３）。这些极大点独立集叫编码顶点的极大点独立集群。
如图７中：伪同色集Ａx1＝｛x1：……｝，伪同色集Ｃx2,x4＝｛x２,x４：……｝，伪同色集Dx３,x５＝｛x３,x５：……｝中‘……’的求法:
①先求在所有顶点中减去已经锁定的顶点后的Y集合：
Y=x－Ａx1－Ｃx2,x4－Dx３,x５=x－｛x1：｝－｛x２,x４：｝－｛x３,x５：｝=｛x6、x7、x8、x９、x10、x１１｝
伪同色集中的‘……’等于 Y中和其‘：’前没有相邻关系的顶点。
②依据：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＝｛x1：x９，x10，x１１｝,伪同色集Ｃx2,x4＝｛x２,x４：x6,x7｝，伪同色集Dx３,x５＝｛x３,x５：x７,x８,x10｝。
④伪同色集Ａx1＝｛x1：x９，x10，x１１｝依据x9＝｛x2，x3，x4，x8,x10｝，x10＝｛x4、x7、x8、x9、x11｝、x11＝｛x4，x5，x6，x7，x10｝。
∴A1=｛x１，x９，x１１：｝
⑤伪同色集Ｃ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：｝。
Ｃ的极大点独立集群：Ｃ１＝｛x２,x４,x6：｝，Ｃ２＝｛x２,x４,x７：｝。
Ｄ的极大点独立集群：Ｄ１＝｛x3,x5,x7：｝，Ｄ２＝｛x3,x5,x8：｝，Ｄ３＝｛x3,x5,x１０：｝。

１0、分别在３个不同的极大点独立集群中各取一个极大点独立集进行组合成一个三合一的并集群，群中每一个并集分别表示为Ｘ并1、Ｘ并2……Ｘ并m。（m＝m１×m２×m３＝６）。
Ｘ并1＝Ａ１+Ｃ１+Ｄ１＝｛x１，x９，x１１：｝+｛x２，x４，x6：｝+｛x３，x5，x７：｝
Ｘ并2＝Ａ１+Ｃ１+Ｄ2＝｛x１，x９，x１１：｝+｛x２，x４，x6：｝+｛x３，x5，x８：｝
Ｘ并3＝Ａ１+Ｃ１+Ｄ3＝｛x１，x９，x１１：｝+｛x２，x４，x6：｝+｛x３，x5，x１０：｝
Ｘ并4＝Ａ１+Ｃ2+Ｄ１＝｛x１，x９，x１１：｝+｛x２，x４，x7：｝+｛x３，x5，x７：｝
Ｘ并5＝Ａ１+Ｃ2+Ｄ2＝｛x１，x９，x１１：｝+｛x２，x４，x7：｝+｛x３，x5，x８：｝
Ｘ并6＝Ａ１+Ｃ2+Ｄ3＝｛x１，x９，x１１：｝+｛x２，x４，x7：｝+｛x３，x5，x１０：｝
11、求每一个并集分别与全集Ｘ的补集，分别表示为Ｘ补１、Ｘ补２、Ｘ补３、……Ｘ补m ，这一步也叫极大点独立集的筛选。m=6。
Ｘ补１=Ｘ－Ｘ并1=Ｘ－[｛x１，x９，x１１：｝+｛x２，x４，x6：｝+｛x３，x5，x７：｝]
=｛x8，x１０｝。
Ｘ补2=Ｘ－Ｘ并2=Ｘ－[｛x１，x９，x１１：｝+｛x２，x４，x6：｝+｛x３，x5，x８：｝]
=｛x７，x１０｝。
Ｘ补3=Ｘ－Ｘ并3=Ｘ－[｛x１，x９，x１１：｝+｛x２，x４，x6：｝+｛x３，x5，x１０：｝]
=｛x７，x８：｝。
Ｘ补4=Ｘ－Ｘ并4=Ｘ－[｛x１，x９，x１１：｝+｛x２，x４，x7：｝+｛x３，x5，x７：]
=｛x６，x８，x１０｝。
Ｘ补5=Ｘ－Ｘ并5=Ｘ－[｛x１，x９，x１１：｝+｛x２，x４，x7：｝+｛x３，x5，x８：｝]
=｛x６，x１０：｝＝Ｓ１。
Ｘ补6=Ｘ－Ｘ并6=Ｘ－[｛x１，x９，x１１：｝+｛x２，x４，x7：｝+｛x３，x5，x１０：｝]
=｛x６,x８：｝＝Ｓ２。
依据：x8＝｛x1、x2、x7、x9、x10｝、x10＝｛x4、x7、x8、x9、x11｝，只有Ｘ补５＝｛x６,x１０｝＝｛x６,x１０：｝和Ｘ补６＝｛x６,x８｝＝｛x６,x８：｝成立。
１2、当一个补集是极大点独立集时，我们称这个补集是第四极大点独立集，在所有补集中的第四极大点独立集分别表示为Ｓ１、Ｓ２……Ｓ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个的顶点着色如图５或图６。
１3、由三个极大点独立集组成Ｘ并m能对应产生二个第四极大点独立集。并且，待着色顶点Ｖ可含在各个第四极大点独立集中，Ｇ的不同的极大点独立集个数N＝４。
１4、∵ Ｇ的不同的极大点独立集个数N等于Ｇ＇的不同的极大点独立集个数N＇，即：N＝N＇＝４。　∴　张域典的Ｈ构形中的这个F=5的F－轮构形可约。
∴《四色猜测》成立。

六、求解每个可约方案的集合并作图。
１5、由计算方法解得F=5的F－轮构形可约，总有Ｋ≥1个不同的第四极大点独立集。在含有不同的第四极大点独立集的构形中，除待着色顶点及其围栏顶点的着色不变外，K值不同时：其他顶点的着色有部分不同。
１6、由计算方法解得这个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：｝。

17、特此说明：张域典《四色问题探秘》的H构形中的一个F=5的F－轮构形图7•3-4，如图１。在x1、x2、x3、x4、x5颜色冲突4转3的三色锁定中，要避免x1、x4是同色的情况发生。否则，进入了颜色冲突的迷惑阵。因为，这是由x1、x2、x3、x4、x5之外的顶点关系决定的一个特点，不属于本计算程序的漏洞。具体看下边例2。





《用计算法证明“四色猜测”成立的应用举例2》

例２、构形选择：张域典的H构形中的一个F=5的F－轮构形7•3-4如图7。
计算程序运行过程：
一、在构形图中对各个顶点进行编码：
１、在顶点Ｖ外还有Ｑ个顶点的构形图Ｇ中，如图1，Ｑ=11。Ｇ的顶点数等于Ｑ＋Ｖ，Ｇ＇的顶点数等于Ｑ。对图Ｇ＇的每一个顶点进行编码：待着色顶点Ｖ的５个围栏顶点的编码分别是x1、x2、x3、x4、x5，然后依次对剩余的顶点进行编码分别是x６、x７、………xＱ。如图2。
二、在图2中求解不同极大点独立集的数量N＇：
２、在图2中，求得Ｇ＇的不同的极大点独立集个数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中两个同色顶点B1,B2所夹的两个单色顶点Ｃ１、Ｄ１的颜色，取代这两个同色顶点的颜色，并且符合相邻顶点不同色的规则，这一步叫x1、x2、x3、x4、x5颜色冲突4转3。即： x１由A1→C 。　如图8。
四、在图8中进行下列计算程序：
4、列出由顶点编码表示的Ｑ个顶点的全集合Ｘ＝｛x1，x2，x3……x11｝。
5、由顶点编码表示的每一个顶点的围栏顶点的集合叫这个顶点的围栏集合，分别表示为x1、x2、x3……X11。
6、由所有顶点的围栏集合组成的方程组叫n-轮构形方程组。
x1＝｛x2，x5，x6，x7,x8｝。x5＝｛x1，x4，x6,x11｝。x9＝｛x2，x3，x4，x8,x10｝。
x2＝｛x1，x3，x8,x9｝。    x6＝｛x1，x5，x7,x11｝。x10＝｛x4，x7，x8，x9,x11｝。
x3＝｛x2，x4，x9｝。 x7＝｛x1，x6，x8，x10,x11｝。  x11＝｛x4，x5，x6，x7，x10｝。
x4＝｛x3，x9，x10,x11｝。 x8＝｛x1，x2，x7，x9,x10｝。
７、在x1、x2、x3、x4、x5颜色冲突4转3后，这一例不进行五加一3色锁定，而是只做x1、x2、x3、x4、x5中的3色锁定。然后将其顶点颜色标称相同的为同一个集合，每一个集合的标称除和其所含的顶点颜色标称相同外，右下角再加其顶点编码，这一步叫4转3后的3色锁定。在构形中将4转3后3色锁定时没有锁定的顶点的原着色全部解除只留编码。如图9。
五、如图9中进行下列计算程序：
８、真同色集和伪同色集：顶点相互间是互不相邻的同色顶点的极大点独立集叫右下角顶点编码的真同色集或右下角顶点编码的极大点独立集。顶点相互间可能是互不相邻的同色顶点的集合叫右下角顶点编码的伪同色集。
4转3后3色锁定后，三个集合都是伪同色集。其集合的标称或A（顶点编码）或B（顶点编码）或C（顶点编码）或D（顶点编码）。伪同色集中的顶点没有全部确定为是互不相邻的顶点。
如图9中：Bx2, x5的伪同色集是B x2, x5＝｛ x2, x5：……｝，　Ｃx1,x4的伪同色集是Ｃx1,x4＝｛x1,x４：……｝，Ｄx３的伪同色集是Ｃx３＝｛x３：……｝，‘：’表示其前的顶点是互不相邻的顶点，其后的顶点是没有确定为互不相邻的顶点。
９、在各个伪同色集中，依据n-轮构形方程组，求解极大点独立集群，群中每个极大点独立集的标称除和编码顶点的颜色相同外，在右下角加序号１、２、３、……m１。（不同的伪同色集产生的极大点独立集分别为m１、m２、m３）。这些极大点独立集叫编码顶点的极大点独立集群。
如图9中：伪同色集Bx2, x5＝｛x2, x5：……｝，伪同色集Ｃx1,x4＝｛x1,x４：……｝，伪同色集Dx３＝｛x３：……｝中‘……’的求法:
①先求在所有顶点中减去已经锁定的顶点后的Y集合：
Y=x－Bx2, x5－Ｃx1,x4－Dx３=x－｛x2, x5：｝－｛x1,x４：｝－｛x３：｝=｛x6、x7、x8、x９、x10、x１１｝
伪同色集中的‘……’等于 Y中和其‘：’前没有相邻关系的顶点。
②依据：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｝。
③伪同色集Bx2, x5＝｛x2, x5：x7，x10｝,伪同色集Ｃx1,x4＝｛x1,x４：｝，伪同色集Dx３＝｛x３：x6,x7,x8,x10,x11｝。
④伪同色集Bx2, x5＝｛x2, x5：x7，x10｝依据，x7＝｛x1、x6、x8、x10、x11｝,x10＝｛x4、x7、x8、x9、x11｝。
∴ B1=｛x2, x5, x7：｝, B2=｛x2, x5, x10：｝
⑤伪同色集Ｃx2,x4＝｛x1,x４：｝，
∴Ｃ１＝｛x1,x４：｝。
⑥伪同色集Ｄx３＝｛x３：x6,x７,x８,x10,x11｝，依据x6＝｛x1，x5，x7,x11｝、x7＝｛x1、x6、x8、x10、x11｝、x8＝｛x1、x2、x7、x9、x10｝、x10＝｛x4、x7、x8、x9、x11｝、x11＝｛x4，x5，x6，x7，x10｝。中没有x３，但x７,x８,x10是互为相邻的。
∴Ｄ１＝｛x3,x6,x8：｝，Ｄ２＝｛x3,x6,x１０：｝，Ｄ３＝｛x3,x８,x１１：｝。
⑦已有的极大点独立集群：
B的极大点独立集群：
B1=｛x2, x5, x7：｝。
B2=｛x2, x5, x10：｝。
Ｃ的极大点独立集群：
Ｃ１＝｛x1,x４：｝。
Ｄ的极大点独立集群：
Ｄ１＝｛x3,x6,x8：｝。
Ｄ２＝｛x3,x6,x１０：｝。
Ｄ３＝｛x3,x８,x１１：｝。
１0、分别在３个不同的极大点独立集群中各取一个极大点独立集进行组合成一个三合一的并集群，群中每一个并集分别表示为Ｘ并1、Ｘ并2……Ｘ并m。（m＝m１×m２×m３＝6）。
Ｘ并1＝B１+Ｃ１+Ｄ１＝｛x2, x5, x7：｝+｛x1,x４：｝+｛x3,x6,x8：｝
Ｘ并２＝B１+Ｃ１+Ｄ２＝｛x2, x5, x7：｝+｛x1,x４：｝+｛x3,x6,x1０：｝
Ｘ并３＝B１+Ｃ１+Ｄ３＝｛x2, x5, x7：｝+｛x1,x４：｝+｛x3,x8,x11：｝
Ｘ并４＝B２+Ｃ１+Ｄ1＝｛x2, x5, x１０：｝+｛x1,x４：｝+｛x3,x6,x8：｝
Ｘ并５＝B２+Ｃ１+Ｄ２＝｛x2, x5, x１０：｝+｛x1,x４：｝+｛x3,x6,x1０：｝
Ｘ并＝B２+Ｃ１+Ｄ３＝｛x2, x5, x１０：｝+｛x1,x４：｝+｛x3,x6,x11：｝
１1、求每一个并集分别与全集Ｘ的补集，分别表示为Ｘ补１、Ｘ补２、Ｘ补３、……Ｘ补m ，这一步也叫极大点独立集的筛选。m＝６。
Ｘ补１=Ｘ－Ｘ并1=Ｘ－【｛x2, x5, x7：｝+｛x1,x４：｝+｛x3,x6,x8：｝】
＝｛x９，x１０，x１１｝。
Ｘ补2=Ｘ－Ｘ并2=Ｘ－【｛x2, x5, x７：｝+｛x1,x４：｝+｛x3,x6,x１０：｝】
＝｛x８，x９，x１１｝。
Ｘ补３=Ｘ－Ｘ并３=Ｘ－【｛x2, x5, x7：｝+｛x1,x４：｝+｛x3,x8,x11：｝】
＝｛x６，x９，x１０｝。
Ｘ补４=Ｘ－Ｘ并４=Ｘ－【｛x2, x5, x１０：｝+｛x1,x４：｝+｛x3,x6,x8：｝】
＝｛x７，x９，x１１｝。
Ｘ补５=Ｘ－Ｘ并５=Ｘ－【｛x2, x5, x１０：｝+｛x1,x４：｝+｛x3,x6,x１０：｝】
＝｛x７，x８，x９，x１１｝。
Ｘ补６=Ｘ－Ｘ并６=Ｘ－【｛x2, x5, x１０：｝+｛x1,x４：｝+｛x3,x8,x11：｝】
＝｛x６，x７，x９｝。
依据：：x6＝｛x1、x5、x7、x11｝，x7＝｛x1、x6、x8、x10、x11｝, x9＝｛x2，x3，x4，x8,x10｝，x11＝｛x4，x5，x6，x7，x10｝。在Ｘ补1至Ｘ补６中：没有在补集群中筛选出极大点独立集。所以，本计算程序在此停止。
12、本计算程序在此停止原因如下：
张域典《四色问题探秘》的H构形中的一个F=5的F－轮构形图7•3-4，如图１。本例题在x1、x2、x3、x4、x5颜色冲突4转3的三色锁定中，发生了x1、x4不可锁定是同色的情况，这是由x1、x2、x3、x4、x5之外的顶点关系决定的一个特点，不属于本计算程序的漏洞。