博文

Zmn-0863 薛问天: 关于四着色方法同许寿椿先生的讨论，回复《0862》。

已有 976 次阅读 2022-5-10 23:02 |个人分类:数学啄木鸟|系统分类:论文交流

Zmn-0863 薛问天: 关于四着色方法同许寿椿先生的讨论，回复《0862》。

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

关于四着色方法同许寿椿先生的讨论，

回复《0862》。

薛问天

xuewentian2006@sina.cn

薛问天-s.jpg 对于我编制的那个对任何平面地图，能自动用四色标注，保证邻国颜色不同的程序。而且这个程序可以给出全部的所有的合格标注方案，并算出合格方案的数量。许寿椿先生，作为一位专门研究四色问题的专家，对此程序给予了很高的评价。最近在《0862》中，向我提出了四个问题，我当然非常高兴能同许寿椿先生进行讨论。

许寿椿提出的四个问题是:

①，【我确实前后花了近十年得到希伍德反例图的全部四着色。原因是求全部四着色的“色多项式计算”遇到困难。薛先生不知道用的什么高招。请予指教。】

②，【还有希伍德反例图有不少四着色二色子图Gij 都是树型图，此类着色十分耗费机器时间。不知道您是如何处理的。】

③，【还有希望薛先生的四着色结果能够可视化表达。】

④，【另外如下两个小图g14A,g15A,您的全部四着色是多少？】

一，程序的进一步改进和调整。

首先还需要说明一下，我对程序又作了进一步的改进和调整。即合格着色方案，最后就选择是不同构的方案，从而计算出的数量sgn，就等于所有不同构的合格着色方案的数量。从而所有合格方案的数量就是n=4!*sgn(=24*sgn)，我们的不同构方案等价于许先生提出的满足【规范化表达】。所以关于希伍德反例图的例1的正确回答成为:

例子-001gn.jpg

另外发现原例3的数据输入有错，多加了邻边【0#6】，改正后例3的正确结果是:

例子-003gn.jpg

二。着色程序所用的基本方法。

我们现在来讨论问题①。许寿椿先生说【求全部四着色的“色多项式计算”遇到困难。】如果把图中各国的颜色看作是未知数，那么相邻国家的颜色不相同，就为这些未知数给出了很多【色不相同】的方程式。因而求各国的合格着色方案就是对这些方程的求解过程。因而问题的关键就是如何为此方程求解。许寿椿先生釆取的办法，是对图形的结构进行分析，探讨怎样的结构可以用四着色来使相邻国的颜色不同。当然这样的理论分析是相当复杂的。从而会遇到困难，正如许先生所说【求全部四着色的“色多项式计算”遇到困难。】

而我编的求着色方案的程序使用的方法并不是如此，并不需要对图的结构作任何理论分析。对所有的图形都只进行同样的统一处理，就是采用试採的求解方法，排除掉不合格的方案，要求相邻国家颜色不同，就只此一项要求，相对来讲非常简单。也就是说编了一个函数，它能判断试採的着色方案不合格(异常)，在国家0到国家gi间，存在国家i和j，相邻且颜色相同。我这个函数程序是这么编的，非常简单。

其中tugl[i*m+j]==1 表示i国同j国相邻。gs[i]==gs[j]，表示两国的颜色标注相同。

三，用可重复操作的递归程序技术，即ωhi1e循环语句，实现从少到多个国家着色的探测，从而大大減少了循环次数。

现在来讨论②，关于时间耗费的问题。

我们采用的是试探的方法来求出合格方案。当然最原始的方法是先求出所有可能的探索方案，一个个地测试，然后排除所有不合格的方案，求出所有合格的方案。我们知道如果国家的数目是gn，每个国家标注的颜色有4个，那么所有的可能共有4^gn个。如果gn=25，那么就有4²⁵个可能。我用计算机算了一下，4²⁵大约等于1.125*10¹⁵。我们知道一年等于31536000秒，大约等于3.15*10⁷秒。因而如果计算机能在一秒钟算出一百万个(10⁶)方案，则算出所有的可能就大约需要100年。显然这是办不到的。

我们的试探不是采用的这种办法，而是国家由少到多地试探。如果方案对较少量的前面几个国家已不合格，后面就不必再试了。也就是说，如果方案对少量的前面几个国家已合格了，才继续对后面的国家来试採着色测试。这样就使检测的数量減少了很多很多。使程序成为可能。用我们的方法，对希伍德反例图(25个国家)，用不到几分钟就可一个个地求出所有的256个基本合格方案来。

四，程序对例6(g14A)和例7(g15A)的运算结果。

现在来回答问题④。请注意在我的程序中，是用0,1,2,3,...来表示国家，是从0开始的，因而对图中的国家编号进行了重排。另外我们是用0,1,2,3表示四种颜色。

例6(g14A)

例6-002.jpg

输入的国家相邻关系。

例子-006-gl.jpg

程序算出的共20个合格着色方案

程序输出的全部合格方案数量。

例子-006-gsn.jpg

例7(g15A)。

例7-002.jpg

输入的国家相邻关系。

例子-007-gl.jpg

程序算出的共个合格着色方案，由于太多，这里只打印部分。

程序输出的全部合格方案数量。′

例子-007-gsn.jpg

五，关于四着色的二着色子图及程序结果的可视化表达。

现在来讨论② ③中的二着色子图和可视化表达的问题。

关于子图和二看色子图，我想先讨论它的严格数学定义。

【定义1(子图)】。我们把图的点的子集及此子集点间的所有连线构成的图，称为原图的子图。

在这个定义中，子图包含了所有子图内点间的所有连线，但不包括所有与子图外的点的连线。

【定义2(偶性图)】。我们称某图是偶性图，当且仅当此图滿足下述条件。图中的连线不形成圈，或所形成的圈都只含有偶数个点，不存在含奇数点构成圈。

例如下图都是偶性图。

而下面的图都不是偶性图。

可以严格证明下述定理。

【定理1(二着色)】。图可以只用二种颜色着色，使相邻点颜色不同，当且仅当它是偶性图。

【定义3(二层偶性结构)】。如果一个图能形成如下结构，称其为二层偶性结构图。该图刚好由有穷个(n个)偶性子图A0,A1,a2,...,An-1构成。而且把这n个子图㸔成n个点，把子图Ai和AJ在原图中有点相互连线㸔作是点Ai和点Aj有连线，由这些点及其连线就形成一个新的抽象图，这个抽象图也是偶性图。

有了这个二层偶性图的定义，就可严格证明下述定理。

【定理2(四着色)】。一个图可以用四种颜色着色，使相邻点颜色不同，当且仅当它是二层偶性图。

这个定理很容易证明，如果知原图是二层偶性图，先用颜色对(0,1)和(2,3)对抽象图的点着色，然后再分别用(0,1)和(2,3)对所有的偶性子图的点着色，从而原图得到四着色。反之也很好证明。如果原图的点已四着色，可以很容易用着色是(0,1)和(2,3)建立偶性子图和抽象图，形成二层偶性图。当然也可用着色是(0,2)(1,3)及(0,3)(1,2)形成另外两个二层偶性图。即一个四着色图可以形成三个二层偶性图。证毕。

由于在四色问题的理论研究中，1976年，数学家凯尼斯·阿佩尔(K. Appel)和沃夫冈·哈肯(W. Haken)借助电子计算机完全证明了四色定理。即证明了任何平面图形都可以用至多四种颜色标注，而使相邻国的颜色不同。那么就可以由四色定理推出下述定理。

【定理3(等价的四色定理)】。任何平面图都可表示为二层偶性图。

显然由定理2可知，定理3同四色定理是等价的定理。如果不是用1976年证明的四色定理来证明，而是直接证明了定理3，那么这就是等价的四色定理的一个新的证明。我们希望有人能作到这点。能作到这点当然是非常有意义的。

由以上分析可知，许寿椿先生提出的【四着色二色子图】，严格说应是【二层偶性图】。有了这套理论就可看出许寿椿先生举的例子g14A和g15A，旁边列的三个图就是相应的三个二层偶性图。可以㸔出许寿椿先生是分析原图的结构，在计算机的帮助下，人工找出二层偶性图来，由此图来求出原图的四着色方案。当然这是相当复杂和困难的，而我的程序是计算机用试探法直接找出所有的合格四着色方案。如果需要，对每个合格的四着色方案，都可以′很容易地画出相应的二层偶性图来，这可以看作是很容易的【结果的可视化表达】。

例如对于例6，g14A ，

对于求出的gs1这个四着色方案，

例子-006-gs001.jpg