Files
2025-12-02 01:47:15 +08:00

78 lines
4.2 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
# 基于独立集的区域涂色方式计数方法
## 引言
对于排列组合中的区域上色问题,在中学阶段少有系统、规范的讨论方法。日常教学时老师会提到“将相同颜色的色块进行分组”,但实际操作过程中也常有遗漏,算了数分钟却发现ABCD都无法匹配的现象可谓屡见不鲜。本文将基于图论中的独立集,提出一种具有普遍性的统计方式,并探讨可能的优化方向。
### 例题
提供四种不同颜色的颜料给图中六个区域涂色,要求每个区域涂一种颜色,有公共边的两个区域不能涂相同的颜色,则不同的涂色方法共有()种。
<img src="./svgs/C0.svg" alt="题目" width="100">
#### 常规思路
首先, $D,E,F$显然无法同色,对这三个区域有 $A_4^3$ 种涂法。
当 $B,D$ 同色时,区域被分成 $\{A\},\{B,D\},\{C\},\{E\},\{F\}$四块,有 $A_4^3 \times 2 \times 3 = 144$ 种方案。
$B,F$ 同色与 $B,D$ 同色相对称,也有 $144$ 种方案。
最后, $B,D,F$ 之间均不同色时,有 $A _4 ^3 \times 2 \times 2 = 96$ 种方案。
故总方案数为 $144 + 144 + 96 = 384$ 种。
#### 基于独立集的思路
##### 理论
可将A~F抽象为图中的节点,用边连接具有公共边的色块对应的节点,形成图$C_1$:
<img src="./svgs/C1.svg" alt="C1" width="100">
将每个节点和与之相连的节点分离,和与之不相连的节点相连(即构建 $C_1$ 的独立集),形成图$C_2$:
<img src="./svgs/C2.svg" alt="C2" width="100">
此时,$C_2$ 中的边所连接的节点对应的,就是“一对不具有公共边的色块”,也就是一对可以被涂上同种颜色的色块。\
那么,对于 $C_2$ 中的任意子图,如果其任意两个顶点间都有相邻的边,该子图对应的所有色块都可以被同种颜色涂色。\
这样的子图在图论中被称为“团”。\
方便起见,本文将用团的点集表示团,如 $\{A,C,E\}$ 表示由 $A,C,E$ 三个节点组成的团
再将$m$种颜色分配给$i$个团,方案数为 $A_m^i$ 。
若将 $C_2$ 拆分为$i$个团的方案数为 $n_i$ ,提供的最大颜色数为 $m$,总染色方案数为 $N$ ,有:
$$N = \sum_{i = 1}^{m}({n_i} \times {A_m^i})$$
##### 实现
由于对任意节点,其参与形成的不同的团不会处于同一分割方式中,可递归地对图进行分割。
如,$A$ 节点可形成 $\{A\},\{A,C\},\{A,E\},\{A,F\},\{A,C,E\}$几个团。\
以分割 $\{A\}$ 为例。此时,除$\{A\}$以外的部分形成了一张新的子图 $C_3$:
<img src="./svgs/C3.svg" alt = "C3_2" width=100>
选择 $C_3$ 中的节点分类讨论,最终递归地统计每种分割方案产生的团的数量,即可得到表达式中的 $n_i$。
但在实际计算过程中,这种繁琐的递归不仅效率及其低下,也很容易出错。因此,对其进行优化是有必要的。
##### 一种优化思路
分割时常常会遇到一类链状的图,如例题中的$C_3$。在图论中,这类图被称为路径图,含 $n$ 个节点的路径图就用 $P_n$ 表示。\
这类路径图的节点排列方式各有不同,但具有相同的结构,也就有相同的分割方式与涂色方案。
定义 $f(i,k)$ 为“将路径图 $P_k$ 分割为$i$个团的方案数"。考虑到路径图的团至多有2个节点,至少有1个节点, $f(i,k) \neq 0$ 时有 $i \in [ {\lceil \frac{k}{2} \rceil},k ]$ 。\
显然有 $f(k,k) = 1$ 。\
若将任意两相邻节点合并为新的团,则有 $C_{k-1}^1 = k-1$ 种方案,即 $f(k-1,k) = k-1$ 。\
$i < 3$ 且 $n < 4$时,路径图较为简单, $f(i,k)$ 的值小,可直接数出。见下表:
| $n$ | $f(i,n)$ |
|-|-|
|1|$f(1,1) = 1$|
|2|$f(1,2) = 1,f(2,2) = 1$|
|3|$f(1,3) = 1,f(2,3) = 2$|
对于 $ i \geq 3 $ 或 $ n \geq 4$ 的路径图,可以在端点处递归分割,即 $f(i,k) = f(i-1,k-1) + f(i-1,k-2)$ 。
回到例题,显然 $C_3$ 属于路径图 $P_5$ 。对于 $C_3$ ,$i \in [2,3]$ , $f(2,5) = 0$ , $f(3,5) = f(2,4) + f(2,3) = 1 + 2 = 3$ 。即将 $C_2$分割为3个团的方案有0个,分割为4个团的方案有3个。
用相同方法处理剩下四种情况,即可得:
$$N = A_4^3 \times (0+0+1+1+2) + A_4^4 \times (3+2+3+3+1) = 384$$