|
引言 下图是一张世界地图，从这张地图看很清楚的看到每个国家的位置，英国数学家法兰西斯·古德里在1852年提出：“是否只用四种颜色就能为所有地图染色?”由此出现了四色定理。  1.四色定理 下图是一张抽象画的地图，四色定理可以表述为：一张地图最多只要用四种颜色就快用完全表示出来。四色定理最核心的一点是：彼此相邻的两个区域颜色不能相同。  然而，人们发现，要证明宽松一点的“五色定理”（即“只用五种颜色就能为所有地图染色”）很容易，但四色问题却出人意料地异常困难。曾经有许多人发表四色问题的证明或反例，但都被证实是错误的。 2.普通数学表述 虽然靠着“经验”感觉一张地图最多用四种颜色即可解决，但是作为数学还是需要严谨的描述。其定义可以描述为：
3.图论阐述 图论可以把上面问题更进一步抽象画，即将一个地图转化为图论中的一个无向平面图。具体来说，是将地图中的每一个国家用其内部的一个点代表，作为一个顶点。如果两个国家相邻，就在两个顶点之间连一条线。这样得到的图必然是一个平面图（不会有两条边相交），而与每个国家选取的代表点无关。四色定理可以叙述为：必然可以用四种颜色给平面图的顶点染色，使得相连的顶点颜色不同  一个四个国家的地图转化为一个平面图 要注意的是，并非所有的地图都可以转化为图论中的平面图。如果一个国家有飞地的话，就不能用只一个点来代表一个国家。另外，如果一个国家是“国中国”，那么即便可以地图其转化为平面图，也会造成讨论上的不便。但是，“国中国”的着色十分容易解决，因为它只有一个邻国，只需将它染成和邻国不一样的颜色就可以。所以在大部分有关四色问题的讨论中可以忽略“国中国”的情形。 同样地，只有两个邻国的情形也可以被忽略。如果规定不能够有四个或者以上的国家有公共边界，那么地图转化成的平面图里面，每个区域都是至多由三条边围成的。这样的地图被称为正规地图。如果任何一个顶点都连出三条边，那么就称其为“三度图”（trivalent map）。可以证明，如果存在四色定理的反例，那么国家数最少的反例必定是三度图。因此在四色问题的证明过程中，常常会假设地图对应的图是三度图 4.数学证明 目前主要有放电法（放电法利用地图转换成图染色后成为平面图的特性，将其看作是平面的“电网”，并将每个“节点”按照度数（连出的边数）分类。）和染色算法 地图染色算法是一个应用的问题：能否给出一个算法，将一个地图进行k-染色，或判定它不能k-染色？当k = 2时，存在多项式时间的算法。只需将某个国家随机染上一种颜色，然后它的邻国就只能染成另一种颜色，邻国的邻国的颜色也随之确定……这个算法等价于广度优先搜索，因此是多项式时间的。 学术界通常认为，四色问题，目前还没有好的证明方法。 |
|
|
