爱华网四色定理是一个著名的数学定理，如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样；另一个通俗的说法是每个地图都可以用不多于四种颜色来染色，而且没有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界，而不仅仅是一个公共的交点。例如右图左下角的圆形中，红色部分和绿色部分是邻接的区域，而黄色部分和红色部分则不是邻接区域。
四色定理_四色定理 -基本介绍
四色问题又称四色猜想、四色定理是世界近代三大数学难题之一。地图四色定理(Four color theorem)最先是由一位叫古德里Francis Guthrie的英国大学生提出来的。德・摩尔根Augustus De Morgan180618711852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明四色定理的设想与感受。一个多世纪以来数学家们为证明这条定理绞尽脑汁所引进的概念与方法刺激了拓扑学与图论的生长、发展。1976年美国数学家阿佩尔K.Appel与哈肯W.Haken宣告借助电子计算机获得了四色定理的证明又为用计算机证明数学定理开拓了前景。
地图四色定理(Four color theorem)最先是由一位叫古德里Francis Guthrie的英国大学生提出来的。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示即“将平面任意地细分为不相重叠的区域每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”也就是说在不引起混淆的情况下一张地图只需四种颜色来标记就行
四色定理_四色定理 -发展历史
来自地图的启示
四色定理
相传四色问题是一名英国绘图员提出来的此人叫格思里。1852年他在绘制英国地图的发现如果给相邻地区涂上不同颜色那么只要四种颜色就足够了。需要注意的是任何两个国家之间如果有边界那么其边界不能只是一个点否则四种颜色就可能不够。
格思里把这个猜想告诉了正在念大学的弟弟。弟弟认真思考了这个问题结果既不能证明也没有找到反例于是向自己的老师、著名数学家德・摩根请教。德・摩根解释不清当天就写信告诉自己的同行、天才的哈密顿。可是直到哈密顿1865年逝世为止也没有解决这个问题。从此这个问题在一些人中间传来传去当时三等分角和化圆为方问题已在社会上“臭名昭着”而“四色瘟疫”又悄悄地传播开来了。
问题的证明一波三折
四色定理
1878年凯莱正式向伦敦数学会提出了这个问题。凯莱可是英国响当当的数学家他看中的问题必定不同凡响。消息传到了律师肯普的耳朵里引起了他的极大兴趣。不到一年肯普就提交了一篇论文声称证明了四色问题。人们以为事情到此就已经完结了。谁知到1890年希伍德在肯普的文章中找到一处不可饶恕的错误。
不过让数学家感到欣慰的是希伍德没有彻底否定肯普论文的价值运用肯普发明的方法希伍德证明了较弱的五色定理。这等于打了肯普一记闷棍又将其表扬一番总的来说是贬大于褒。真不知可怜的肯普律师是什么心情。 追根究底是数学家的本性。一方面五种颜色已足够另一方面确实有例子表明三种颜色不够。那么四种颜色到底够不够呢？这就像一个淘金者明明知道某处有许多金矿，结果却只挖出一块银子你说他愿意就这样回去吗？
接下去的戏就得由闵可夫斯基来演了。这里得说他几句好话他虽然没有成功可自认第一流倒也并非自不量力。要知道19世纪末20世纪初德国格丁根大学能成为世界数学中心就是由于他和希尔伯特、克莱因“三巨头”的努力。四色瘟疫在英国蔓延时还真没有一个研究过它的数学家比得上闵可夫斯基。
令闵可夫斯基尴尬的一堂课
四色定理
19世纪末德国有位天才的数学教授叫闵可夫斯基他曾是爱因斯坦的老师。爱因斯坦因为经常不去听课便被他骂作“懒虫”。万万没想到就是这个“懒虫”后来创立了著名的狭义相对论和广义相对论。闵可夫斯基受到很大震动他把相对论中的时间和空间统一成“四维时空”这是近代物理发展史上的关键一步。
在闵可夫斯基的一生中把爱因斯坦骂作“懒虫”恐怕还算不上是最尴尬的事…… 一天闵可夫斯基刚走进教室一名学生就递给他一张纸条上面写着“如果把地图上有共同边界的国家涂成不同颜色那么只需要四种颜色就足够了您能解释其中的道理吗”
闵可夫斯基微微一笑对学生们说“这个问题叫四色问题是一个著名的数学难题。其实它之所以一直没有得到解决仅仅是由于没有第一流的数学家来解决它。” 为证明纸条上写的不是一道大餐只是小菜一碟闵可夫斯基决定当堂掌勺问题就会变成定理……
下课铃响了可“菜”还是生的。一连好几天他都挂了黑板。后来有一天闵可夫斯基走进教室时忽然雷声大作他借此自嘲道“哎上帝在责备我狂妄自大呢我解决不了这个问题。”
缓慢的进展
四色定理
当时由大数学家黎曼、康托尔、庞加莱等创立的拓扑学之发展可谓一日千里后来竟盖过大数学家高斯宠爱的数论成为雍容华贵的数学女王。四色问题就是属干拓扑学范畴的一个大问题。拓扑学不仅引进了全新的研究对象也引进了全新的研究方式。对数学来说它不啻是一场革命。 回顾拓扑学的历史就可以说明为什么四色问题对于20世纪数学来说是重要的。通俗地说连续变换就是你可以捏、拉一个东西但不能将其扯破也不能把原先不在一起的两个点粘在一起。比如对于26个大写英文字母一些拓扑学家就认为可将其分成3类
第一类ADOPOR
第二类B
第三类CEFGHlJKLMNSTUVWXYZ。
第一类在连续变换下都可以变成O第三类则都可变成I。
因为4是平面的色数它也是一种示性数可见示性数有很多种体现了平面的拓扑性质与国家的形状无关将平面弯成曲面也没关系。数学家必须确定这个数究竟是5还是4这很重要。如果国家分布在一个环面上画地图最多得要七种颜色。
吊起数学家胃口的还有一个原因。乍一看环面似乎更复杂事实上环面的七色定理却比较容易证明希伍德当时就做到了到1968年其他所有复杂曲面的色数均已确定唯有平面或球面的四色问题依然故我。看来平面没有人们想象的那么简单
1913年伯克霍夫引进了一些新的技巧导致1939年弗兰克林证明22国以下的地图都可以用四色着色。1950年温恩将22国提高为35。1968年奥尔又达到了39国。1975年有报道52国以下的地图用四色足够。可见其进展极其缓慢。
计算机帮助人们圆梦
不过情况也不是过分悲观。数学家希奇早在1936年就认为讨论的情况是有限的不过非常之大大到可能有10000种。对于巨大而有限的数，最好由谁去对付？今天的人都明白：计算机。
从1950年起希奇就与其学生丢莱研究怎样用计算机去验证各种类型的图形。这时计算机才刚刚发明。两人的思想可谓十分超前。
1972年起黑肯与阿佩尔开始对希奇的方法作重要改进。到1976年他们认为问题已经压缩到可以用计算机证明的地步了。于是从1月份起他们就在伊利诺伊大学的IBM360机上分1482种情况检查历时1200个小时，作了100亿个判断最终证明了四色定理。在当地的信封上盖“Four colorssutfice”四色，足够了的邮戳就是他们想到的一种传播这一惊人消息的别致的方法。
人类破天荒运用计算机证明著名数学猜想应该说是十分轰动的。赞赏者有之，怀疑者也不少，因为真正确性一时不能肯定。后来也的确有人指出其错误。1989年，黑肯与阿佩尔发表文章宣称错误已被修改。1998年托马斯简化了黑肯与阿佩尔的计算程序但仍依赖于计算机。无论如何四色问题的计算机解决给数学研究带来了许多重要的新思维。
四色定理_四色定理 -问题影响
一个多世纪以来，数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。
四色定理_四色定理 -实际应用
虽然任何平面地图可以只用四个颜色着色，但是这个定理的应用却相当有限，因为现实中的地图常会出现飞地，即两个不连通的区域属于同一个国家的情况（例如美国的阿拉斯加州），而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种情况下，只用四种颜色将会造成诸多不便。
实际中用四种颜色着色的地图是不多见的，而且这些地图往往最少只需要三种颜色来染色。此外，即便地图能够只用四种颜色染色，为了区分起见，也会采用更多的颜色，以提示不同地区的差别。
四色定理_四色定理 -四色原理的一种逻辑证明
地图上任何一个区域必将存在邻域，且又通过邻域与其他非邻域发生间接联系，我们可以将任何一个地图以图论图形的表示出来。
假设存在一张至少需要m种着色的地图，那么决定该地图必须要用m种着色的条件有且只有一个，即该地图至少存在这样一个区域Q，与该区域相邻的所有区域必须满足m-1着色。首先满足这个条件后，Q只能用第m种颜色，其次如果这个推论一是错误的，对于m着色地图不存在这样的区域，那么地图上任何一个区域的邻域只能满足少于m-1的着色，那么整个地图势必不需要m中颜色，这与假设相矛盾，所以这是一个充分必要条件。（推论一）
假设随意取一张任意结构的至少m着色的地图M，其上满足上述条件的区域有n个，那么将图论图形中的这n个区域及其与邻域的关系线我们可以全部去掉，这样我们就将构建一个至少m着色地图M的问题转化成了一个在至少需要m-1着色地图上添加n个满足推论一条件的区域问题。
如果五着色地图存在且能构建成功，那么必然存在构建这样五着色的四着色模型图，而要存在这样的四着色模型图必然存在构建该四着色的三着色模型图，同理要存在这样的三着色模型图必然要存在构建它的二着色模型图，那么我们来构建一下五色图是否存在：
二着色地图是由一着色而来的一种简单的着色地图模型，我们很容易得到满足二着色的地图仅有的两种类型的结构，一种是不闭合的链状结构，如图一；另一种是由第一种衍生出来的闭合的环状结构且环所联系的区域为偶数个，称为偶数环，如图二。
我们看下二着色结构特点发现，图一图二都是一个原理就是奇偶位置决定着色，任何两个区域的任何联系链条只有相隔偶数个区域才满足两区域着色不同，我们定义这两个区域为偶隔域。
我们随意取一张任意结构的二着色的地图M，来构建一个具有n个满足推论一条件区域的地图Q，构建方式有且只有一个，就是在图论图形中我们如何去掉的这n个区域及其与邻域的关系线，我们接怎么给它添加回去。我们任取这n个区域中一个区域q为例，只要我们在M地图上将必须满足二着色的几个区域W直接联系到q上，这样就满足推论一中的条件而使Q必须为三着色。而W要满足二着色则必定含有偶隔域，如果W有x个区域和q发生直接联系，则q上出去的关系线有x个，那么我们一定可以将该复杂的联系分解成x-1个不可分解关系环，其中至少有一个不可再分的关系环是M中的偶隔域与q联系的，（推论二）假设这个推论是错误的，所有不可再分的环全部是奇隔域，那么这些环拼接回去时满足每个小环的间隔区域数相加再减去共用的区域，仍旧是奇隔域，这样W便不满足二着色，所以这些不可再分环中一定有偶隔域和q发生联系而构成奇数环（环连的区域为奇数），并且导致q必须使用第三色的就是这些不可再分的奇数环。由于满足二着色的只有偶隔域一种条件，那么构造的三着色地图中决定三着色的条件也只有一种，存在不可再分的奇数环。
在上面构建的三色着色地图Q基础上我们再来构建四着色地图P，假如P存在满足推论一条件的区域有k个，同样的方法，我们任取k中一个区域p，只要我们在Q地图上将必须满足三着色的几个区域R直接联系到q上，这样就满足推论一中的条件而使P必须为四着色。而R要满足三着色则必定含有奇数环并且组成奇数环的区域都能够与p发生联系（保证奇数环没有被包围在其他闭合环内的部分），如果R有y个区域和p发生直接联系，则p上出去的关系线有y个，那么导致p为第四色原因是可发生联系的奇数环，既只要有一个这样的奇数环存在就一定会导致p使用第四色（推论三），假设这一推论不成立那么没有这样的奇数环存在，则由前面二着色建立三着色正经得到，除了奇数环再没有能使地图为三着色的条件了，或者当奇数环区域不能全部与p发生联系，这样p必然的不需要第四色了。故我们的推论三成立。由于三着色条件唯一而使得p四着色的条件唯一，我们来看四着色条件的特点，当p与R发生联系后，不管R有多少满足条件的奇数环，势必最终只能有包括p在内的三个区域能与外界区域发生联系。因为p和R上的任何两个区域都可以构成一个封闭的三角形，而当我们选的R上这俩区域与p关系线是最外侧的关系线时，则R上其他区域一定不能在三角形外，不然或造成以上两根关系线不再是最外侧或者有关系线出现交叉，所以R上剩馀区域必定在三角形内而造成四着色图最多只有三个区域能与外界发生联系。
那么我们在构建五着色地图时，四着色结构最多提供三种不同着色，不能满足推论一的条件，而决定将无法构建五着色地图。
四色问题的简单几何图形证明如下（对错不保证，如果方法错误请删除以下内容）
0 这个证明是一个近似的证明。
1 对于二维平面，用无限分割三边形来证明。（必须）
2 为了方便说明，所有三边形为相同大小的等边三角形为例。（并非必须）
3 因为等边三角形最多只有三个边，最多只能与三个相同的等边三角形接壤，算上自己最多就是四种颜色复杂度，也不可能出现第五种！
4 而地图上各个国家的边界就是这些三角形边的近似组成，而领土就是这些三角形的近似拼合。这些三角形同样具备上述颜色属性。
a 类似的证明方法还有采用无限等边多边形分割等腰三角形的圆周率计算。
b 也有采用无限四边形矩阵组合成的计算机屏幕上的像素，这些像素可以组合成任意几何图形。（圆的，方的，三角的，最好是失量图。）
四色定理_四色定理 -另一种证明的思路
两域相邻就能只在这两个域的范围内，画出连接两个域任意各一点的线，且其过这两个域的公共边。（公理1）
m着色成立的充要条件是存在其中m个域两两相邻。（证其逆否命题可得，定理1）
一条公共边只能同时属于两个域。（公理2）
公理1+公理2：如果两条所述线相交（每两个域只画一条），则一定有其中至少一条经过了至少三个域。（推论1）
公理1+定理1+推论1：m着色成立的充要条件是存在m个域，各域中任意一点可两两相连不交叉。（推论2）
p能推出q，q也能推出p，则称p，q互为充要条件。（定义1）
推论2+定义1：在平面内能找出m个点两两相连不相交，则m色原理成立。（推论3）
之后就发现四色原理其实和拓扑中多点两两连线不相交问题本质上是一致的。
结论就可以照搬了，平面或单曲面上是四色原理，莫比乌斯环上是七色原理……
