排列图重构算法与共线图子类和谐着色问题研究

# 排列图重构算法与共线图子类和谐着色问题研究 ## 1. 排列图重构算法 ### 1.1 非关键情况 考虑原像图 $G = (V, E)$ 存在一个最小强多顶点模块 $M$，且 $|M| \geq 3$，同时 $G[M]$ 非关键的情况。 - 若 $M$ 是素模块，根据引理，$G[M]$ 是素图，存在顶点 $v$ 使得 $G[M] - v$ 是素图，那么 $M - v$ 是 $G[M] - v$ 的最小强多顶点模块。 - 若 $M$ 不是素模块，根据模块分解定义，$G[M]$ 是完全图或者由孤立顶点组成，同样存在顶点 $v$ 使 $M - v$ 是 $G[M] - v$ 的最小强多顶点模块。 搜索原像的方法是，向图集中每个图的每个最小强多顶点模块 $M'$ 添加一个顶点 $v$，检查 $M'$ 是否为所需的 $M - v$。对于每个候选图，使用 DECK CHECKING 算法检查其是否为原像。 若能确定 $N_G(v)$，就能构建 $G$ 的候选图。由于 $M' \cup \{v\}$ 应是 $G$ 的模块，所以很容易确定 $N_G(v) \setminus M'$，剩下的任务是确定 $N_G(v) \cap M'$。 根据模块分解定义，$M'$ 可能是团、孤立顶点集合或诱导素图的模块。若 $M'$ 是团或由孤立顶点组成，结合已知的 $G$ 的度序列，可将 $v$ 连接到 $M'$ 中 $deg_G(v) - |N_G(v) \setminus M'|$ 个顶点。 若 $G[M']$ 是素图，关于模块分解为素图的排列图有唯一表示，$v$ 与 $M'$ 中顶点的连接方式只有 $O(n^2)$ 种。通过 DECK CHECKING 算法检查这 $O(n^2)$ 个候选图是否为原像，可得到多项式时间算法。 算法时间复杂度分析：图集中有 $n$ 个图，每个图有 $O(n)$ 个最小强多顶点模块，计算这些模块的时间复杂度为 $O(n + m)$，DECK CHECKING 的时间复杂度为 $O(n^4)$，计算排列图的排列图的时间复杂度为 $O(n + m)$，所以该算法的时间复杂度为 $O(n \cdot n((n + m) + n^2 \cdot n^4)) = O(n^8)$。 定理：若排列图原像 $G = (V, E)$ 有最小强多顶点模块 $M$ 且 $|M| \geq 3$，$G[M]$ 非关键，则可在 $O(n^8)$ 时间内重构 $G$。 算法代码如下： ```plaintext for each graph G′ in the deck { for each minimal strong multi-vertex module M ′ of G′ { prepare a isolated vertex v; connect v to vertices in V \ M ′ suitably; if M ′ is a clique, or M ′ are isolated vertices { connect v to degG(v) −|NG(v) \ M ′| vertices in M ′; do DECK CHECKING; } else { create a unique permutation diagram of G[M ′]; for each way of adding v do DECK CHECKING; } } } ``` ### 1.2 关键情况 考虑原像 $G = (V, E)$ 的每个最小强多顶点模块 $M$ 满足 $G[M]$ 是关键图，或者每个最小强多顶点模块大小为 2 的情况。 - **模块大小为 2 的情况**：大小为 2 的模块形成双胞胎顶点，此时重构 $G$ 较容易。图集中的任何图 $G'$ 是从 $G$ 中移除一个双胞胎顶点得到的，可通过复制 $G'$ 中的顶点来重构 $G$。对图集中每个图的每个顶点创建弱双胞胎和强双胞胎顶点，使用 DECK CHECKING 算法检查得到的图是否为原像。 - **部分模块大小大于 2 的情况**：设 $G$ 中存在大小大于 2 的最小强多顶点模块 $M$，因为 $G[M]$ 是关键图，它同构于 $H(|M|)$ 或 $H(|M|)$。$x_1$ 和 $x_2$ 在 $H(|M|)$ 和 $H(|M|)$ 中几乎是双胞胎顶点，对应 $M$ 中的顶点 $v_1$ 和 $v_2$ 满足 $|N_{G[M]