《数学啄木鸟专栏》分享 http://blog.sciencenet.cn/u/wenqinghui 对错误的数学论点发表评论

博文

Zmn-0861 薛问天: 四色标图程序的进一步调试和验证。兼评许寿椿先生的《0860》

已有 240 次阅读 2022-4-22 21:14 |个人分类:数学啄木鸟|系统分类:论文交流

Zmn-0861 薛问天: 四色标图程序的进一步调试和验证。兼评许寿椿先生的《0860》

【编者按。下面是薛问天先生的文章,兼评许寿椿先生的《Zmn-0860》。现在发布如下,供网友们共享。请大家关注并积极评论。另外本《专栏》重申,这里纯属学术讨论,所有发布的各种意见仅代表作者本人,不代表本《专栏》编辑部的意见。《专栏》中有些文章发扬了啄木鸟精神,对一些错误的观点和言论进行了说理的批评。但请大家注意,也有些有严重错误的文章在这里发布,就是为了引起和得到广大网友们的评论。不要以为在这里发布的文章都是正确无误的。】

 

 

四色标图程序的进一步调试和验证。

兼评许寿椿先生的《0860》

薛问天

xuewentian2006@sina.cn

 

薛问天-s.jpg我编了一个对任何平面地图,自动用四色标注,而保证邻国颜色不同的程序。而且这个程序可以给出全部的所有的合格标注方案,并算出合格方案的数量。

最近我对程序作了进一步的调试和验证。发现计算的数量多算了一个,现已作了调整和更正。另外又选了几个简单的图例,进一步验证了程序的正确性。

一,对程序的进一步调整,和对计算的合格方案数gsn的确切含义作准确的解释。

在调试中,我发现在打印合格标注方案数量gsn时,多算了一个,现己将程序更正。也就是说,对例1的Heawood反例,正确的gsn数量应是gsn=512。而不是513 。

li-1-gsn.jpg

关于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个。程序打印出它们的相邻关系,

lizi-3 拷贝.jpg

li-3-gl.jpg

程序算出的所有四色标注方案方案gs1,gs2,...,gs12,共12个方案。由于数量少,我就全部打印出来了,可以进行分析。

lizi-3-5-gs-1-6.jpg

lizi-3-5-gs-7-12.jpg

li-3-gsn.jpg

验证出全是合格方案,相邻国家不同色,说明程序是正确的。

另外㸔出前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个国家。

下面是点图及和程序打出的相邻关系。

lizi-004.jpg

li-4-gl.jpg

程序算出只有gsn=2个方案。

li-4-gs1.jpg

li-4-gs2.jpg

li-4-gsn.jpg

同样验证出全是合格方案,相邻国家不同色,说明程序是正确的。另外可看出,gs1和gs2同构。


例5。这是在图例4上增加一条线的的图例。

下面是点图及和程序打出的相邻关系。只比例4多一个相邻,即2#4。

lizi-005.jpg

li-5-gl.jpg

显然这条蓝色线是不能加上的。它同另一条线相交了。把它输入给程序,结果算出没有方案,gsn=0。

li-5-gsn.jpg

这说明程序在这种情况下也能算出正确的结果。

四,程序没有错,有些图例,四着色的数量可能很大。

许先生说【薛先生文中谈到希伍德反例图的第1000000(百万个)四着色,此数目过大,是不可能有的。

这是许先生的理解错误,我程序中打印出的【第1000000(百万个)四着色】,说的是例2的四着色,例2并不是希伍德反例。在这个图中,是用线段包围的区域表示国家,而不是用点表示国家,所以说它不是例1所表示的希伍德反例。许先生理解错了。我在前面己解释清楚,希伍德反例共有gsn*12=512*12=6144个不同的合格四着色方案,当然不可能有第1百万个不同的四着色方案。

我要说明的是,我的程序是对任意平面图例都可计算的程序,不是只能处理希伍德反例一个图例的程序。例2不是例1,不是希伍德反例,是另一个图例。希伍德反例只有6144个四着色方案,不等于说其它的图例就不可能有更多的四着色方案,例2有超过一百万个合格的四着色方案,这是客观存在的事实,是完全可能的。说【此数目过大,是不可能有的。】是不对的。对于这个例2图例,是完全正确的。也就是说,程序算出的结果沒有错误。

许先生对我编的程序给予了很高的评价。甚至还认为【从我的阅读经历看:西方数学界似乎一直没有人给出希伍德反例的任何四着色结果;无论是人工还是用计算机。】如果真是如此,我的程序还真是作出了一定的贡献。不管如何,我在想办法把此程序进一步正规化和公开化,能让业界人士方便使用,这已成为一项有意义的工作。正如我上次所说,这个程序并不复杂。许先生也同意,说实际上【用计算机给出四着色确实很容易、很迅速就能够拿到大量结果。】而且不仅仅是【大量结果】,可以准确地说是全部的结果

当然由此也可想像出,许先生所采取的【以“电脑+软件”为工具的“四色问题的数学实验研究”,】有多么困难。【1995年得到希伍德反例的200多个四着色;2005年得到其全部四着色256个(规范化表达)。】化了十多年的艰辛努力,才逐步求出这个数字。但是用计算机的程序,几分钟就可立即完成,算出最后结果,而且是任何图例都可完成,可见方便很多。

参考文献







 

返转到

   zmn-000文清慧:发扬啄木鸟精神-《数学啄木鸟专栏》开场白及目录

       







https://blog.sciencenet.cn/blog-755313-1335189.html

上一篇:Zmn-0860 许寿椿:回复Zmn-0859
下一篇:Zmn-0862 许寿椿: 回复Zmn-0861 薛问天先生文

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-7-8 01:06

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部