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

博文

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

已有 309 次阅读 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,相邻且颜色相同。我这个函数程序是这么编的,非常简单。


function csyc() { //测试异常
        for( i=0;i<gi+1;i++){
                 for (j=0;j<gi+1;j++) {
                    if(tugl[i*m+j]==1 &&gs[i]==gs[j])                    
                                {
                                 return true;
                                }  
                  }
          }
          return false;
        }

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

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

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

我们采用的是试探的方法来求出合格方案。当然最原始的方法是先求出所有可能的探索方案,一个个地测试,然后排除所有不合格的方案,求出所有合格的方案。我们知道如果国家的数目是gn,每个国家标注的颜色有4个,那么所有的可能共有4gn个。如果gn=25,那么就有425个可能。我用计算机算了一下,425大约等于1.125*1015。我们知道一年等于31536000秒,大约等于3.15*107秒。因而如果计算机能在一秒钟算出一百万个(106)方案,则算出所有的可能就大约需要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-1-10.jpg


006-11-20.jpg

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

例子-006-gsn.jpg

 

例7(g15A)

例7-002.jpg

输入的国家相邻关系。

例子-007-gl.jpg

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

007-01-31.jpg

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

例子-007-gsn.jpg

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

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

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

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

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

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

例如下图都是偶性图。

ouhetu.jpg

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

feiouhe.jpg

可以严格证明下述定理。

定理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

可以很容易画出四着色图


颜色表达.jpg


006-100.jpg

按(0,1)(2,3)画出第一个二层偶性图

006-101.jpg

按(0,2)(1,3)画出第2个二层偶性图

006-102.jpg

按(0,3)(1,2)画出第3个二层偶性图

006-103.jpg 

因为对每个合格的四着色方案,我们都可以很容易画出相应的三个二层偶性图来。许寿椿铣对g14A画出的三个二医偶性图,实际上由我们结果的gs4可很容易画出。

们来具体查看。我们算出的第4个合格四二着色结果是 :

例子-006-gs004.jpg

可以很容易画出四着色图

006-000.jpg

按(0,1)(2,3)画出第一个二层偶性图

006-001.jpg

按(0,2)(1,3)画出第2个二层偶性图

006-002.jpg

按(0,3)(1,2)画出第3个二层偶性图006-003.jpg当然对于g15A也是同样的。我们可以对每个合格方案(基本方案共32个,总共768个),画出三个二层偶性图来。我查阅了一下,许先生所画的三个子图,实际上是我算出的结果gs16的相应的二层偶性图。gs16是

例子-007-gs016.jpg

许先生和有兴趣的读者可以很容易地具体画出来,结果完全一样。当然如果需要,对其它的每个合格着色方案,也可画出相应的三个二层偶性图来。我就不在此一一赘述了。自然,这一切都可以看作是【结果的可视化表达】。这个可视化结果现在可用手工去做,但可以完全常规编程,用计算机把它们画出来。这已是容易的事了。

 

 

返转到

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

       






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

上一篇:Zmn-0862 许寿椿: 回复Zmn-0861 薛问天先生文
下一篇:Zmn-0864 薛问天: 关于√2不是有理数的证明沒有错误。回复weikeli先生的两封来信,

0

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

数据加载中...

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

GMT+8, 2022-7-8 00:18

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部