Files
2026-10-10 12:17:32 +08:00

4.8 KiB
Raw Permalink Blame History

+++ date = '2026-02-17T18:42:40+08:00' draft = false title = 'Maps' summary = '基于独立集的区域涂色方式计数方法' +++

基于独立集的区域涂色方式计数方法

提供四种不同颜色的颜料给图中六个区域涂色,要求每个区域涂一种颜色,有公共边的两个区域不能涂相同的颜色,则不同的涂色方法共有()种。

{{

}}

常规思路

首先, $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:

graph TD
    classDef nodeStyle fill:#d3d3d3, stroke:#333, stroke-width:2px;
    linkStyle default stroke:#808080, stroke-width:5.5;

    A((A)):::nodeStyle
    B((B)):::nodeStyle
    C((C)):::nodeStyle
    D((D)):::nodeStyle
    E((E)):::nodeStyle
    F((F)):::nodeStyle

    A --- B
    A --- D;
    B --- C
    B --- E;
    C --- F;
    D --- E
    D --- F;
    E --- F;

将每个节点和与之相连的节点分离,和与之不相连的节点相连(即构建 C_1 的独立集),形成图$C_2$:

graph TD
    classDef nodeStyle fill:#d3d3d3, stroke:#333, stroke-width:2px;
    linkStyle default stroke:#808080, stroke-width:5.5;

    A((A)):::nodeStyle
    B((B)):::nodeStyle
    C((C)):::nodeStyle
    D((D)):::nodeStyle
    E((E)):::nodeStyle
    F((F)):::nodeStyle

    A --- C
    A --- E
    A --- F;
    B --- D
    B --- F;
    C --- D
    C --- E;

此时,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$:


graph TD
    classDef nodeStyle fill:#d3d3d3, stroke:#333, stroke-width:2px;
    linkStyle default stroke:#808080, stroke-width:5.5;

    B((B)):::nodeStyle
    C((C)):::nodeStyle
    D((D)):::nodeStyle
    E((E)):::nodeStyle
    F((F)):::nodeStyle

    B --- D
    B --- F;
    C --- D
    C --- E;

选择 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