地图染色与涂色计数：相邻不同色的分步决策树

什么是几何涂色问题？

在小学四至六年级的排列组合模块中，有一类既像游戏又充满数学奥妙的题型——染色问题：

题目：现有红、黄、蓝、绿 4 种不同的颜色，要给地图上的 4 个区域 $A, B, C, O$ 涂色，要求有公共边界的相邻区域不能涂同一种颜色。
问：一共有多少种不同的涂色方案？

很多孩子做这道题时习惯“顺手抓阄”：

• 从 $A$ 开始涂，写一个 4；
• 再看 $B$，写一个 3；
• 看到 $C$，不知道该受谁的限制；
• 看到中间的 $O$，发现同时碰到了 $A, B, C$，此时脑子已经成了一团浆糊！

第一铁律：谁接触最多，谁最先涂（贪心约束原理）

在图论和组合数学中，决定一道染色题难易度的关键是“区域接触度”（即每个区域有多少个相邻的邻居）。

在上面的图形中：

• 区域 $O$ 处于中心枢纽位置，同时与 $A, B, C$ 三个区域相邻；
• 区域 $A, B, C$ 各自只与 $O$ 以及边上的 1 个区域相邻。

如果我们先涂周围的区域，中心 $O$ 会同时受到多重限制，极容易陷入死胡同。
反之，如果我们先把最难缠的“枢纽中心 $O$”搞定，剩下的外围区域就变成了各自独立的简单链条！

分步决策树推导（乘法原理）

让我们以中心区域 $O$ 为起点，依次分步染色：

1. 第一步：涂中心区域 $O$
   • 没有任何限制，4 种颜色皆可自由选择；
   • 方案数：4 种。
2. 第二步：涂外围第一个区域 $A$
   • 区域 $A$ 与 $O$ 相邻，不能与 $O$ 同色；
   • 方案数：$4 - 1 = \mathbf{3 \text{ 种}}$。
3. 第三步：涂外围第二个区域 $B$
   • 区域 $B$ 同时与 $O$ 和 $A$ 相邻，既不能与 $O$ 同色，也不能与 $A$ 同色；
   • 方案数：$4 - 2 = \mathbf{2 \text{ 种}}$。
4. 第四步：涂外围第三个区域 $C$
   • 区域 $C$ 同时与 $O$ 和 $B$ 相邻（不与 $A$ 相邻），不能与 $O$ 同色，也不能与 $B$ 同色；
   • 方案数：$4 - 2 = \mathbf{2 \text{ 种}}$。

根据乘法原理，分步完成一件事情，总方案数为各步相乘：

高阶大坑：环状闭合“分类讨论”（同色 vs 异色）

如果外围区域首尾相接形成一个封闭环形（即 $C$ 也与 $A$ 相邻）：

• 此时涂到 $C$ 时，它同时与 $O, B, A$ 三个区域相邻；
• 但是！$A$ 和 $B$ 已经涂了不同颜色，那么 $A$ 和 $C$ 能不能同色呢？
• 此时单靠分步乘法就会失效，必须引入分类讨论：

1. 第一类：$A$ 与 $C$ 涂相同颜色
   • 此时 $A$ 和 $C$ 占用同一种颜色，中心 $O$ 占一种，一共消耗 2 种颜色；
   • 剩下区域 $B$ 只要避开这 2 种颜色即可。
2. 第二类：$A$ 与 $C$ 涂不同颜色
   • 此时 $A, C, O$ 三个区域颜色两两不同，占用 3 种颜色；
   • 区域 $B$ 必须同时避开这 3 种颜色。

最后使用加法原理将两类方案数汇总相加！
牢记八字诀：“直线分步乘，环形同异分”，小升初排列组合压轴大题手到擒来！