无爪无小行星三元组图的研究与算法分析

### 无爪无小行星三元组图的研究与算法分析 #### 1. 引言 无爪无小行星三元组图是一类特殊的图，它既不包含爪形子图，也不包含小行星三元组。这类图是无小行星三元组图的一个子类，并且包含所有二部图的补图。在图论中，有许多与图相关的组合问题，如识别问题、计算半径、寻找中心顶点、独立集问题、支配集问题和着色问题等。本文将介绍针对无爪无小行星三元组图解决这些问题的高效算法，并论证这些算法的最优性。 以下是本文重点研究的几个问题： 1. **识别问题**：提出一个时间复杂度为 $O(n^{2.376})$ 的识别算法，且证明除非找到比 $O(n^{2.376})$ 更快的三角形识别算法，否则该算法是最优的。 2. **半径计算**：证明存在线性时间算法来计算无爪无小行星三元组图的半径。 3. **所有中心顶点计算**：给出一个线性时间算法来计算无爪无小行星三元组图的所有中心顶点。 4. **独立集问题**：存在线性时间算法解决无爪无小行星三元组图的独立集问题。 5. **支配集问题**：有线性时间算法解决无爪无小行星三元组图的支配集问题。 6. **着色问题**：证明计算无爪无小行星三元组图的最优着色与二部图和一般图的最大匹配计算相关，存在时间复杂度为 $O(\sqrt{nm})$ 的着色算法，且对该时间复杂度的改进意味着存在比 $O(n^2 + \sqrt{nm})$ 更快的二部图最大匹配算法。 #### 2. 预备知识 我们只考虑有限、无向、简单且连通的图。对于图 $G = (V, E)$ 和 $W \subseteq V$，$G[W]$ 表示由 $W$ 中顶点诱导的 $G$ 的子图。对于顶点 $x$，$N(x) = \{y \in V : \{x, y\} \in E\}$ 是 $x$ 的邻域，$N[x] = N(x) \cup \{x\}$ 是 $x$ 的闭邻域，$\alpha(G)$ 表示 $G$ 中独立集的最大基数。 以下是一些重要定义： - **爪形图**：一个包含四个顶点的图，其中一个顶点与其他三个顶点相邻，而这三个顶点两两不相邻。如果一个图不包含爪形图作为诱导子图，则称该图为无爪图。 - **小行星三元组（AT）**：图中的三个顶点组成的三元组，对于其中任意两个顶点，都存在一条连接它们的路径，且该路径不包含第三个顶点的闭邻域中的任何顶点。如果一个图不包含小行星三元组，则称该图为无小行星三元组图（AT - 自由图）。无爪无小行星三元组图就是既无爪又无小行星三元组的 AT - 自由图。 在研究 AT - 自由图时，有一个重要的概念是支配对（DP）。一个图 $G$ 的顶点对 $(x, y)$ 是支配对，如果对于 $x$ 和 $y$ 之间的任意路径 $P$，$P$ 的顶点集是 $G$ 的支配集。每个连通的 AT - 自由图都有一个支配对，并且可以通过线性时间算法计算得到，该算法的主要思想是使用字典序广度优先搜索（LexBFS）。 以下是 LexBFS 和 2LexBFS 的算法流程： ```plaintext Procedure LexBFS(G, x); Input: a connected graph G = (V, E) and a distinguished vertex x of G Output: a numbering σ of the vertices of G begin label(x) := |V |; for each vertex v in V \ {x} do label(v) := Λ; for i := |V | downto 1 do begin pick an unnumbered vertex v with (lexicographically) largest label; σ(v) := i; {assign to v number i} for each unnumbered vertex u in N(v) do append i to label(u) end return σ end; {LexBFS} Procedure 2LexBFS(G); Input: a connected graph G = (V, E) Output: a numbering σ2 of the vertices of G begin choose a vertex w of G; LexBFS(G, w); let σ1 be the output of LexBFS(G, w) and let x be the vertex with σ1(x) = 1; LexBFS(G, x); let σ2 be the output of LexBFS(G, x); return σ2 end; {2LexBFS} ``` 一个顶点排序 $x_n, x_{n - 1}, \ldots, x_1$ 被称为 $G$ 的 2LexBFS 排序，如果某个 $2L