何谓“四色猜想”的计算机证明？

lkvc · 发表于 2006-6-17 00:41:38

我早就听说过“四色猜想”猜想，但一直对它的证明不关心，今天看了方舟子的《质疑中国哲学狂人证明四色定理》，其中写道：

众所周知，四色难题早在1976年已由美国数学家哈肯与阿佩尔借助计算机证明了。黎鸣认为，“电子计算机获得的证明是难以让人信服的，人们无法检验计算机所做出的100亿次以上的判断”，这显然是误把计算机所做的运算次数当成了证明步骤了。如果计算机运算有误，那就是硬件出了故障，只要把程序拿到别的计算机上运算，看是否有同样的结果，就可以排除硬件发生故障的可能性。
　　还有一种可能性，是哈肯与阿佩尔编的证明程序中存在未发现的漏洞。这种可能性可以由别人独立地编程、验证来排除。实际上，在他们之后，也有别人改进哈肯与阿佩尔编的证明方法，独立地证明了四色定理。哈肯与阿佩尔是把地图的无限种可能情况简约为1936种构型，后来又简约为1476种，但是要靠人工一个个去验证这么多的构型是不现实的，所以才借助计算机进行验证。在1996年，罗伯森等人又进一步简约为633种构型，再用计算机验证。在2004年，沃纳和冈席尔用通用的数学证明验证程序，对罗伯森等人的证明进行了验证，肯定了其证明的正确性。至此，人们对计算机证明的最后一丝疑问，也应该可以消除了。

我对其中的“哈肯与阿佩尔是把地图的无限种可能情况简约为1936种构型，后来又简约为1476种”很感兴趣，这是如何做到的？

lkvc · 发表于 2006-6-17 19:33:26

诚心请教，愿高人教我解疑惑

长歌－废墟 · 发表于 2006-6-17 20:20:05

据我所知,四色定理的证明是用穷举法一个个情况验证的,至于约化无非是用了一些数学定理吧,不过我对这方面不清楚,希望有会员解答,解答对的愿意给两个威望奖励.

调侃 · 发表于 2006-6-17 21:02:52

推荐一个四色定理的论坛

http://www.channelwest.com/bbs/forum.asp?Forum_ID=8

长歌－废墟 · 发表于 2006-6-17 23:05:04

那论坛倒是不错,但是民间科学家太多了,这帮人难缠啊,我在一个地方和他们较量过,实在无聊,比如说三等分角,不可能证明我估计他们都没看过,就瞎说,一个个自以为比高斯还厉害.

lkvc · 发表于 2006-6-17 23:43:31

谢谢调侃提供的信息，我初步看了一下，都是争先恐后“创新”的

我现在连哈肯与阿佩尔的证明都没弄清楚，还是先不管那些“创新”吧

我对方文中“哈肯与阿佩尔是把地图的无限种可能情况简约为1936种构型，后来又简约为1476种”的初步理解：
在二维平面中，所有地图组合都可以由1936或1476种构型推导出，姑且称这种推导为运算吧，这种构型之间的运算是完备的，任意两种构型的运算结果必为这1936或1476种构型之一，只有这样，用计算机证明地图的无限种可能情况才有意义。

我现在就是想弄明白我的理解对不对？

aπολλωv · 发表于 2006-6-17 23:55:25

四色问题和图论联系颇深，还有就是几何拓扑

下面是偶从网上搬的旧兵.........

四色定理证明的基本方法是十分简单的，是经典归纳法的一个变型；如果一个地图不是四种颜色则必存在一个具有最少国家数目的反例；研究了“最小反例”的两种性质：(一)如果存在最小反例，则必存在正则地图为最小反例，(二)在正则最小反例地图中，每个国家的边界为圈。第4章从拓扑到组合，四色定理可以形成为纯组合的命题，涉及Wagner和Fary定理，Euler多面体公式，地图的对偶理论，包含了证明四色定理的完整基础和所需要的公式。第5章四色定理的组合形式，拓扑四色定理有效，而且每个平面图有一个相容的顶点4?染色，也就是把一个拓扑地图的四色问题变为一个组合图的顶点4染色问题，讨论了构型、不可约和不可避免构型。第6章约简，论述约简方法，叙述Durre-Heesch约简算法。第7章不可约集的搜索，Heesch算法涉及搜索可约构型的不可避免集合，主要有三个“障碍”，论述了解决这些障碍的规则方法。

《The Four-Color Theorem》
1998, 260pp..
Hardcover DM 69.00
ISBN:0-387-98497-6
1 Springer-Verlag
《四色定理》
鲁道夫和G.弗雷茨著

lkvc · 发表于 2006-6-18 00:07:53

谢谢hooker提供的信息，不过其中很多信息对我来说太专业了。我能理解“最小反例”的思路，也能理解“从拓扑到组合，四色定理可以形成为纯组合的命题”，但对“正则地图”、Wagner和Fary定理、Euler多面体公式、地图的对偶理论、组合图的顶点4染色问题等术语就一无所知了。

长歌－废墟 · 发表于 2006-6-18 00:09:54

引用第7楼lkvc于2006-06-18 00:07发表的“”:
谢谢hooker提供的信息，不过其中很多信息对我来说太专业了。我能理解“最小反例”的思路，也能理解“从拓扑到组合，四色定理可以形成为纯组合的命题”，但对“正则地图”、Wagner和Fary定理、Euler多面体公式、地图的对偶理论、组合图的顶点4染色问题等术语就一无所知了。

所以兄要学啊,我至少知道多面体公式

.

lkvc · 发表于 2006-6-18 00:21:47

引用第8楼长歌－废墟于2006-06-18 00:09发表的“”:

所以兄要学啊,我至少知道多面体公式.

引用第9楼hooker于2006-06-18 00:13发表的“”:

书名我已经提供了...........我也只能是望梅止渴.........

多谢两位斑竹，我目前还不想改行，能弄明白最好，弄不明白也不求己过

		自动登录	找回密码
密码			注册

[【理工类】] 何谓“四色猜想”的计算机证明？