图的平面分隔符定理 我们先从平面图的基本概念开始。平面图是指可以画在平面上使得边仅在顶点处相交的图。这种画法称为平面嵌入。平面图的一个重要性质是，它们可以通过移除相对较少的顶点被分割成若干个较小的连通部分。这个性质由平面分隔符定理精确描述。 1. 分隔符的基本定义 在图论中，一个图 G=(V, E) 的分隔符是一个顶点子集 S ⊆ V，当从图中移除 S（以及与其相连的所有边）后，剩下的图会被分割成两个或多个互不连通的子图。每个这样的子图的大小（顶点数）通常不超过原图大小的一个固定比例（例如，2/3）。分隔符的作用类似于“瓶颈”，能将大图分解成更小的部分，这在设计分治算法时非常有用。 2. 平面图的特殊性质 平面图之所以重要，是因为它们受到欧拉公式的强大约束。对于一个连通的平面图，设其顶点数为 n，边数为 m，面数为 f，则欧拉公式表述为：n - m + f = 2。利用这个公式，可以证明任何平面图都满足 m ≤ 3n - 6（当 n ≥ 3 时）。这个不等式限制了平面图中边的最大数量，意味着平面图是“稀疏”的。正是这种稀疏性，为存在小的分隔符提供了可能性。 3. 平面分隔符定理的表述 最著名的平面分隔符定理由 Lipton 和 Tarjan 于 1979 年证明。其核心内容是：任何一个具有 n 个顶点的平面图，都存在一个大小不超过 √(8n) ≈ 2.83√n 的顶点分隔符 S。移除 S 后，剩下的图被划分为两个不相交的顶点子集 A 和 B，使得 A 和 B 之间没有边相连，并且 |A| ≤ 2n/3，|B| ≤ 2n/3。简单来说，你可以用大约 O(√n) 个顶点将一个平面图切成两块，每块的大小都不超过原图的三分之二。 4. 定理的证明思路（概述） 证明的关键步骤利用了平面图的层次结构： a. 生成树与对偶图 ：首先，在图的平面嵌入中选取一棵生成树。这棵生成树的对偶图（由面的邻接关系构成）会形成一个圈。 b. 寻找平衡分隔圈 ：通过对偶图进行广度优先搜索（BFS），可以找到一个圈 C，这个圈在原始图中对应一个环（可能不是诱导圈）。这个圈将平面图分成内部和外部两部分。 c. 调整平衡性 ：通过精心选择这个圈，可以确保圈内部的顶点数和外部的顶点数都大致平衡（都不超过 2n/3）。这个圈 C 本身的大小为 O(√n)，因为它通常是一个 BFS 层的边界。 d. 构造分隔符 ：分隔符 S 由圈 C 上的所有顶点组成。由于圈 C 的大小是 O(√n)，所以分隔符的大小也是 O(√n)。 5. 定理的推广与应用 平面分隔符定理不仅是一个优美的理论结果，还具有广泛的应用： 算法设计 ：它是设计高效分治算法的基础。例如，对于平面图上的NP难问题（如最大独立集），可以利用分隔符定理将问题分解为子问题，递归求解，然后合并结果，从而得到比一般图更高效的算法（有时甚至是多项式时间近似方案）。 推广到其他图类 ：该定理的思想被推广到排除某些小图作为子式的图族（如外平面图、有界树宽图等）。对于这些图类，也存在大小依赖于树宽的分隔符。 几何应用 ：该定理与几何中的区域分解密切相关，例如在计算几何中用于点集的划分。 总结来说，平面分隔符定理揭示了平面图可以被高效分解的内在结构特性，这一特性是许多高效算法设计的理论基石，并深刻影响了算法图论和计算几何的发展。