正则图中最大诱导匹配与受限循环覆盖的近似算法研究

### 正则图中最大诱导匹配与受限循环覆盖的近似算法研究 #### 正则图中最大诱导匹配相关研究 1. **d - 有界图的简单性质** - 若边 \(e \in E\) 是三角形的一部分，其潜在冲突度至少降低 \(d\)。因为三角形的存在不影响 \(e\) 的一阶冲突边数量，但二阶冲突边数量从最多 \(2(d - 1)\) 条降为 \(d - 2\) 条。 - 若共享边 \(e' = \{k, l\}\) 连接 \(seci(e)\) 和 \(secj(e)\) 且二者都在 \(sideU\) 侧，\(ei = \{u, k\}\)，\(ej = \{u, l\}\) 和 \(e' = \{k, l\}\) 构成三角形，\(ei\) 和 \(ej\) 的潜在冲突度至少降低 \(d\)。 2. **共享边对 1 - 邻域的影响** - **引理 5**：连接 \(seci(e)\) 和 \(secj(e)\) 且二者都在 \(sideU\) 侧的共享边，使计入 \(1 - 邻域(e)\) 的边（来自 \(seci(e)\) 或 \(secj(e)\)）最多增加 \(d - 2\) 条。因为 \(|seci(e)| \leq d - 1\)，\(|secj(e)| \leq d - 1\)，且 \(e'\) 是共享边，所以 \(seci(e)\) 中的每条边最多与 \(secj(e)\) 中 \(d - 2\) 条不属于 \(seci(e)\) 的边相连，反之亦然。 3. **对角边的情况分析** - **引理 6**：若 \(e' \in seci(e)\)，\(e'' \in secj(e)\) 是对角边且 \(seci(e)\) 和 \(secj(e)\) 都在 \(sideU\) 侧，\(ei\) 和 \(ej\) 的潜在冲突度至少降低 1。因为边 \(e\) 作为正方形一部分时，其潜在冲突度至少降低 1，\(e'\)，\(e''\)，\(ei\) 和 \(ej\) 构成正方形，所以四条边的潜在冲突度都至少降低 1。 - **引理 7**：若 \(e' \in seci(e)\)，\(e'' \in secj(e)\) 是对角边且 \(seci(e)\) 和 \(secj(e)\) 都在 \(sideU\) 侧，\(1 - 邻域(e)\) 的大小使计入 \(1 - 邻域(e)\) 的边（来自 \(seci(e)\) 或 \(secj(e)\)）最多增加 1 条。因为 \(e1 = \{k, l\} \in seci(e)\)，\(e2 = \{l, m\} \in secj(e)\) 作为对角边连接 \(seci(e)\) 和 \(secj(e)\) 构成正方形，\(seci(e)\) 中的每条边通过这对对角边只与 \(secj(e)\) 中 1 条不属于 \(seci(e)\) 的边相连，反之亦然。 4. **一侧 1 - 邻域的边界** - **引理 8**：设 \(seci(e)\) 是 \(sideU\) 侧所有 \(secj(e)\) 组中，具有最大数量 \(M -\) 冲突度为 1 的边（不包括共享边）的组。那么属于 \(\{sideU - \{\{共享边\} \cup seci(e)\}\}\) 且 \(M -\) 冲突度为 1 的边的数量最多为 \(0.5d^2 - 1.5d + 1\)。产生冲突的方式有共享边和对角边两种： - 共享边：根据引理 5，每条共享边最多为解增加 \(d - 2\) 条边，但根据引理 4，\(ei\) 的潜在冲突度降低 \(d\)。 - 对角边：根据引理 7，每对对角边（其中一条边必须来自 \(seci(e)\)）为解增加 1 条边，且 \(ei\) 的冲突度降低 1。 - 若属于 \(\{sideU - \{\{共享边\} \cup seci(e)\}\}\) 且 \(M -\) 冲突度为 1 的边的数量大于 \(0.5d^2 - 1.5d + 1\)，则 \(ei\) 的冲突度 \(\leq 2d^2 - 2d + 1 - (0.5d^2 - 1.5d + 1) = 1.5d^2 - 0.5d\)，这与算法矛盾，因为阶段 1 后不存在冲突度 \(\leq 1.5d^2 - 0.5d\) 的边。 5. **共享边的边界** - **引理 9**：连接 \(seci(e)\) 和 \(secj(e)\) 的每条共享边使 \(e\) 的潜在冲突度至少降低 1。分两种情况证明： - \(seci(e) \in sideU\) 且 \(secj(e) \in sideV\) 或反之：\(ei = \{u, k\}\)，\(ej = \{v, l\}\)，\(e' = \{k, l\}\) 和 \(e = \{u, v\}\) 构成正方形，根据引理 6，\(e\) 的潜在冲突度降低 1。 - \(seci(e)\)，\(secj(e) \in sideU\) 或 \(seci(e)\)，\(secj(e) \in sideV\)：以 \(seci(e)\)，\(secj(e) \in sideU\) 为例，\(ei = \{u, k\}\)，\(ej = \{u, l\}\) 和 \(e' = \{k, l\}\) 构成三角形，\(e\) 的二阶冲突边数量从最多 \(2(d - 1)\) 条降为 \(2d - 3\) 条，所以 \(e\) 的潜在冲突度至少降低 1。 6. **近似边界的整合** - 若共享边数量 \(> 0.5d^2 - 1.5d + 1\)，则 \(e\) 的冲突度 \(\leq 2d^2 - 2d + 1 - (0.5d^2 - 1.5d + 1) = 1.5d^2 - 0.5d\)，与算法矛盾，所以共享边数量最多为 \(0.5d^2 - 1.5d + 1\)，即 \(M -\) 冲突度为 1 的共享边数量最多为 \(0.5d^2 - 1.5d + 1\)。 - \(seci(e)\) 中的边最多为 \(d - 1\) 条，与 \(e\) 一阶相邻的边加上 \(e\) 本身