利用数字搜索树修剪图

### 利用数字搜索树修剪图 在图处理领域，为了利用图结构实现更高效的算法，我们可以证明在某些特殊的修剪情况下，顶点的一些良好排序能产生时间和空间复杂度均为线性的算法，例如计算二分图的“修剪图”。此外，对于二分距离遗传图上的完全二分覆盖问题，我们也通过线性算法改进了复杂度边界。 #### 1. 数据结构 ##### 1.1 通用问题 设 $G = (V, E)$ 为无向图。对于 $x \in V$，$N(x) = \{y \in V, y \neq x|(x, y) \in E\}$ 是 $x$ 在 $G$ 中的开邻域，$N_c(x) = N(x) \cup \{x\}$ 是其闭邻域。若 $\#N(x) = 1$，则 $x$ 为悬挂顶点；若 $N(x)\setminus\{y\} = N(y)\setminus\{x\}$，则 $x$ 和 $y$ 为孪生顶点。非相邻的孪生顶点称为真孪生顶点，相邻的孪生顶点称为假孪生顶点。 计算图 $G$ 的“修剪图”，主要需检测假孪生顶点（即 $N(x) = N(y)$ 的顶点 $x$ 和 $y$）和真孪生顶点（即 $N_c(x) = N_c(y)$ 的顶点 $x$ 和 $y$）。检测悬挂顶点只需一个数据结构来跟踪每个顶点 $x$ 的度数 $\#N(x)$。之后，需从图中删除顶点，并尝试检测新的可移除顶点，依此类推。 此过程可换种方式表达。考虑集合族 $\{N(x)|x \in V\} \cup \{N_c(x)|x \in V\}$，它完全刻画了图 $G$。主要需检测相等集合以检测孪生顶点（注意，对于任意 $x$ 和 $y$，$N_c(x) = N(y)$ 不可能成立）。删除顶点 $x$ 后，需通过删除集合 $N(x)$ 和 $N_c(x)$ 并从其他集合中删除 $x$ 的所有出现来更新集合族。 现在将主要问题用集合形式重新表述。设 $X$ 是基数为 $n$ 的集合，给定 $X$ 上的 $k$ 个集合 $S_1, \ldots, S_k$。问题是找到一种数据结构，使我们能以最佳摊还复杂度执行以下操作： - **相等操作**：找到 $(i, j)$ 使得 $S_i = S_j$，$i \neq j$，或检测所有集合都不同。 - **集合删除操作**：给定 $i$，删除 $S_i$。 - **元素删除操作**：给定 $x \in X$，从所有集合中删除 $x$ 的所有出现。 ##### 1.2 数据结构概述 输入由 $k$ 个集合 $S_1, \ldots, S_k$ 组成，$S_i \subseteq X$，$\#X = n$。设 $l_i$ 为 $S_i$ 的基数，$d$ 为输入大小，假设 $d \in \Omega(k + \sum_{i = 1}^{k} l_i)$。在图修剪问题中，$d \in \Theta(m + n)$ 且 $k = n$。 需要 $X$ 上的一个顺序，因为会涉及排序。对于一般结果，无需计算特定顺序，输入的隐式顺序即可。但在某些特定情况下，若计算出精心选择的顺序，可保证线性时间和空间算法。 顺序将 $X$ 与 $[[1, n]]$ 对应，可将 $X$ 上的集合（如 $S_i$）与 $[[1, n]]$ 中字母排序的单词对应。 第二步，将表示集合的字母排序的单词存储在字典树（一种通过带标签的边编码单词的树）中，称此字典树为字典序树。以下是字典序树的一个示例： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A([Root]):::startend -->|1| B(S1,S5):::process A -->|2| C(S3,S4):::process B -->|2| D(S1):::process B -->|3| E(S1,S2,S5):::process C -->|3| F(S3,S4):::process D -->|3| E D -->|4| G(S1):::process E -->|4| G F -->|5| H(S3):::process ``` 字典序树的特点： - 同一父节点的两条边不会有相同标签。对于给定的 $i$，恰好有一个节点标有 $S_i$，且该节点也标有所有等于 $S_i$ 的 $S_j$。 - 所有叶子节点至少对应一个 $S_i$，且边数为 $O(d)$。 数据结构的基本项是边及其指向的节点，称为“nodge”。它包含以下信息： - 一个标记（如 0），表明此结构为