平面反馈顶点集的改进内核

### 平面反馈顶点集的改进内核 #### 1. 基本概念 在图论中，对于图 $G$ 中的顶点 $v$，用 $C(v)$ 表示包含顶点 $v$ 的所有环的集合。对于 $V(G)$ 的子集 $A$，定义 $C(A) = \bigcup_{v\in A}C(v)$。用 $P_i$ 表示与长度为 $i$ 的路径同构的（子）图，路径长度指构成该路径的边的数量，路径 $P$ 的内部顶点集用 $I(P)$ 表示。 当 $C(u) \subset C(v)$ 时，称顶点 $u$ 被顶点 $v$ 支配，即经过 $u$ 的每个环也经过 $v$。检测这种环支配很容易，对于每对 $\{u, v\} \subset V$，删除 $v$ 并检查 $u$ 是否属于剩余图的一个环，可通过深度优先搜索在 $G$ 具有线性数量的边的情况下以线性时间完成。 #### 2. 约简规则 以下是一系列用于内核化算法的约简规则，每个规则都描述了一个（条件，动作）对，当相应条件成立时可执行该动作。 |规则编号|条件|动作| | ---- | ---- | ---- | |规则 1|顶点的度数小于 2|删除该顶点| |规则 2|顶点 $u$ 的度数为 2，且其关联的是单边 $uv$ 和 $uw$|删除 $u$ 并添加边 $vw$| |规则 2*|顶点 $u$ 有两个邻居 $v$ 和 $w$，其中 $uv$ 是单边，$uw$ 是双边|将 $w$ 放入 $S$，$k$ 减 1，删除 $u$ 和 $w$| |规则 3|两个顶点之间的边数超过 3 条|安全地移除除两条边之外的所有边| |规则 4|顶点 $u$ 恰好有两个邻居 $v$ 和 $w$，且 $uv$、$uw$ 和 $vw$ 都是双边|将 $v$ 和 $w$ 都添加到 $S$，$k$ 减 2，删除 $u$、$v$ 和 $w$| |规则 5|$uv$ 是 $G$ 中的双边，$w$ 是度数为 3 的顶点，其邻居为 $u$、$v$ 和 $w'$|删除 $w$ 并添加两条边 $uw'$ 和 $vw'$| |规则 6|$P$ 是端点为 $u$ 和 $v$ 的诱导路径，且 $N(P \setminus \{u, v\}) = \{w\}$，$P$ 有超过两个内部顶点|将 $w$ 放入 $S$ 并删除它，由于规则 2 的重新应用，$P$ 被边 $uv$ 替换| |规则 7|$(A, B) = K_{2,b}$ 是 $G$ 的子图，$b \geq 3$，且 $B$ 中的每个顶点的度数为 3|在 $A$ 的两个元素之间添加双边，通过规则 5 和（可能）规则 4 删除 $B$ 的所有元素| |规则 8|$P$ 是满足 $|N(I(P))| = 4$ 的诱导路径，$|I(P)| = 6$，且 $|N_{I(P)}(v)| \geq |N_{I(P)}(u)|$|删除 $v$ 并将 $k$ 减 1| 这些规则的应用过程如下： ```mermaid graph TD; A[开始] --> B[检查规则 1 条件是否满足]; B -- 是 --> C[执行规则 1 动作]; B -- 否 --> D[检查规则 2 条件是否满足]; C --> D; D -- 是 --> E[执行规则 2 动作]; D -- 否 --> F[检查规则 2* 条件是否满足]; E --> F; F -- 是 --> G[执行规则 2* 动作]; F -- 否 --> H[检查规则 3 条件是否满足]; G --> H; H -- 是 --> I[执行规则 3 动作]; H -- 否 --> J[检查规则 4 条件是否满足]; I --> J; J -- 是 --> ```