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

博文

Zmn-0859 薛问天: 给任意地图排四色标注的程序并不复杂

已有 181 次阅读 2022-4-17 10:43 |个人分类:数学啄木鸟|系统分类:论文交流

Zmn-0859 薛问天:  给任意地图排四色标注的程序并不复杂

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

 

 

给任意地图排四色标注的程序并不复杂

薛问天

xuewentian2006@sina.cn

 

薛问天-s.jpg最近在科学网《数学啄木鸟专栏》中看到有关四色问题的讨论。确实在理论上严格证明,任何平面地图,都可只用4种颜色来标注各国(限制不允许在他国有超地),使邻国颜色不同。确实有一定的难度。甚至要借助计算机来证明。但是在实际上为任何地图安排四色标注这件事,在逻辑上并不复杂,只有一项明确的要求,那就是相邻国的颜色不同。因为邻国太多,因而人们用手脑直接去安排,是很费事的。但是用计算机编个程序去完成,则并不复杂。

为此我就动手编了个程序,来为任何给出的地图,去找出四色标注的方案。这个程序很快就调试成功了。下面就简单介绍一下我用此程序为两个例图所求出的结果,我原以为可能程序要运行很长时间,但事实上很快。就在我普通的筆记本电脑上,不到一秒钟就可给出一个结果来,相当快。

 

例图1。

要让程序安排四色标注,当然首先要把地图的描述输入给程序。告诉程序地图中国家的数目等于多少,告诉图中哪些国家相邻。即如果用小于总国数的自然数0,1,2...,来表示各国家,就要表示有哪些i和j表示的囯家相邻。我们选的第一个例图就是所谓的Heawood反例,早先还有人认为它是不可以用四色标注的。

1反例d-001.jpg

可以㸔出它用25个点来标明25个国家。用点同点之间有连线表明它们相邻。我们用0,1,2,...,24,来标明这25个点。于是用i#j来标明国家的相邻,例如在把这些数据输入给计算机后所显示的内容。

Untitled-8.jpg

当计算机确认了这些输入的数据后,就可进行计算,并给出它的回答,为每个点给出标注的颜色,我们用0,1,2,3表示四种不同的颜色,于是计算程序就为每个点给出一个颜色来。这就是计算机对每个点i给出的gi的方案。

Untitled-9.jpg

我们可以很快验明这个方案是正确的,即相邻的国家颜色不同。

这个程序不仅可给出一个方案,而是可以给出所有的合格方案。要知道满足邻国颜色不同的四色标注方案很多很多,我们不可能在这里一一列出,我们只在这里随意地现出第101个,第201个,第301个和第401个方案来,让大家看㸔。

Untitled-10.jpg

1Untitled-11.jpg

Untitled-12.jpg

Untitled-13.jpg

程序最后给出,所有的合格的不同方案共513个。

Untitled-14.jpg

 当然这里只指的是不同构的方案,由0,1,2,3的任何不同排列构成的方案称为同构方案。如果把同构方案也㸔作是不同方案,那就更多,要乘上24 (=4!)。

 

例图2。

我们知道上图对地图的描述,是用点来表示国家,用点间的连线表示国家的相邻。而实际的地图是用线所围绕的空间表示国家,而由线相隔的国家是相邻的。我们为方便起見,仍以上图作为这样描述的地图实例,来进行一下实例计算。这样就需对每个空间标明国号,如下图。

1反例d-002.jpg


而国家间的相邻关系如下。这是计算机显示的国家间相邻的数据。

002-9.jpg

当程序确认了这些数据后,进行计算,很快就给出了四色标注的第1个方案来。

002-10.jpg

这个案例的合格方案比例1还更多,我下面显示它的第10方案,第100方案,第1000方案,第10000方案,第100000方案,第1000000方案,


002-11.jpg

002-12.jpg

002-13.jpg

002-14.jpg

002-15.jpg

002-16.jpg

 

还没完,这些方案几分钟就做完了,不知还有多少方案,我没时间继续做下去了。如果需要,还可以继续做下去。直至全部完成。


最后我谈谈程序的结构。

这个程序并不复杂,相对是比较简单的。数据结构只有两个,一个表示地图的相邻,用一个二维向量(矩阵)gl( i,j)来表示,如果i国同j国相邻且i<J则令gl(i,j)=1,否则令gl(i,j)=0。再一个数据结构就是向量gs(i),表示所求方案中第i国的颜色。

程序中的函数只有一个,就是判断这样安排的国家颜色方案是否不合格,是否存在某个国的颜色同其相邻国的颜色相同。具体说就是判断是否存在i和j,使gl(i,j)=1而且gs(i)=gs(j)。

程序本身就是一个while循环语句,来为每个国家一个个地试探性安排颜色,然后判断是否合格,如果不合格则重新安排,如果全部国家的颜色安排后是合格的,则给出一个方案。然后再去给出第二方案,第三方案,...。等给不出合格方案时,就算出了全部合格方案的个数。

程序不长,也就是100左右。程序并不复杂。但功能很全,能为任何地图安排出合格的四色标注方案,而且在需要时,所有合格的方案都可一一列出,并算出这些合格方案的个数。

 

 

 

 

返转到

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

       











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

上一篇:Zmn-0858 Thebeater: 回复薛问天先生0857
下一篇:Zmn-0860 许寿椿:回复Zmn-0859

0

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

数据加载中...

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

GMT+8, 2022-6-26 13:49

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部