图的平面分隔符定理 我们来循序渐进地学习图的平面分隔符定理。这个定理是平面图算法研究中的一个核心工具，它揭示了平面图可以被高效地“分割”成更小部分的结构特性。 基本概念铺垫 平面图 ：一个图如果可以画在平面上，使得其边仅在顶点处相交，则称该图是平面图。 顶点数和边数 ：对于一个连通的平面图，设其顶点数为 n ，边数为 m ，根据欧拉公式，有 m ≤ 3n - 6 （当 n ≥ 3 ）。这个关系很重要，它表明平面图是“稀疏”的。 分隔符 ：图的一个分隔符是一个顶点子集 S ，如果从图中移除 S （同时移除与这些顶点关联的边），那么图会被分割成两个或多个互不连通的部分。这些部分中的每一个连通分量都是一个“片段”。 平衡分隔 ：一个理想的分隔应该满足： 分隔符 S 本身要小。 分隔后产生的每个片段的大小（顶点数）都不超过原图大小的一个固定比例（例如 2n/3 ）。这确保了分割是“平衡”的，避免了产生一个巨大的片段和一个极小的片段。 定理的表述 平面分隔符定理有一个经典且强有力的形式，由 Lipton 和 Tarjan 于 1979 年证明： 任何一个包含 n 个顶点的平面图，都存在一个大小不超过 √(8n) ≈ 2.83√n 的顶点分隔符 S ，使得移除 S 后，剩下的图被划分为两个不相连的部分 A 和 B，每个部分满足 |A| ≤ 2n/3 且 |B| ≤ 2n/3 。 定理的直观理解与重要性 这个定理为什么如此重要？ “平方根”级别的分隔符 ：定理告诉我们，只需要移除大约 O(√n) 个顶点，就能将一个庞大的平面图（可能有数百万顶点）切成两个规模相当的部分。这个数量远小于图的总大小 n 。 算法设计的基石 ：这是分治算法在平面图上能高效运行的关键。我们可以利用这个定理： 分 ：找到分隔符 S ，将原图 G 分解为 A、S、B。 治 ：在（通常小得多的）片段 A ∪ S 和 B ∪ S 上递归地解决问题。 合 ：合并子问题的解，得到原问题的解。 应用领域 ：这种“分隔符分解”策略被广泛应用于平面图的诸多算法中，例如： 最短路径计算 网络流问题 图的着色问题 旅行商问题的近似算法 证明思路概览（不涉及复杂计算） 虽然完整证明需要一些图论知识，但其核心思想非常优雅，可以概括为以下几步： a. 构建生成树 ：首先，为平面图 G 找到一个生成树 T。 b. 利用平面性 ：因为 G 是平面图，所以那些不属于树 T 的边（称为“非树边”）在平面的嵌入中会形成“面”。这些非树边可以被组织成一个层次结构。 c. 寻找“中心”层 ：在这个层次结构中，必然存在一个“层面”或一个“环”，它能够将图相对平均地分成内部和外部两部分。这个性质由平面图的嵌入和生成树的结构所保证。 d. 构造分隔符 ：这个“中心”环本身可能不够小。但是，我们可以通过精心选择这个环上的一小部分顶点（例如，每隔一个顶点选一个），构成一个集合 S 。可以证明，这个集合 S 的大小为 O(√n) ，并且移除 S 后，图被分成的两个部分大小都不超过 2n/3 。 推广与变体 平面分隔符定理的思想被进一步推广： 更小的常数 ：后续研究将分隔符大小的常数从 √8 优化到了 √(4.5) ≈ 2.12 ，这几乎是理论上的最优值。 更广泛的图类 ：这个概念被推广到“排除某个固定子图作为子式的图族”。例如，如果一个图不能以某种“画法”画在某个曲面（如环面）上，那么它也可能存在大小约为 O(√n) 的分隔符。这对于设计更广泛的图类算法具有重要意义。 总结来说，平面分隔符定理深刻地刻画了平面图可以被高效分解的内在结构特性，它为处理大规模平面图问题提供了一个强大而通用的算法范式。