P4429 [BJOI2018] 染色

Alex_Wei · 2022-07-06 20:14:17 · 题解

Upd on 2022.7.7：修正代码，修改笔误。

*P4429 [BJOI2018] 染色

我花了一个下午和一个晚上研究这道结论题及其证明。现有题解的证明与推导过程太简略，并不严谨，且没能很好地体现本题的思维难度，希望我的题解能帮到大家。

如有笔误或难以理解的部分还请指出。

基本判断

显然，当 G 不是二分图时无解，图上所有环均为偶环。

设 G 连通，若 G 不连通，其每个连通块独立，可分别求解。

度数为 1 的点不产生贡献，因其可根据唯一邻点的颜色确定自身颜色，不可能无解，故不断剥去度数为 1 的点，直到图上所有点度数 \geq 2。

固定

由样例可知若 G 包含 K_{3, 3} 则无解，但这个条件太强了，不必要。

尝试手玩 K_{2, 2}，即长度为 4 的环 (1, 2, 3, 4)，目标是确定一些颜色，降低不确定性。

不失一般性，节点 1 的颜色集合 S_1 = \{A, B\}。注意到 3 与 2, 4 相连，若给 1 涂上颜色 A 后，2, 4 被迫选择 B, C，令 S_3 = \{B, C\} 即可导出矛盾。根据推理，当 S_1 = \{A, B\}，S_2 = \{A, B\}，S_3 = \{B, C\}，S_4 = \{A, C\} 时，可固定 c_1 = B。

尝试抽象出固定的本质。设节点 i 及 S_i = \{A, B\}，「固定」需要两个「自由点」j, k，使得 i 取某个颜色时，j 不得不取某个 与 i 不同 的颜色，而 k 的颜色集与 i, j 颜色重合，得到矛盾。

简单环

接下来讨论的环为不经过重复节点的 简单环。

一个环固定环上任意点颜色，只需再用一个环导出矛盾即可。因形如 “只能选两种颜色之一” 的限制可通过度数为 2 的节点传播，故若 G 存在两个不交的由一条链连接的环，则无解。

证明：考虑环 C_1, C_2 及连接它们的路径 P = u\to v，其中 u\in C_1，v\in C_2。令 P 上所有节点颜色集合为 \{A, B\}。固定 c_u = A，c_v 根据 |P| 奇偶性固定为 A 或 B 容易通过 P 导出矛盾。证毕。

进一步地，若 G 存在两个交于一点的环，则无解，此时 P 退化为单点。例如在上例基础上添加环 (1, 5, 6, 7)，令 S_5 = \{A, B\}，S_6 = \{A, C\}，S_7 = \{B, C\} 可固定 c_1 = A，矛盾。

两个四度点

注意到两个交于一点的环形成度数为 4 的节点，设两个 deg \geq 4 的节点 u, v。

若存在 u\to v 的两条路径 P_1, P_2 交于 q_1, q_2, \cdots, q_k\neq u, v，则 C_1 = u\xrightarrow{P_1} q_1 \xrightarrow{P_2} u 与 C_2 = v\xrightarrow{P_1} q_k\xrightarrow{P_2} v 至多交于一点 q_1，无解。

假设 u\to v 某四条路径分别长 L_1, L_2, L_3, L_4。

当 L 为奇数时，因无重边，故 L_2, L_3, L_4 \geq 3。因形如 “只能选某固定颜色” 的限制可通过度数为 2 的节点 以 2 为周期 传播，即讨论无解性时长 k 的链可归约至长 k - 2 的链，故只需考虑 L_2 = L_3 = L_4 = 3。根据固定的本质，读者容易自行构造反例。如果不会，见三度点部分 (3, 3, 1) 反例，其强于 (3, 3, 3)。

当 L 为偶数时，同理只需考虑 L_1 = L_2 = L_3 = L_4 = 2 的 K_{2, 4}。令 S_u = \{A, B\}，S_v = \{C, D\}，中间四个点分别为 \{A, C\}，\{A, D\}，\{B, C\}，\{B, D\} 即可。

因此，图上存在至少两个 deg\geq 4 的节点时，无解。

一个四度点

当图上仅有一个 deg\geq 4 的节点时，要么存在至少两个 deg = 3 的节点，要么剩余所有节点 deg = 2。

对于后者，其形态为两个交于一点的环，无解。

对于前者，设两个 deg = 3 的节点 u, v，同理可证 u\to v 之间任意路径仅在 u, v 处相交，与存在 deg\geq 4 的节点矛盾。

因此，图上存在至少一个 deg\geq 4 的节点时，无解。

接下来讨论不存在四度及以上节点的图。

三度点

讨论完四度点，让我们将目光转向三度点。一旦图上存在三度点的情况被讨论清楚，问题就迎刃而解。

考虑图上某两个三度点 u, v，上文已经说明 u\to v 之间任意路径仅在 u, v 处相交，故图上仅存在两个三度点。

设 u\to v 三条路径长 L_1, L_2, L_3，L_1 \geq L_2 \geq L_3。

考虑 L_3 = 1。

因无重边，故 L_1, L_2 \geq 3。如法炮制，根据归约关系考虑 L_1 = L_2 = 3。根据固定的本质，在最开始例子的基础上，添加环 (1, 2, 5, 6)，令 S_5 = \{A, C\}，S_6 = \{B, C\} 可固定 c_1 = A。无解，称为 (3, 3, 1) 反例。

考虑 L_3 = 2。

从简单情况入手，考虑 L_1 = L_2 = 2 的 K_{2, 3}。

• 若 S_u\cap S_v \neq \varnothing，则令 c_u 和 c_v 等于它们的交中的某个颜色，则中间三个点因为 |S| = 2，总可以选择不与该颜色相同的颜色，有解。
• 若 S_u\cap S_v = \varnothing，则 c_u 与 c_v 的颜色共有 4 种不同情况，而每个节点只被唯一情况封锁住，所以至少有一种情况没有封锁住任何节点，有解。

这说明 K_{2, 3} 有解。

进一步地，考虑 L_1 \geq 4。K_{2, 3} 的讨论给予我们突破点：考虑 c_u, c_v 的颜色情况数，与夹在中间的节点个数 2 作比较。若情况数 > 2 或 c_u = c_v 则有解，否则无解。

• 若 L_1 对应路径存在相邻两个点的 S 不同，则当 c_u 取两种颜色时，按照环边染色，c_v 分别有两种和至少一种合法选择。
  • 若 S_u\cap S_v \neq \varnothing，存在三种不同情况，有解。
  • 若 |S_u\cap S_v| = \{A\}，若 c_u = c_v = A 不合法，则剩余三种情况互不相同，有解；否则 c_u = c_v = A 合法，有解。
  • 若 S_u = S_v，c_u\neq c_v 的情况只有两种，必然存在 c_u = c_v 合法的情况，有解。
• 否则，由于 L_1 为偶数，所以 c_u = c_v，有解。

这说明仅有 L_1 \geq 4 时仍然有解。

容易发现上述证明并没有用到 L_1 \geq 4 的性质，即它可以用于证明 K_{2, 3} 的有解性。但如果不先从 K_{2, 3} 下手，不易想到情况数这一突破点。因此，从简单情况入手 是这种推性质题相当好用的解题技巧。

进一步地，考虑 L_1, L_2\geq 4。由于上文讨论过 (3, 3, 1) 无解，不难再此基础上稍作修补，构造出使得 (4, 4, 2) 无解的反例。提示：考虑固定的本质，L_1, L_2 \geq 4 说明存在两组自由点 j, k，每组自由点可固定 c_u 为某颜色。

综上，我们得到图上存在三度点有解的充要条件：图上仅存在两个三度点，且至少存在两个与两个三度点同时相邻的二度点。

偶环

最后，考虑仅存在二度点的图。因无重边，它是一个长度 \geq 4 的环。

类似地，考虑环上相邻三个节点 u, v, q 并最后考虑 v 的限制。若 u 从环的另一侧到 q 的路径上 S 相同，则 c_u = c_q 合法，有解。否则考虑使得 c_q 有两种染色方案的 c_u，无法封锁 v，有解。

结论

对 G 的每个连通块单独求解，若存在连通块无解则整张图无解。