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

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

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

薛问天

xuewentian2006@sina.cn。

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

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

例图1。

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

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

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

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

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

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

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

例图2。

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

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

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

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

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

最后我谈谈程序的结构。

这个程序并不复杂，相对是比较简单的。数据结构只有两个，一个表示地图的相邻，用一个二维向量(矩阵)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文清慧：发扬啄木鸟精神-《数学啄木鸟专栏》开场白及目录

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

• Zmn-0858 Thebeater:  回复薛问天先生0857   2022-4-14 08:59

• Zmn-0857 薛问天:   不同的极限定义，当然有不同的特性。评Thebeater《0856》   2022-4-10 09:52

• Zmn-0856 Thebeater:  要分清集合的极限和实数的极限-评0853,0851   2022-4-6 08:57

• Zmn-0855 薛问天:   论康托尔集(三分集)可以用受一定限制的三进制无穷小数表示   2022-4-5 08:51

• Zmn-0854 新   华： 自身元素无法表示的集合的一个尝试表示   2022-4-4 10:41

• Zmn-0853 薛问天:   概念要清晰，谈无穷集合的给定。评林益先生的《0851》   2022-4-2 21:57

• Zmn-0852 李振华： 实例说明集合乘法是有效的推理方式。回薛先生《0849》。   2022-4-2 10:09

• Zmn-0851 林   益： 非常感谢薛问天老师的评论   2022-3-31 12:51

• Zmn-0850 林   益： 道理很清楚，还是感到奇怪  2022-3-29 18:02

• Zmn-0849 薛问天:   李振华先生定义的广义集合的乘法运算是不关闭的，及评李振华《0842》   2022-3-28 20:16

• Zmn-0848-4 许寿椿：对Zm n-0848-1汇报的一点补充-谈我对美国人1976年计算机证明认识的变化过程 2022-3-25 11:46

• Zmn-0848-3 许寿椿：文稿3，非退化树都是极大平面图四着色之Gk特性树   2022-3-23 16:50

• Zmn-0848-2 许寿椿：文稿2，五轮图可约性的证明  2022-3-23 10:49

• Zmn-0848-1 许寿椿：我怎样走上四色问题“数学实验或计算实验”之路-向专门家及读者汇报.  2022-3-23 09:32

• Zmn-0847 薛问天:   无穷小数并不是相应的有穷小数的无穷序列。评林益先生的《0846》   2022-3-21 13:59

• Zmn-0846 林   益： 用自身元素无法表示的集合   2022-3-20 08:26

• Zmn-0845 薛问天    道理想清楚，这里沒有矛盾，就不会感到奇怪了。评林益先生的《0843》。   2022-3-19 14:02

• Zmn-0844 李振华： 炮轰现代数学！长线段不能与短线段一一对应的数学证明。把积分推广到集合。   2022-3-17 18:00

• Zmn-0843 林   益： 一个奇怪的问题   2022-3-16 19:57

• Zmn-0842 李振华： 数学惊人发现：存在既大于0又小于0的数，存在最大正数，最小负数。   2022-3-15 11:28

• Zmn-0841 许寿椿： 回复薛问天先生《0837》的评论   2022-3-14 13:17

• Zmn-0840 薛问天： 命题的表述中缺少【量词】和【论域】是错误的关键。评杨六省先生的《0839》   2022-3-11 17:16

• Zmn-0839 杨六省： 268 个字让你确信——毕达哥拉斯学派关于√2 不是有理数的证明是无效的   2022-3-10 08:41

• Zmn-0838 双木林： 对侯小山先生Zmn-0813一文的评论   2022-3-9 20:37

• Zmn-0837 薛问天： 四色猜想已经得到严格证明，业界已公认是四色定理。请看有关介绍文章。   2022-3-3 10:16

• Zmn-0836 林   益：  回复双木林老师   2022-3-2 22:02

• Zmn-0835 许寿椿： 四色定理数学归纳法证明的一个新尝试   2022-3-1 08:23

• Zmn-0834 侯小山： 三谈开区间(0,1) 共有多少个小数，及文清慧对此文的评语(5)。  2022-2-28 10:50

• Zmn-0833 双木林： 对林 益先生Zmn-0821一文的回复和评论   2022-2-26 16:13

• Zmn-0832 侯小山： 再谈实数可数定理和基数减少法 —回复《Zmn-0826》，及文清慧对此文的评语4。   2022-2-13 16:19

• Zmn-0831 薛问天： 证明出错，並未解决世纪悬奖的难题：P vs NP问题。评重庆理工大学学报。   2022-2-8 18:46

• Zmn-0830 吴文杰： 回薛问天的《0827》《0823》   2022-1-31 09:13

• Zmn-0829 林   益： 请教文清慧老师几个问题，及文清慧的回复。  2022-1-29 11:04

• Zmn-0828 侯小山： 再谈开区间(0; 1) 共有多少个小数-回答文清慧评语，及文清慧对此文的评语   2022-1-25 15:25

• Zmn-0827 薛问天： 正确认识公理和真理的关系，不要把公理和真理对立起来。评吳文杰先生的《0824》   2022-1-24 18:39

• Zmn-0826 侯小山： 实数可数定理和基数减少法，及文清慧评语   2022-1-23 09:54

• Zmn-0825 侯小山： 开区间(0; 1) 共有多少个小数，及文清慧评语   2022-1-22 16:48

• Zmn-0824 吴文杰： 有穷不能推无穷是真理还是公理  2022-1-21 17:55

• Zmn-0823 薛问天： 吴文杰先生的【相对无穷论】让自然数中包含无穷自然数是严重错误。评《0800》   2022-1-20 13:19

• Zmn-0822 何   许：  芝诺的“阿克琉斯-乌龟悖论”的破解   2022-1-18 09:53

• Zmn-0821 林   益：  回复双木林老师的问题   2022-1-16 08:29

• Zmn-0820 薛问天： 要认清无穷序列概念的确切含义，评李鸿仪先生的《0816》   2022-1-15 08:51

• Zmn-0819 薛问天： 正确理解极限概念，极限没有可达极限和不可达极限之分。评沈卫国《0817》   2022-1-14 08:34

• Zmn-0818 双木林： 回复林 益先生的问题   2022-1-13 09:15

• Zmn-0817    2022-1-12 08:33

• Zmn-0816 李鸿仪： 实数不完全定理   2022-1-11 08:50

• Zmn-0815 薛问天： 沈卫国先生提出的所谓【新导数定义】根本不是【不需要极限概念的新微积分理论】，是谎言，必须揭穿.   2022-1-10 10:37

• Zmn-0814 侯小山： 三次致师教民先生的回信   2022-1-9 19:02

• Zmn-0813 侯小山： 为林益老师的公正之文点赞   2022-1-9 09:27

• Zmn-0812 薛问天： 幂集定理是严格证明的定理，不能说它是【猜想】，评林益先生《0806》   2022-1-8 09:02

• Zmn-0811 沈卫国： 回复 Zmn-0807 Thebeater   2022-1-7 17:48

• 科学网《数学啄木鸟专栏》Zmn-000 到 Zmn-0850 期目录：