画一张台湾地图需要几个颜色:四色定理
热身运动
玩法1:两人一组,轮流将给定的地图著色.每次只能涂一块区域,相邻两区不能用同一种颜色;最后能以至多n种颜色将地图上完色就算成功.
玩法2:两人一组,至多能用n种颜色轮流将给定的地图著色.每次只能涂一块区域,相邻两区不能用同一种颜色;最后能让对方没有颜色可用的人赢.
以n = 2试试下面这几个图:
1.
2.
3.
4.
5.
以n = 3试试下面这几个图:
1.
2.
3.
4.
以n = 4试试下面这几个图:
1.
2.
3.
地图著色问题
为了让人能一目了然,在彩色地图上,我们总是习惯地把相邻的两区(两国,两省或两县等)涂以不同的颜色.地图上有多少区域就涂多少种颜色当然是一种涂法.但是根据经验,我们知道只要"少少"几种颜色就够了,最少要几种呢
注意,这里所指的区域都是连通的.例如台湾岛与澎湖群岛被海水隔开,就不是连通的;而像梵蒂冈从义大利的内陆挖去了一块则无所谓,因为义大利还是连通的.因外,如果两个区域只以数个点相接则不算是相邻.如下图,A与B,D相邻,但是与C不相邻.
下面是一张台湾地图,你觉得最少需要用多少颜色来著色,才能让相邻的两县涂上不同的颜色呢
两色地图
让我们先看几个比较简单的图形.你需要多少种颜色才能将下面这个图形完成著色
显然是两个颜色就够了.涂法是在相邻(共用同一边线)的两个小方格中涂上不同颜色.如下:
大家应该都看过西洋棋的棋盘,是不是和上图很类似呢

让我们再试试下面这张图:
看起来有点复杂,但是别被它的外表吓到了,它也只需要两个颜色就能涂满.
当然不是所有的图都可以这样做,那麼是否有什麼简单的方法可以帮助我们判断一张图是不是这种所谓的两色地图呢
若将上图看成是一个海中的小岛,各个区域是不同的国家,我们注意到它们的国界总会在某些点上交会,而那些不在海岸线上的交点就称为「内点」.对於相交在同一内点的几个国家而言,它们必定是要交替涂上不同的颜色,如下图:

观察上图,我们不难发现图中每一个内点的秩都是偶数.让我们再看看,若一个图图中存在某个内点的秩是奇数又如何呢
以下图为例:
我们若以两种颜色从第一个区域开始,依逆时钟方向交替涂完区域2,3,4之后,区域5就无再法用原本的两个颜色来涂,也就是说区域5势必要用到第三个颜色.
一般而言,一个图若图中存在某个内点的秩是奇数,n,又如何呢
我们将环绕该点的区域,依逆时钟方向填入数字1,2,…,n.如上例,我们若以青,黄两种颜色从区域1开始,依逆时钟方向交替将各个区域涂色,则除了最后一个区域(也就是区域n)之外,所有奇数区域都将涂上青色,而有偶数区域都将涂上黄色,如下图:
而区域n因为与区域1及区域n-1(偶数)相邻,因此不能用原本的两个颜色来涂,也就是说区域n势必要用到第三个颜色.
这意味著若某一内点四周有奇数个国家,则无法以两色来著色.
我们因此得到下面的结论:「如果一个海岛上的国家能以两种颜色来著色,则每个内点的秩一定是偶数.」

下一页