博文
Zmn-0861 薛问天: 四色标图程序的进一步调试和验证。兼评许寿椿先生的《0860》
||
Zmn-0861 薛问天: 四色标图程序的进一步调试和验证。兼评许寿椿先生的《0860》
【编者按。下面是薛问天先生的文章，兼评许寿椿先生的《Zmn-0860》。现在发布如下，供网友们共享。请大家关注并积极评论。另外本《专栏》重申，这里纯属学术讨论，所有发布的各种意见仅代表作者本人，不代表本《专栏》编辑部的意见。《专栏》中有些文章发扬了啄木鸟精神，对一些错误的观点和言论进行了说理的批评。但请大家注意，也有些有严重错误的文章在这里发布，就是为了引起和得到广大网友们的评论。不要以为在这里发布的文章都是正确无误的。】
四色标图程序的进一步调试和验证。
兼评许寿椿先生的《0860》
薛问天
我编了一个对任何平面地图，自动用四色标注，而保证邻国颜色不同的程序。而且这个程序可以给出全部的所有的合格标注方案，并算出合格方案的数量。
最近我对程序作了进一步的调试和验证。发现计算的数量多算了一个，现已作了调整和更正。另外又选了几个简单的图例，进一步验证了程序的正确性。
一，对程序的进一步调整，和对计算的合格方案数gsn的确切含义作准确的解释。
在调试中，我发现在打印合格标注方案数量gsn时，多算了一个，现己将程序更正。也就是说，对例1的Heawood反例，正确的gsn数量应是gsn=512。而不是513 。
关于gsn的含义，我上次说【这里只指的是不同构的方案，由（0,1,2,3）的任何不同排列构成的方案称为同构方案。如果把同构方案也㸔作是不同方案，那就更多，要乘上24 (=4！)。】经过仔细分析，这种说法不对。我的gsn的数量是令国家0的颜色为0，gs[0]=0，和国家1的颜色为1，gs[1]=1的所有不同的合格标注方案的数量，它应等于不同构方案个数的2倍。因为在我提供的方案中包括把颜色2换为3，把3換为2的方案，刚好多了一倍的同构合格方案。所以【如果把同构方案也㸔作是不同方案，】那么所有不同的合格方案的数量 n 应等于gsn乘上12(=4*3)，n=gsn*12。当然等于不同构合格方案数量乘上24(=4!)。
这里需要对同构方案给以严格的定义。我们知道颜色(0,1,2,3)可以有24(=4!) 种排列，如(0,1,3,2)，(3,2,1,0)...等。显然一个合格的方案，把每个国家标注的相应颜色全部换成颜色(0,1,2,3)的一个排列，则换后形成的方案仍然是合格方案。例如，所換的排列是(3,2,1,0)，则需把原方案中的0换成3，1换成2，2换成1，3换成0，形成新的方案。也就是说，我们可以把方案的同构严格定义如下。把两个方案称为是同构的方案，如果能用(0,1,2,3)的一个排列将其中一个方案对换形成另一个方案。
二，关于Heawood反例，程序算出的结果同许寿椿先生分析的方案数量完全相等。
经过上述分析可知，关于Heawood反例，我用程序由电脑算出的gsn=512， 刚好是许寿椿先生多年研究而得到的256个的2倍。许先生对这256作了【规范化表达】的解释。而且许先生也说了【如果取消此规范化条件，即把颜色号对调看成是不同的四着色，那么全部四着色数目将变成：256*24=6144。】这同我刚才分析的〖所有不同的合格方案的数量 n 应等于gsn乘上12(=4*3)，n=gsn*12。当然等于不同构合格方案数量乘上24(=4!)。〗结果=6144完全相等。也就是说，如果我说的同构的概念同许先生说的【规范化表达】的概念是等价的话，则我们对于这个图例所算的结果，是完全相同的。许先生作过这样的定义，【这里规范化条件是：V1[1]<V2[1]<V3[1]<V4[1].。】这里需要仔细分析这两个概念的等价性。即满足规范化条件的方案，刚好就是无同构的合格着色方案。
三，进一步的图例验证。
关于这个程序，我曾做过例1和例2的验证。最近又选择了三个简单的图例，验证了程序的正确性。由于图例简单，合格方案较少，所以可以得到确切的验证。
例3，如下图所示，用点0,1,...,11,表示国家，共有12个。程序打印出它们的相邻关系，
程序算出的所有四色标注方案方案gs1,gs2,...,gs12,共12个方案。由于数量少，我就全部打印出来了，可以进行分析。
验证出全是合格方案，相邻国家不同色，说明程序是正确的。
另外㸔出前6个方案分别同后6个方案是同构的。例如gs1同gs9是同构的，即相对于排列(0,1,3,2)将gs1中的所有颜色2换成3，3换成2就得到gs9。用样可以看出2-7，3-8，4-10，5-11，6-12也是同构的。可以㸔出gsn=12，是不同构的方案数量6的2倍。
例4。这是个更加简单的图例，只有5个国家。
下面是点图及和程序打出的相邻关系。
程序算出只有gsn=2个方案。
同样验证出全是合格方案，相邻国家不同色，说明程序是正确的。另外可看出，gs1和gs2同构。
例5。这是在图例4上增加一条线的的图例。
下面是点图及和程序打出的相邻关系。只比例4多一个相邻，即2#4。
显然这条蓝色线是不能加上的。它同另一条线相交了。把它输入给程序，结果算出没有方案，gsn=0。
这说明程序在这种情况下也能算出正确的结果。
四，程序没有错，有些图例，四着色的数量可能很大。
许先生说【薛先生文中谈到希伍德反例图的第1000000（百万个）四着色，此数目过大，是不可能有的。】
这是许先生的理解错误，我程序中打印出的【第1000000(百万个)四着色】，说的是例2的四着色，例2并不是希伍德反例。在这个图中，是用线段包围的区域表示国家，而不是用点表示国家，所以说它不是例1所表示的希伍德反例。许先生理解错了。我在前面己解释清楚，希伍德反例共有gsn*12=512*12=6144个不同的合格四着色方案，当然不可能有第1百万个不同的四着色方案。
我要说明的是，我的程序是对任意平面图例都可计算的程序，不是只能处理希伍德反例一个图例的程序。例2不是例1，不是希伍德反例，是另一个图例。希伍德反例只有6144个四着色方案，不等于说其它的图例就不可能有更多的四着色方案，例2有超过一百万个合格的四着色方案，这是客观存在的事实，是完全可能的。说【此数目过大，是不可能有的。】是不对的。对于这个例2图例，是完全正确的。也就是说，程序算出的结果沒有错误。
许先生对我编的程序给予了很高的评价。甚至还认为【从我的阅读经历看：西方数学界似乎一直没有人给出希伍德反例的任何四着色结果；无论是人工还是用计算机。】如果真是如此，我的程序还真是作出了一定的贡献。不管如何，我在想办法把此程序进一步正规化和公开化，能让业界人士方便使用，这已成为一项有意义的工作。正如我上次所说，这个程序并不复杂。许先生也同意，说实际上【用计算机给出四着色确实很容易、很迅速就能够拿到大量结果。】而且不仅仅是【大量结果】，可以准确地说是全部的结果。
当然由此也可想像出，许先生所采取的【以“电脑+软件”为工具的“四色问题的数学实验研究”，】有多么困难。【1995年得到希伍德反例的200多个四着色；2005年得到其全部四着色256个（规范化表达）。】化了十多年的艰辛努力，才逐步求出这个数字。但是用计算机的程序，几分钟就可立即完成，算出最后结果，而且是任何图例都可完成，可见方便很多。
参考文献
返转到
zmn-000文清慧：发扬啄木鸟精神-《数学啄木鸟专栏》开场白及目录
https://m.sciencenet.cn/blog-755313-1335189.html
上一篇：Zmn-0860 许寿椿：回复Zmn-0859
下一篇：Zmn-0862 许寿椿: 回复Zmn-0861 薛问天先生文
