图的平面分离定理 我们先从最直观的平面图说起。平面图是可以在平面上画出，且边与边只在顶点处相交的图。想象一下在一张纸上画一个复杂的电路图或地图，你希望连线不交叉，这就是平面图的核心。 现在思考一个问题：对于一个顶点数为n的平面图，是否存在一种方法，用相对较少的一些顶点将它“切开”，使得剩下的图被分成几个规模大致相当、且互不相连的部分？这就是 平面分离定理 要回答的问题。 第一步：分离器的直观概念 一个分离器，就像剪刀的刀刃。在图论中，对于一个图G，一个顶点集合S称为一个分离器，如果我们将S（及其相连的边）从G中移除后，剩下的图会被分割成两个或多个互不连通的“部分”（即连通分支）。一个“好”的分离器，应该“小”而“有效”——即集合S本身很小，并且它分割后产生的每个部分规模都不超过原图规模的某个固定比例（例如2/3）。 第二步：平面图独有的性质——平面分离定理的表述 对于平面图，存在一个非常优美的结论，这就是Lipton和Tajian在1979年证明的平面分离定理： 任何一个具有n个顶点的平面图，都存在一个大小不超过√(8n) ≈ 2.83√n 的分离器S，使得移除S后，剩下的每个连通分支的顶点数不超过2n/3。 这个定理是惊人的，因为它保证 总是存在 一个大小仅为O(√n)的分离器，将图平衡地分开。作为对比，一个n个顶点形成的简单链（路径图），其最优平衡分离器的大小是1（砍断中间一条边即可），但分离后两部分规模平衡。而对于一个完整的网格图（如√n × √n的网格），其最优分离器也是一条大约为√n的“分割线”。 第三步：定理证明的核心思想——循环塔定理 平面分离定理的一个标准证明依赖于图论中另一个深刻定理—— 循环塔定理 。我们一步步来看： 平面图与对偶图 ：任何一个连通的平面图G，都对应一个 对偶图G * 。G的每个面变成G 的一个顶点；如果G中两条边相邻于一个公共面，则在G 中对应的顶点间连一条边。 生成树与补树 ：我们在原图G中任取一棵 生成树T （包含G所有顶点且无圈的连通子图）。那么，那些 不在T中的边 ，被称为“补边”。每一条补边，在G的对偶图G* 中，都对应一条边。 关键构造 ：考虑对偶图G 中所有由“补边”对应的边构成的集合，它们恰好构成G 的一棵 生成树 ！这棵生成树被称为T的“补树”或“循环塔”。 分离操作 ：现在，我们在G 的这棵生成树（补树）上，找一条边e ，使得移除它后，生成树被分成两棵子树，每棵子树所关联的G中的顶点数都不超过2n/3。根据树的特性，这样的边总是存在的（类似于在树中找一个平衡的分割点）。 回到原图 ：对偶图中的这条边e* ，对应回原图G，就是 一条边e 。我们取这条边e的两个端点，再加上生成树T中连接这两个端点的 唯一路径 上的所有顶点，这些顶点构成的集合S，就是我们想要的分离器。 规模估计 ：因为T是一棵树，连接两点的唯一路径长度可以控制。通过更精细的分析（涉及生成树的最短路径），可以证明这条路径上的顶点数，即分离器S的大小，不超过√(8n)。 第四步：定理的推广与加强 原始的平面分离定理可以进一步强化： 常数优化 ：后来有研究者将分离器大小上限改进到了√(6n) ≈ 2.45√n，甚至更小。 更一般的图类 ：这个思想被极大地推广了。如果一个图 不包含 一个特定的非平面子图（例如完全图K5或完全二分图K3,3）作为其“拓扑子式”（可以粗略理解为经过顶点分裂、边收缩等操作后能得到），那么该类图也存在大小为O(√n)的平衡分离器。这是算法图论中里程碑式的结论。 第五步：定理的重大意义与应用 平面分离定理不仅仅是图论中的一个漂亮结论，它是 算法设计 ，特别是 分治算法 的基石。 分治算法 ：对于许多在平面图上的NP难问题（如寻找最小顶点覆盖、最大独立集等），我们可以利用平面分离定理设计高效的近似算法或精确指数时间算法。基本步骤是：找到平衡分离器S，然后递归地解决分离后的各个子问题，最后将解组合起来。由于分离器很小，需要枚举的可能性受限，从而提升了效率。 数据结构 ：它也是设计平面图点位置、最短路径查询等高效数据结构的核心工具。 并行计算 ：帮助将大图平衡地划分到多个处理器上，以最小化通信开销。 总结来说， 图的平面分离定理 揭示了平面图可以被一个小型顶点集平衡分割的深刻结构性质。它的证明巧妙结合了对偶图和生成树理论，而其应用彻底改变了我们对平面图算法设计的认知，是理论计算机科学和图论交叉领域的一颗明珠。