树组装问题的可处理性与Petrie可划分平面图形的特征

### 树组装问题的可处理性与Petrie可划分平面图形的特征 #### 树组装问题 在树组装问题中，我们关注如何将森林 $F$ 中的树木组合成目标树 $T^*$。下面是一些关键规则和引理。 ##### 规则2 - 设 $q = |C_{B_γ}(r)|$ ，$p = |C_{T^*}(r^*)|$ 。 - 若 $q = 1$ 且 $p = 1$ ，则分别从 $F$ 和 $T^*$ 中移除节点 $r$ 和 $r^*$ 。 - 若 $q = 0$ 且 $p = 1$ ，则分别从 $F$、$T^*$ 和 $T$ 中移除节点 $r$、$r^*$ 和 $γ$ 。 - 注意，由于 $F$ 至少有两棵树，所以 $q$ 和 $p$ 不能同时为 0 。 ##### 引理4 对 $(F, T^*)$ 应用规则 2 得到实例 $I'$ 和辅助树 $T'$ ，则 $I'$ 相对于 $T'$ 为“是”当且仅当 $(F, T^*)$ 相对于 $T$ 为“是”。 ##### 通过排序构造子实例 当 $q$ 和 $p$ 的值不满足规则 2 的情况时，对于 $r$ 的每个子节点 $v$ ，在可行的附着方法 $E^+$ 下，$F \setminus B_γ$ 中至少有一棵树附着到 $B_γ(v)$ 的某个节点上。 我们先为 $r$ 的子节点 $\{v_1, \ldots, v_q\}$ 固定一个任意排序，其中 $q \leq p \leq h \leq k - 1$ 。对于 $r^*$ 的子节点 $u_1, \ldots, u_p$ 的排序，如果 $\Phi(C_{B_γ}(r))$ 中的节点总是在 $C_{T^*}(r^*) \setminus \Phi(C_{B_γ}(r))$ 的左侧（$\Phi$ 是由 $E^+$ 指定的从 $V(F)$ 到 $V(T^*)$ 的双射），则称该排序是调整过的。 ##### 引理5 若 $(F, T^*)$ 为“是”，则存在 $r^*$ 子节点的调整排序 $\rho = u_1, \ldots, u_p$ 和 $γ$ 子节点的排序 $\sigma = ν_1, \ldots, ν_h$ ，满足以下两个性质： 1. 对于所有 $1 \leq i \leq q$ ，有 $\Phi(v_i) = u_i$ 。 2. 可以在多项式时间内找到 $ν_1, \ldots, ν_h$ 的一个划分 $P = \{X_1, \ldots, X_p\}$ ，使得对于 $T(ν)$ 中的每个节点 $ν'$ （其中 $ν \in X_i$ ，$1 \leq i \leq p$ ），$B_{ν'}$ 中的节点在 $\Phi$ 下的像都在 $T^*(u_i)$ 中。 基于上述引理，我们可以将实例 $(F, T^*)$ 拆分为 $p$ 个子实例： 1. 对于 $1 \leq i \leq q$ ，令 $F_i = \{B_γ(v_i)\} \cup \{B_ν|ν \in V(T(ν')), ν' \in X_i\}$ ，$T^*_i = T^*(u_i)$ 。$(F_i, T^*_i)$ 的辅助树 $T_i$ 可通过将所有 $ν \in X_i$ 的 $T(ν)$ 附着到新根 $γ_i$ 得到，其中对应于 $γ_i$ 的树 $B_{γ_i}$ 是 $B_γ(v_i)$ 。 2. 对于 $q + 1 \leq i \leq p$ ，令 $F_i = \{B_ν|ν \in V(T(ν')), ν' \in X_i\}$ ，$T^*_i = T^*(u_i)$ 。$(F_i, T^*_i)$ 的辅助树 $T_i$ 是 $T(ν_j)$ ，其中 $X_i = \{ν_j\}$ 。 ##### 引理6 实例 $(F, T^*)$ 为“是”当且仅当对于所有 $1 \leq i \leq p$ ，子实例 $(F_i, T^*_i)$ 相对于辅助树 $T_i$ 为“是”。 ##### 算法呈现 以下是一个以实例 $(F, T^*)$ 和辅助树 $T$ 为输入的算法： ```mermaid graph TD; A[输入实例(F, T*)和辅助树T] --> B[判断|F|是否为1]; B -- 是 --> C[返回结果]; B -- 否 --> D[判断是否满足规则2]; D -- 是 --> E[应用规则2]; D -- 否 --> F[固定r的子节点排序]; F --> G[枚举r*子节点的排序]; G --> H[检查是否满足引理5的性质]; H -- 是 --> I[拆分实例为子实例]; I --> J[递归处理子实例]; J --> K[根据引理6判断结果]; K -- 是 --> L[返回是]; K -- 否 --> M[继续枚举排序]; M ```