3-划分问题到子林同构问题的多项式变换

我们可以定义一个新的问题：给定一个无向图 $G=(V,E)$，是否存在一个 $3$ 划分 $/{V_1,V_2,V_3/}$，使得对于每个 $i//in//{1,2,3//}$，$G[V_i]$ 是一个森林。/n/n我们可以用以下方式将一个 $3$ 划分问题转化为一个子林同构问题：/n/n对于每个 $i//in//{1,2,3//}$，将 $G[V_i]$ 中的每个连通块看作一个节点，构成一个新的无向图 $H_i$。显然，$H_i$ 是一个森林。/n/n现在，我们将问题转化为：给定三个森林 $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$。/n/n可以证明，这两个问题是等价的。因此，我们可以用子林同构问题的算法来解决 $3$ 划分问题。