四色定理怎么机器证明

① 数学发烧友进来

2006年4月,正在主来讲"神经网络自"的科大信息学院陈贤富老师突然被自己在黑板上随便画的 5 阶Hopfield联想记忆模型"惊"了片刻.为何5 阶Hopfield联想记忆模型(K5)具有奇特的、"立体的美感"?! 被这一瞬间的灵感触发, 联想起著名的四色问题, 陈贤富博士针对任意简单连通图的k染色问题展开了持续的思索和研究, 终于提出了基于不可约肯普链团的k色猜想, 并于最近彻底攻克"格思里四色猜想"的数学证明问题. 此外,在机器证明方面,陈贤富博士也提出了一个将人类卓越的归纳推理能力与计算机高速的计算能力相结合的证明四色猜想的新方法。基本思路是让机器证明一个规模相当小的染色特例问题（在个人电脑上可以简单方便地验证），再运用数学归纳法，将机器证明的特例归纳推广到一般情形。真可谓"殊途同归,一通百达!"

② 四色定理用计算机怎么证明

四色猜想是世界近代三大数学难题之一。四色猜想的提出来自英国。1852年,毕业於伦敦捶的弗南西斯·格思里(Francis Guthrie)来到一家科研单位搞地图着色工作时,发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家著上不同的颜色。”这个结论能不能从数学上加以严格证明呢?他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠,可是研究工作没有进展。
1852年10月23日,他的弟弟就这个问题的证明请教他的老师、著名数学家德·摩尔根,摩尔根也没有能找到解决这个问题的途径,于是写信向自己的好友、著名数学家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后,对四色问题进行论证。但直到1865年哈密尔顿逝世为止,问题也没有能够解决。
1872年,英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题,于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间,著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文,宣布证明了四色定理,大家都认为四色猜想从此也就解决了。
11年后,即1890年,数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久,泰勒的证明也被人们否定了。后来,越来越多的数学家虽然对此绞尽脑汁,但一无所获。于是,人们开始认识到,这个貌似容易的题目,其实是一个可与费马猜想相媲美的难题:先辈数学大师们的努力,为后世的数学家揭示四色猜想之谜铺平了道路。
进入20世纪以来,科学家们对四色猜想的证明基本上是按照肯普的想法在进行。1913年,伯克霍夫在肯普的基础上引进了一些新技巧,美国数学家富兰克林於1939年证明了22国以下的地图都可以用四色着色。1950年,有人从22国推进到35国。1960年,有人又证明了39国以下的地图可以只用四种颜色着色;随后又推进到了50国。看来这种推进仍然十分缓慢。电子计算机问世以后,由于演算速度迅速提高,加之人机对话的出现,大大加快了对四色猜想证明的进程。1976年,在J. Koch的算法的支持下,美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿判断,终于完成了四色定理的证明。四色猜想的计算机证明,轰动了世界,当时中国科学家也有在研究这原理。它不仅解决了一个历时100多年的难题,而且有可能成为数学史上一系列新思维的起点。
证明方法将地图上的无限种可能情况减少为1,936种状态(稍后减少为1,476种),这些状态由计算机一个挨一个的进行检查。这一工作由不同的程序和计算机独立的进行了复检。在1996年,Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas使用了一种类似的证明方法,检查了633种特殊的情况。这一新证明也使用了计算机,如果由人工来检查的话是不切实际的。
四色定理是第一个主要由计算机证明的理论,这一证明并不被所有的数学家接受,因为它不能由人工直接验证。最终,人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任。
缺乏数学应有的规范成为了另一个方面;以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿!”

德·摩尔根:地图四色定理

地图四色定理最先是由一位叫古德里(Francis Guthrie)的英国大学生提出来的。德摩尔根(A,DeMorgan,1806～1871)1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明四色定理的设想与感受。一个多世纪以来,数学家们为证明这条定理绞尽脑汁,所引进的概念与方法刺激了拓扑学与图论的生长、发展。1976年美国数学家阿佩尔(K.Appel)与哈肯(W.Haken)宣告借助电子计算机获得了四色定理的证明,又为用计算机证明数学定理开拓了前景。以下摘录德摩尔根致哈密顿信的主要部分,译自J. Fauve1 and J.Gray(eds.),The History of Mathematics :A Reader,pp. 597～598。
德·摩尔根致哈密顿的信(1852年10月23日)

我的一位学生今天请我解释一个我过去不知道,现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分著上颜色,使任何具有公共边界的部分颜色不同,那麽需要且仅需要四种颜色就够了。下图是需要四种颜色的例子。现在的问题是是否会出现需要五种或更多种颜色的情形。就我目前的理解,若四个不订分割的区域两两具有公共边界线,则其中三个必包围第四个而使其不与任何第五个区域相毗邻。这事实若能成立,那麽用四种颜色即可为任何可能的地图着色,使除了在公共点外同种颜色不会。

现画出三个两两具有公共边界的区域ABC,那麽似乎不可能再画第四个区域与其他三个区域的每一个都有公共边界,除非它包围了其中一个区域。但要证明这一点却很棘手,我也不能确定问题复杂的程度一对此您的意见如何呢?并且此事如果当真,难道从未有人注意过吗?我的学生说这是在给一幅英国地图着色时提出的猜测。我越想越觉得这是显然的事情。如果您能举出一个简单的反例来,说明我像一头蠢驴,那我只好重蹈史芬克斯的覆辙了……。

③ 在中国，一个能在纸面上利用简单方法证明出地图四色定理的人是一个怎么样的人

是个天才。不过”一个能在纸面上利用简单方法证明出地图四色定理的人“和”一个自以为能在纸面上利用简单方法证明出地图四色定理的人“是有区别的。

④ 为什么用机器证明四色猜想就行·

四色定理的机器证明，不是说证明所有的数。而是首先将所有可能的图映射到一千多个构型上，然后用机器证明了这一千多个构型全都是可4染色的。

⑤ 黎鸣是怎么证明四色定理的

1、首先是都知道四色定理是来源于地图的,而地图则是来源于,对于球体剖开之后,数学的投影变版换.因此可以权将四色定理,由平面问题转换成体的问题.
2、而对于体的问题,就四色定理而言,最简单的体模型,就是一个四面体——它有四个顶点,有四个面,如果把四个面涂上四种不同的颜色.
3、如果用刀从半截上破开一个四面体,就会得到一个五面体,对于新出现的平面,周边有三个平面相邻；为其涂上那个不相邻的平面的颜色——于是符合四色定理.
4、依次类推,从直观上,就可以得知,对于一个多面体,总可以通过切掉一个顶点（最多只包括一个顶点）的办法来增加一个新的平面……无穷下去,就可以无限逼近于球体.
5、对于最后得到的某个程度上的,类球体,将其用抽象地图的方式,便可以得到平面地图.
需要注意的问题：
1、对于最后得到的平面地图,只要不致于使得,某些线段变成无穷,可以通过拉扯其结点的方式,以切合我们的现实地图.
2、四色可以填充最简单的四面体,这个事实就是四色定理的证明,简单到不用证明。

⑥ 四色猜想是怎样的此问题为何会困扰数学家近半个世纪

到目前为止，四色猜想仍然是计算机证明的数学问题的一个独特的例子，但它显示了机器证明时代的到来。它可能为人们与机器合作解决问题开辟一条新途径，成为数学一系列新思维的起点。其次，四色猜想的证明是对人工智能机器与人类自身关系的验证。通过人工智能的应用，找到解决一些数学问题的方法不应该给人们带来一些顾虑，在人工智能机器面前。

那么它们必须用不同的颜色来绘制，为了充分证明四色猜想的稳定定理，我们仍然需要在概念上努力工作，特别是找到可约构型，即，将大量区域的问题简化为少量区域的情况。在 20世纪60年代和 20世纪70年代，估计有 8，000 到 10，000 种这样的配置，这是计算机无法做到的。

关于四色猜想是怎样的此问题为何会困扰数学家近半个世纪的问题，今天就解释到这里。