下图中包含了五个区域，为了使相邻的区域颜色不同，我们要对下图区域进行填色.
这就是我们需要填充的颜色的数量吗?
这是制图师在绘制许多有共同边界的省地图或国家地图时所面临的问题. 我们想要找到区分相邻区域所需颜色的最小数量.
想要找到给上图上色的方法，请继续阅读. 或者，直接跳到今日挑战，尝试独立解决上色问题吧!
数学家们花了100多年的时间来证明以下定理:
给定一个被划分为不同区域的图形，我们可以使用四种或更少的颜色来填充这些区域，使得两个相邻的区域(共享边界的区域)都是不同的颜色。 所以，对于有5个区域的图形，5种颜色显然是不必要的.
上面的定理非常实用，但是我们如何使用少于五种颜色给图形上色呢?
有一种策略被称为“贪婪算法”. 我们遵循以下步骤:
- 用从1到
(假设图中区域的总数为 )的数字对图中的每个区域进行标识. - 制作一个有序的颜色列表. (因为我们知道最多需要四种颜色，所以我们将按此顺序使用红、黄、绿和蓝. )
- 用列表上的第一种颜色给第一个区域上色.
- 从区域
到区域 ，用序数最小且在相邻区域中还没有使用过的颜色给它上色. - 重复步骤4，直到每个区域都上过色.
下面，根据左边的区域编号生成右边的颜色:
看起来可以用3种颜色给这个图上色.
但我们必须小心! 贪婪算法不一定是使用颜色数量最少的上色方法. 例如，用以下区域编号则对应了4种颜色:
那么怎么能确定这个图不能只用两种颜色上色呢? 请看区域1、2和3，它们在两种编号方式下对应的区域是相同的. 它们中的每一个区域都与其他两个区域相邻. 所以用两种颜色是不可能的，因为如果我们用第一种颜色给区域1上色，用第二种颜色给区域2上色，那么区域3就无法上色.
如果你用贪心算法来解决今日挑战，请确保使用颜色的数量确实是最少的!