地图上的四色定理

在维基百科看到一个四色定理，就想到软件中的四色原型。软件中的四色原型是类与类之间的四种关系：“关联、依赖、继承、实现”，类的这四色是任何复杂软件系统的基础，于是有了ManyToOne,ManyToMany,Extends,Implements这些关键字.

维基百科的四色定理如下：

四色定理 指出每个可以画出来的无飞地地图都可以至多用4种颜色来上色，而且没有两个相接的区域会是相同的颜色。被称为相接 的两个区域是指他们共有一段边界，而不是一个点。

这一定理最初是由Francis Guthrie在1853年提出的猜想。很明显，3种颜色不会满足条件，而且也不难证明5种颜色满足条件且绰绰有余（仅使用到欧拉-笛卡尔公式）。但是，直到1977年四色猜想才最终由Kenneth Appel 和Wolfgang Haken证明。他们得到了J. Koch在算法工作上的支持。

证明方法将地图上的无限种可能情况减少为1,936种状态（稍后减少为1,476种），这些状态由计算机一个挨一个的进行检查。这一工作由不同的程序和计算机独立的进行了复检。在1996年，Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas使用了一种类似的证明方法，检查了633种特殊的情况。这一新证明也使用了计算机，如果由人工来检查的话是不切实际的。

四色定理是第一个主要由计算机证明的理论，这一证明并不被所有的数学家接受，因为它不能由人工直接验证。最终，人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任。参见实验数学。

缺乏数学应有的规范成为了另一个方面；以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿！”

虽然四色定理证明了任何地图可以只用四个颜色着色，但是这个结论对于现实上的应用却相当有限。现实中的地图常会出现飞地，即两个不连通的区域属于同一个国家的情况（例如美国的阿拉斯加州），而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种情况下，四个颜色将会是不够用的。

（来自http://zh.wikipedia.org/w/index.php?title=%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86&variant=zh-cn ）

 

 

 

我把它抽象成一个3×3无限模型，下面一种是只需要四种颜色就可以完整的填充的：

 

ColorB	ColorD	ColorC
ColorC	ColorA	ColorB
ColorB	ColorD	ColorC

注意第一行和第三行是重复的，如果说9个方格完全不一样需要9种颜色（3×3=9），那么第一行和第三行一样就省了三种，9-3=6，假设最多是6种颜色，然后可以注意到第一行第三列和第二行第一列是不相邻的，同样第一行第一列和第二行第三列也不是相邻的

，又可以省去两种颜色，6-2=4种颜色

我是直觉证明，呵呵

==============

在程序语言中，我们尽量节省地址空间，可以用char的地方不要轻易用varchar，可以用short的地方不要轻易用Integer或Long

==============

在www.jdon.com里有篇文章，讲的是类的四色，就是类与类之间的四种关系，继承、实现、组合、关联