邻接涂色与同色分支

约 3547 字大约 12 分钟

涂色计数先看哪些位置必须异色，不看图形面积。决定下一步有几种颜色的，是已涂邻点实际用了几种不同颜色；这个数随前面选择改变时，就要先分类再分步。

一、知识点概念与依据

1. 把异色约束列成邻接关系

区域题中“相邻”通常指有公共边，仅在一点接触不算；顶点题则按题干指定的棱或连线约束两端异色。可把每个待涂位置记为一个点，把每对必须异色的位置连一条边。这个记录只表达限制，不由面积或形状决定方案数。

图上有线不自动意味着两端异色，例如无人机队形要按具体题意判断。反过来，环的闭合边和三棱柱的侧棱不能漏记。

2. 禁掉的是颜色种数，不是邻点个数

有 $q$ 种可区分颜色。涂一个位置时，已经涂色的邻点实际用了 $s$ 种不同颜色，便有 $q-s$ 种可用颜色。多个邻点同色，只禁掉一种；后续还须检验它与后来位置之间的约束。

只有每种合法既有历史都给相同的 $s$ ，这一步才能统一乘 $q-s$ 。若两个前邻点同色与异色会改变后续选择数，先分这两个互斥且完整的分支，各支内部再相乘，最后相加。不相邻只表示允许同色，并非必须同色，也并非必须异色。

3. 开链与闭环的差别

$n$ 个固定位置只按前后相邻连成链。 $q\ge2,n\ge1$ 时，首位 $q$ 种，其后只排除前位一色，共

q(q-1)^{n-1}.

单独一个位置、 $q\ge1$ 时就是 $q$ 种； $q=1,n\ge2$ 时没有合法涂法，不借 $0^0$ 争论边界。环额外要求首尾异色，最后一步可能禁掉一种或两种颜色，不能机械套链式乘积。

“田”字四格若编号为左上 $A$ 、右上 $B$ 、左下 $C$ 、右下 $D$ ，边为 $AB,AC,BD,CD$ 。 $q\ge2$ 时先涂 $A,B$ ，再分 $C=B$ 与 $C\ne B$ ，共有

q(q-1)\big[(q-1)+(q-2)^2\big].

第一支 $C$ 只选 $B$ 色， $D$ 有 $q-1$ 种；第二支 $C$ 避开 $A,B$ ， $D$ 避开 $B,C$ ，各有 $q-2$ 种。反向读取最终四格颜色，分支唯一，故不重不漏。 $q=2$ 时第二支为零，仍有两种； $q=1$ 应直接判无解，不能把“负一种颜色”当选择数。

4. 颜色有名，位置固定，是否用满另读题

通常固定区域或顶点可区分，颜色名称也可区分。改变某个位置的颜色就是另一结果；“有若干种颜色可供选择”不等于“每种都必须用到”。若要求恰好用某几色，须额外检查使用数，各类必须互斥完整。

旋转、镜像或交换颜色名后是否算同一种，必须由题目约定。没有约定不能除旋转数或颜色数的阶乘；有约定也不能盲除。只有这些组互不重叠、覆盖全部合法涂色，且每组恰含同样的 $d$ 个不同记录时，才可用固定位置总数除以 $d$ ；旋转操作数不一定就是这个 $d$ 。

二、考点方法与例题

1. 先核边，再按开放或闭合结构推进

列全公共边，沿约束简单的位置推进。链首位之后各只避一色；环最后两邻点的同异色会改变禁色数，须提前分类。每步都要能从最终涂色唯一反读，才是无重复的构造。

例题 01 五个区域是否形成闭环

题目

已知五个区域A，B，C，D，E依次相邻，如图所示，现在给这5个区域涂色，要求相邻的两个区域不能涂相同的颜色，现有5种不同的颜色可供选择，则不同的涂色方法有（）

A．1140 B．1200 C．1280 D．1400

答案与解析

解析

图的公共边关系仅为 $A-B-C-D-E$ ， $B,D$ 之间有间隙，也没有额外的首尾公共边。

按 $A,B,C,D,E$ 顺序，首区有 $5$ 种颜色，之后各只需避开前区一色，故为 $5\times4^4=1280$ 。较远区域可以同色，不要求五色全用，也不除旋转数或交换颜色名称的倍数。其余选项不等于这个逐步构造的总数。

本题结论

选 C，共 $1280$ 种。

例题 02 田字格的涂色

题目

用红、黄、蓝、白、黑五种颜色在“田”字型的4个小方格内涂色，每格涂一种颜色，相邻两格涂不同的颜色，则不同的涂色方法共有（）

A．120 B．260 C．280 D．320

答案与解析

解析

$A$ 有 $5$ 种， $B$ 有 $4$ 种。 $C$ 不能同于 $A$ ，但可同于 $B$ 。

若 $C=B$ ， $C$ 只有一种， $D$ 只避这一个颜色，有 $4$ 种。
若 $C\ne B$ ， $C$ 要避 $A,B$ 两色，有 $3$ 种； $D$ 避 $B,C$ 两色，也有 $3$ 种。

故总数为 $5\times4(1\times4+3\times3)=260$ 。 $AD,BC$ 只点接触，不添加异色条件。不能把它当开放链乘 $4$ ，也不能按四格全异色算 $5\times4\times3\times2$ 。

本题结论

选 B，共 $260$ 种。

2. 找出决定后续禁色数的同色关系

先涂约束多而容易确定的位置，把后续邻点的实际颜色集合写清。按关键两位置同色或异色分支；相同分支常只有一种确定颜色，异色分支还须排除其余已禁色，不是只排除比较的那一个位置。

题干中的人物年代与历史背景仅转述原资料，未作独立认证。

例题 03 中心区域和外侧四环

题目

如图为我国数学家赵爽（约3世纪初）在为《周髀算经》作注时验证勾股定理的示意图，现在提供5种颜色给其中5个小区域涂色，规定每个区域只涂一种颜色，相邻区域颜色不相同，则不同的涂色方案种数为（）

A．120 B．26

C．340 D．420

答案与解析

解析

按标注，中心 $C$ 邻接四个外区，外圈为 $A-B-E-D-A$ 。依次涂 $A,B,C$ ，分别有 $5,4,3$ 种。

$D$ 邻接 $A,C$ ，不能用这两色； $B$ 色仍可用。

若 $D=B$ ，只有一种， $E$ 只避 $B(=D),C$ ，有 $3$ 种。
若 $D\ne B$ ， $D$ 避 $A,B,C$ ，有 $2$ 种； $E$ 避 $B,C,D$ ，也有 $2$ 种。

所以 $5\times4\times3(1\times3+2\times2)=420$ 。 $B,D$ 没有公共边，若强迫异色，就漏掉第一分支。

本题结论

选 D，共 $420$ 种。

3. 同一几何图的不同小问，要重建约束

底面内部异色与所有棱两端异色不是同一问题。先固定一个底面的三种颜色，再按另一个底面是否使用剩余色分类；也可按一条四顶点链用几种颜色分类，但必须穷尽所有合法同色关系。

例题 04 底面约束与全部棱约束

题目

如图，用四种不同的颜色给三棱柱 $ABC-{A}^{\prime}{B}^{\prime}{C}^{\prime}$ 的六个顶点涂色，要求每个点涂一种颜色．

原图右侧顶点标签不完整，此处按原邻接关系重绘，六个顶点及九条棱不变。

(1)若每个底面的顶点涂色所使用的颜色不相同，则不同的涂色方法共有多少种？

(2)若每条棱的两个端点涂不同的颜色，则不同的涂色方法共有多少种？

答案与解析

解析

(1) 每个底面三点各异色，有 $4\times3\times2=24$ 种。题目未要求对应侧棱两端异色，两个底面可分别选择，共 $24^2=576$ 种。

(2) 固定一底面后分类。先涂 $A,B,C$ ，有 $24$ 种，把三色记为 $1,2,3$ ，剩余为 $4$ 。另一个底面三点两两异色，还要 $A'\ne1,B'\ne2,C'\ne3$ 。

不用 $4$ ，只有 $(A',B',C')=(2,3,1),(3,1,2)$ ，共 $2$ 种。
用 $4$ ，它恰出现一次，位置有 $3$ 种。若在 $A'$ ， $(B',C')$ 只能为 $(1,2),(3,1),(3,2)$ ，共 $3$ 种。 $4$ 在其他位置时，重命名相应三色，仍各有 $3$ 种。

故第二底面有 $2+3\times3=11$ 种，总数 $24\times11=264$ 。

另一方法：保留按四顶点用色数分类。按 $B',A',A,C$ 这条链考虑，四者相邻链端要求异色，故至少两色，最多四色。

四色：四者各异色，有 $4\times3\times2\times1=24$ 种。 $C'$ 只能同 $A$ 色， $B$ 只能同 $A'$ 色，贡献 $24$ 。
三色：只有一对非邻位置同色，共三支。 $B'=A$ 时， $C'$ 只能用剩余色， $B$ 有两种，贡献 $24\times1\times2=48$ ； $A'=C$ 时， $B$ 只能用剩余色， $C'$ 有两种，贡献 $48$ ； $B'=C$ 时， $B,C'$ 各有两种，贡献 $24\times2\times2=96$ 。
两色：只能 $B'=A,A'=C$ ，两有名色选择为 $4\times3=12$ 种；剩下 $B,C'$ 各可用另两色，共 $12\times2\times2=48$ 。

五支总和 $24+48+48+96+48=264$ 。资料原解最后一支将尚待涂的 $C'$ 写成 $C$ ，而 $C$ 已确定，应为 $C'$ ；这里只依据题面及九条棱独立复核，不据该误植增改条件。

本题结论

(1) $576$ 种；(2) $264$ 种。

答案与解析

解析

固定位置只有红蓝红蓝、蓝红蓝红两种。转 $90$ 度使二者互换，转 $180$ 度又回原记录。因此旋转等价后两种记录合为一组，只有一种。

直接除以四得 $1/2$ 没有意义，因为每组只含两种不同记录，而不是四种。“四次旋转操作”与“四个不同结果”不能混淆。

本题结论

固定位置 $2$ 种；旋转等价 $1$ 种；不能直接除四。