词汇表

选择左侧的一个关键字...

地图着色

阅读时间: ~10 min
此页面已自动翻译,可能包含错误。如果您想帮助我们审核翻译,请与我们取得联系!

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

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

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

在为美国各州的地图着色时,显然50种颜色就足够了,但所需的颜色就少得多了。尝试使用尽可能少的颜色为下面的地图着色:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

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

像以前一样,我们可以将带有国家和边界的地图转换为平面图:每个国家都变成国家的边缘连接:

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

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

在随后的100年中,许多数学家发布了四色定理的“证明”,只是为了以后发现错误。其中一些无效的证据令人信服,以至于花了10年多的时间才发现错误。

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

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

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

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

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

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

This map on a torus requires seven colours.