试构造一个从 3 划分问题到子林同构问题的多项式变换

我们可以定义一个新的问题：给定一个无向图 $G=(V,E)$，是否存在一个 $3$ 划分 ${V_1,V_2,V_3}$，使得对于每个 $i\in{1,2,3}$，$G[V_i]$ 是一个森林。

我们可以用以下方式将一个 $3$ 划分问题转化为一个子林同构问题：

对于每个 $i\in{1,2,3}$，将 $G[V_i]$ 中的每个连通块看作一个节点，构成一个新的无向图 $H_i$。显然，$H_i$ 是一个森林。

现在，我们将问题转化为：给定三个森林 $H_1,H_2,H_3$，是否存在一个同构映射 $f:V(H_1)\cup V(H_2)\cup V(H_3)\to V$，使得对于每个 $i\in{1,2,3}$，$f(V(H_i))\subseteq V_i$。

可以证明，这两个问题是等价的。因此，我们可以用子林同构问题的算法来解决 $3$ 划分问题。