Untitled Course地图着色

我们已经在某些地图上使用了图论。当我们缩小地图时，个别的道路和桥梁消失了，于是看到了整个国家的轮廓。

为地图或其他由不同区域组成的图形着色时，相邻国家/地区不能使用相同的颜色。我们可能还想使用尽可能少的不同颜色。

一些简单的“地图”（例如棋盘）仅需要两种颜色（黑白），但是大多数复杂的地图需要更多颜色。

在为美国各州的地图着色时，显然50种颜色就足够了，但我们要用更少的颜色。尝试使用尽可能少的颜色为下面的地图着色：

0 使用的颜色数

0 使用的颜色数

0 使用的颜色数

0 使用的颜色数

所有这些地图可以只用四种不同的颜色完成着色，但是不难想象其他非常复杂的地图可能需要更多的颜色。实际上，每张地图包含四个相互连接的国家时，至少需要四种颜色。

像以前一样，我们可以将带有国家和边界的地图转换为平面图：每个国家都变成，同时具有的国家通过一条边连接：

现在，我们要为图的顶点着色，并且两个顶点通过边连接时必须具有不同的颜色。

1852年，植物学专业的弗朗西斯·古思里（Francis Guthrie）必须为英格兰的郡地图上色。他观察到四种颜色似乎足以满足他尝试的任何地图，但他无法找到适用于_所有_地图的证明。原来这是一个极其困难的问题，并被称为 四色定理 。

在随后的100年中，许多数学家发布了四色定理的“证明”，然而那些证明只不过是为之后发现其中的错误提供了机会。其中一些无效求证看起来如此的令人折服，以至于数学家们花了10年多的时间才发现错误。

长期以来，数学家无法证明仅需四种颜色就够了，也找不到需要四种以上颜色的地图。

在四色问题上进展甚微，直到1976年沃尔夫冈·哈肯（ Wolfgang Haken）和肯尼斯·阿佩尔（ Kenneth Appel）使用计算机最终解决该问题时。他们将无数种可能的地图缩减为1936种特殊情况，每种情况都由一台计算机进行了总计超过1000个小时的检查。

四色定理 是第一个使用计算机证明的著名数学定理，此后利用计算机证明定理变得越来越普遍，争议也越来越小。更快的计算机和更高效的算法意味着今天您可以在几个小时内在笔记本电脑上证明四种颜色定理。

伊利诺伊大学香槟分校数学系的邮戳哈肯和阿佩尔曾在那里工作。

四色定理仅适用于平面或球体上的地图，并且所有国家/地区都由一个区域组成。

但是，数学家们还查看了 帝国(国家可以由多个相互独立的组成部分组成) 地图，以及不同形状的行星，如圆环(甜甜圈形状）上的地图。在这些情况下，您可能需要四种以上的颜色，并且证明变得更加困难。

这张在圆环上的地图需要七种颜色。

更改语言