图的所有潜在最大团列举

# 图的所有潜在最大团列举 ## 1. 基本概念与推论 ### 1.1 最小分隔器相关推论 设图 \(G = (V, E)\)，\(a\) 为 \(G\) 的一个顶点，\(G' = G[V \setminus \{a\}]\)。对于 \(G'\) 的任意最小分隔器 \(S\)，\(S\) 或者 \(S \cup \{a\}\) 是 \(G\) 的最小分隔器，且 \(|\Delta_G| \geq |\Delta_{G'}|\)。 ### 1.2 潜在最大团的定义 - 若图 \(G\) 存在一个最小三角剖分 \(H\)，使得顶点集 \(\Omega\) 是 \(H\) 的一个最大团，则称 \(\Omega\) 是图 \(G\) 的一个潜在最大团，记图 \(G\) 的潜在最大团集合为 \(\Pi_G\)。 - 图 \(G\) 的潜在最大团 \(\Omega\) 与包含在其中的最小分隔器密切相关，任何最小分隔器都包含在某个潜在最大团中，且 \(|\Pi_G|\) 至少为 \(|\Delta_G|/n\)。 ### 1.3 相邻分隔器的最大集合 若图 \(G\) 存在一个潜在最大团 \(\Omega\)，使得最小分隔器集合 \(S = \Delta_G(\Omega)\)，则称 \(S\) 是图 \(G\) 的相邻分隔器的最大集合，也说 \(S\) 在 \(G\) 中界定 \(\Omega\)。 ### 1.4 树宽和最小填充的计算 给定图 \(G\) 及其潜在最大团 \(\Pi_G\)，可以在 \(O(n^2|\Delta_G| \times |\Pi_G|)\) 时间内计算图 \(G\) 的树宽和最小填充。 ### 1.5 相关符号定义 - 设 \(K\) 是图 \(G\) 的顶点集，\(C_1(K), \ldots, C_p(K)\) 表示 \(G \setminus K\) 的连通分量，\(S_i(K)\) 表示 \(K\) 中与 \(C_i(K)\) 中至少一个顶点相邻的顶点。若 \(S_i(K) = K\)，则称 \(C_i(K)\) 是与 \(K\) 关联的完全分量。\(S_G(K)\) 表示图 \(G\) 中所有 \(S_i(K)\) 的集合。 - 对于图 \(G = (V, E)\) 和顶点集 \(X \subseteq V\)，\(G_X\) 表示通过对 \(X\) 进行完全化（即在 \(X\) 中任意非相邻顶点对之间添加边）得到的图。若 \(X = \{X_1, \ldots, X_p\}\) 是 \(V\) 的子集集合，\(G_X\) 是对 \(X\) 中所有元素进行完全化得到的图。 ## 2. 潜在最大团的判定定理 ### 2.1 判定定理内容 顶点集 \(K \subseteq V\) 是潜在最大团当且仅当： 1. \(G \setminus K\) 没有与 \(K\) 关联的完全分量。 2. \(G_{S_G(K)}[K]\) 是一个团。 若 \(K\) 是潜在最大团，则 \(S_G(K)\) 是界定 \(K\) 的相邻分隔器的最大集合，即 \(S_G(K) = \Delta_G(K)\)。 ### 2.2 相关备注 - 若 \(K\) 是图 \(G\) 的潜在最大团，对于 \(K\) 中的任意顶点对 \(x\) 和 \(y\)，要么 \(x\) 和 \(y\) 在 \(G\) 中相邻，要么它们通过 \(G \setminus K\) 的某个连通分量 \(C_i\) 相连。 - 考虑包含在潜在最大团 \(\Omega\) 中的最小分隔器 \(S\)，比较 \(G \setminus S\) 和 \(G \setminus \Omega\) 的连通分量，\(\Omega \setminus S\) 包含在与 \(S\) 关联的一个完全分量 \(C_{\Omega}\) 中，\(G \setminus S\) 的其他连通分量也是 \(G \setminus \Omega\) 的连通分量。反之，\(G \setminus \Omega\) 的一个连通分量 \(C\) 要么是 \(G \setminus S\) 的连通分量（此时 \(N_G(C) \subseteq S\)），要么包含在 \(C_{\Omega}\) 中（此时 \(N_G(C) \nsubseteq S\)）。 - 与最小分隔器不同，一个潜在最大团 \(\Omega'\) 不能严格包含在另一个潜在最大团 \(\Omega\) 中。 ### 2.3 判定算法复杂度 给定图 \(G\) 的顶点集 \(K\)，可以在 \(O(nm)\) 时间内识别 \(K\) 是否为图 \(G\) 的潜在最大团。具体步骤如下： 1. 线性时间内计算 \(G \setminus K\) 的连通分量 \(C_i\) 及其邻域 \(S_i\)。 2. 线性时间内验证 \(G \setminus K\) 没有与 \(K\) 关联的完全分量。 3. 对于每个 \(x \in K\)，线性时间内计算 \(K\) 中与 \(x\) 在 \(G\) 中相邻或通过 \(C_i\) 相连的所有顶点 \(y\)，从而验证 \(K\) 是否满足判定定理的条件。 ## 3. 潜在最大团与活跃分隔器 ### 3.1 活跃分隔器的定义 设 \(\Omega\) 是图 \(G\) 的潜在最大团，\(S \subset \Omega\) 是 \(G\) 的最小分隔器。若在图 \(G_{\Delta_G(\Omega) \setminus \{S\}}\) 中 \(\Omega\) 不是团，则称 \(S\) 是 \(\Omega\) 的活跃分隔器；否则，称 \(S\) 是 \(\Omega\) 的非活跃分隔器。 ### 3.2 相关命题 - 设 \(\Omega\) 是图 \(G\) 的潜在最大团，\(S \subset \Omega\) 是活跃分隔器，\((S, C_{\Omega})\) 是与 \(S\) 关联且包含 \(\Omega\) 的块，\(x, y \in \Omega\) 是 \(G_{\Delta_G(\Omega) \setminus \{S\}}\) 中的非相邻顶点，则 \(\Omega \setminus S\) 是 \(G[C_{\Omega} \cup \{x, y\}]\) 中的最小 \(x, y\) - 分隔器。 - 设 \(\Omega\) 是图 \(G\) 的潜在最大团，\(S \subset \Omega\) 是活跃分隔器，\((S, C_{\Omega})\) 是与 \(S\) 关联且包含 \(\Omega\) 的块，则存在图 \(G\) 的最小分隔器 \(T\)，使得 \(\Omega = S \cup (T \cap C_{\Omega})\)。 ### 3.3 包含活跃分隔器的潜在最大团数量 包含至少一个活跃分隔器的潜在