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

晋源泉

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



例３、构形选择：雷明的L构形中的一个F=5的F－轮构形如图１０。
计算程序运行过程 ：
一、在构形图中对各个顶点进行编码：
１、在顶点Ｖ外还有Ｑ个顶点的构形图Ｇ中如图１０，Ｇ的顶点数等于Ｑ＋Ｖ，Ｇ＇的顶点数等于Ｑ=14。对图Ｇ＇的每一个顶点进行编码：待着色顶点Ｖ的５个围栏顶点的编码分别是x1、x2、x3、x4、x5，然后依次对剩余的顶点进行编码分别是x６、x７、………x14。如图１１。
二、在图２中求解不同极大点独立集的数量N＇：
２、在图１２中，求得Ｇ＇的不同的极大点独立集个数N＇，N＇＝４。在构形中同色顶点的编码为同一个极大点独立集，这个极大点独立集的标称和顶点颜色的标称（Ａ、Ｂ、Ｃ、Ｄ）相同。
Ａ＝｛x２,x７,x９,x1３｝、Ｂ＝｛x１,x３,x６,x１１｝、Ｃ＝｛x５,x１２,x１４｝、Ｄ＝｛x４,x８,x10｝。
三、在图1１中进行x1、x2、x3、x4、x5颜色冲突4转3：
３、用x1、x2、x3、x4、x5中两个同色顶点B1,B2所夹的两个单色顶点Ｃ１、Ｄ１的颜色，取代这两个同色顶点的颜色，并且符合相邻顶点不同色的规则，这一步叫x1、x2、x3、x4、x5颜色冲突4转3。即：x１由B1→Ｄ。X３由B2→Ｃ。如图１２。

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

六、求解每个可约方案的集合并作图。
１7、由计算方法解得F=5的F－轮构形可约，总有Ｋ≥1个不同的第四极大点独立集。在含有不同的第四极大点独立集的构形中，除待着色顶点及其围栏顶点的着色不变外，K值不同时：其他顶点的着色有部分不同。
１8、由计算方法解得这个F=5的F－轮构形可约，不同的第四极大点独立集有Ｋ＝2个，雷明的Ｌ构形中的这个F=5的F－轮构形可约的方案就有2个，每个可约方案的集合等于4个极大点独立集的并集，分别是Z1，Z2。如图１４、图１５。
Z1＝Ａ1+Ｂ1+Ｃ1+Ｄ3＝｛x2,x7,x9,x１１：↑x6，x12，x14,v：↑x3,x5,x7,x１0：↑x1,x4,x８,x１3：｝
Z2＝Ａ2+Ｂ2+Ｃ１+Ｄ１＝｛x2,x7,x9,x１3：↑x６，x１2，x14 ,v：↑x3,x5,x7,x１0：↑x1,x4,x8,x１１：｝