[BJOI2018] 染色 题解

[BJOI2018] 染色
神仙结论题，证明思路是 Alex_Wei 的。

我们设 \(S_u=(A,B)\) 表示 \(u\) 的颜色集合是 \(\{ A,B \}\)，\(a_u\) 表示 \(u\) 的颜色。
首先有一些比较显然的事情：

1. 不是二分图就一定无解，所以只有偶环。
2. 度数为 \(1\) 的点不影响答案，可以删去，所以可以不断去掉度数为 \(1\) 的点，下面假设图上只存在度数 \(\ge 2\) 的点。
3. 每个连通块可以分别考虑，下面假设图连通。

性质

有两个比较重要的性质。

性质一

考虑如下一条 \(S\) 相同的链，那么当第一个点的颜色确定了链上每个点的颜色也确定了，且以 \(2\) 为周期交替出现。

性质二

对于一个四元环，我们可以使得环上某个点只能取一种固定的颜色。

比如上图我们就固定了 \(a_1\) 只能取 \(B\)。
进一步的，不难发现对于任何环我们都可以通过类似的构造使得环上某个点只能取一种固定的颜色。

一些无解情况

通过上面两条性质我们可以推出一些无解情况。

两个由路径连接起来的简单环

对两个简单环，如果他们之间由一条路径连接起来，假设这条路径的两个端点为 \(u,v\)，其中 \(u,v\) 分别在两个环上，那么我们可以让这条路径上的点 \(S\) 都相同（假设为 \((A,B)\)），然后根据性质二通过第一个环固定 \(a_u=A\)，进一步的根据性质一得出 \(v\) 的颜色，然后再通过第二个环把 \(a_v\) 固定成另一个颜色推出矛盾。所以这种情况无解。
特殊地，当两个环相交于一点的时候，路径退化成一个点，此时一样无解。

两条相交路径

假设从 \(u\) 到 \(v\) 有两条在除了端点处相交的路径 \(P_1,P_2\)，设他们相交的点为 \(x_1,x_2,...,x_k\)（\(x_i\ne u,v\)），则 \(u-^{P_1}\to x_1-^{P_2}\to u\) 和 \(v-^{P_1}\to x_k-^{P_2}\to v\) 这两个环通过一条 \(x_1 \to x_k\) 的路径连接，无解。

四度点

这里的四度点指度数 \(\ge 4\) 的点

两个四度点

我们将举出反例证明此时无解。
这两个四度点之间必定有四条路径 \(P_1,P_2,P_3,P_4\)，且根据上面的分析这四条路径互不相交。由于是二分图，所以 \(P_1,P_2,P_3,P_4\) 长度的奇偶性相同。根据性质一如果某一条路径的长度 \(>3\) 那么我们可以把它的长度 \(-2\)，不影响反例的正确性，所以下面认为他们的长度 \(\le 3\)。

• 如果他们的长度为奇数，那么因为没有重边，必定存在三条路径的长为 \(3\)，反例如下：
  

• 如果长度为偶数，那么长度均为 \(2\)，反例如下：
  

可以发现这两个其实本质上还是两个环的无解情况。

一个四度点

如果不存在三度点，那么剩下的只有二度点，图形如两个环交于一点，无解；如果存在三度点，那么因为度数之和为偶数，所以至少存在两个三度点，而这两个三度点之间的路径必定交于这个四度点，无解。

综上如果图存在四度点就无解。

三度点

若存在三度点，那么至少存在两个，而类似于上面"一个四度点"的后半部分的分析，只能存在两个三度点。
仍然考察他们之间的三条不交路径 \(P_1,P_2,P_3\)，假设 \(|P_1|\ge |P_2| \ge |P_3|\)。

如果长度为奇数，那么当 \(|P_1|=|P_2|=3,|P_3|=1\) 时，反例只需要把"两个四度点的奇数情况"的反例中间那两个点去掉即可。对于其他情况根据性质一都可以归约到这个情况。、
所以长度只能是偶数，而根据 \(|P_1|=|P_2|=3,|P_3|=1\) 的反例不难构造出 \(|P_1|=|P_2|=4,|P_3|=2\) 的反例，所以有 \(|P_1|\ge 2,|P_2|=|P_3|=2\)，即图长这个样子：

若 \(P_1\) 上的点的 \(S\) 都相同，那么因为 \(|P_1|\) 是偶数，所以 \(a_u=a_v\)，\(a_x,a_y\) 显然有解。
否则，假设 \(S_u=(A,B)\)，那么当 \(a_u=A\) 时 \(a_v\) 两种颜色都可以取，当 \(a_u=B\) 时 \(a_v\) 至少有一种取值可以取（或者反过来），也就是说 \(a_u,a_v\) 的组合至少有三种是合法的（一共四种）：

• \(| S_u \cap S_v | \le 1\)：此时三种组合互不相同，根据鸽巢原理，三种组合中至少有一种能使得 \(a_x,a_y\) 都有解。
• \(S_u=S_v\)：此时有两种组合满足 \(a_u=a_v\)，那么必定有一组是合法的，有解。

综上有解当且仅当 \(|P_1|\ge 2,|P_2|=|P_3|=2\)。

结论

最后的结论就是，输出 YES 当且仅当：

1. 只存在二度点，即图是若干个不相交的简单环。
2. 只存在度数 \(\le 3\) 的点，且恰好有两个三度点，且有至少两个二度点同时和这两个三度点相邻。