图的平面性检测算法

题目描述

给定一个无向图 G = (V, E)，请你判断这个图是否是平面图（Planar Graph）。
平面图是指可以画在平面上，使得任何两条边仅在顶点处相交，而不会在非顶点处交叉的图。
我们需要一个算法，它接收图的邻接表表示，输出“是”（平面图）或“否”（非平面图）。

1. 问题背景与基础概念

平面图在电路板设计、地图着色等领域有重要应用。判断一个图是否平面，是图论中的一个经典问题。我们先明确几个关键点：

• 库拉托夫斯基定理（Kuratowski’s Theorem）：一个图是平面图，当且仅当它不包含K₅（完全图5个顶点） 或 K₃,₃（完全二分图两边各3个顶点） 的细分（subdivision）。细分指在原图的边上插入一些新顶点。
• 欧拉公式（用于平面连通图）：如果 G 是一个连通的平面图，有 |V| 个顶点、|E| 条边，并且将平面划分成 |F| 个面（包括最外面的无限面），则 |V| - |E| + |F| = 2。
  由此可推出：对于 |V| ≥ 3 的简单连通平面图，有 |E| ≤ 3|V| - 6；如果是二分图，则有 |E| ≤ 2|V| - 4。这些是平面图的必要条件，可快速排除一些非平面图（比如 |E| 太大时），但不是充分条件。

因此，算法需要检查图是否包含 K₅ 或 K₃,₃ 的细分。直接找细分比较困难，但有一个等价判定：

• 平面性检测算法：我们将图逐步简化（去掉度数为1的顶点、合并某些边等），最后通过深度优先搜索（DFS）在特定嵌入中尝试构造平面画法。最著名的算法是 Left-Right Planarity Test（左右平面性测试），它是基于 路径加法方法 的线性时间算法。

我们这里讲解一个经典且相对容易理解的算法：基于 DFS 的平面性测试（简化的路径添加法），它可以在 O(|V|) 时间内判断一个图是否平面。

2. 核心思路

算法主要步骤：

1. 预处理：检查边的数量是否超过 3|V|-6（或二分图时 2|V|-4），若超过则直接判定非平面。否则继续。
2. 构建 DFS 树：对图做深度优先搜索，得到一棵 DFS 生成树，并为每个顶点标上 DFS 序号（dfs_num）。
   在 DFS 过程中，我们会遇到两种边：
   • 树边（tree edge）：属于 DFS 树的边。
   • 回边（back edge）：连接当前顶点与其祖先（在 DFS 树中）的边。
3. 处理回边为路径：每条回边对应一个“返祖”路径。我们把这些回边（以及它们对应的树上路径）看作要嵌入的片段。
4. 合并路径到嵌入中：我们从 DFS 树的叶子向根逐步添加回边对应的路径。每个顶点处维护一个邻接边按顺时针顺序排列的循环列表（即局部嵌入）。添加新路径时，检查它能否插入到当前顶点的边序列表中而不引起交叉——这通过判断该路径在列表中的“区间”是否被其他路径的端点占用来实现。
5. 冲突检测：如果某条路径无处可放（区间被占满），则说明图是非平面的。

3. 逐步详解

步骤 1：快速不等式检查

计算 |V| 和 |E|。

• 如果 |V| ≥ 3 且 |E| > 3|V| - 6，则直接输出“非平面”。
• 如果图是二分图（可以先用 BFS 染色判断）且 |E| > 2|V| - 4，也直接输出“非平面”。
  这个步骤可以在 O(|V|+|E|) 内完成，并且能快速排除大部分密集的非平面图。

步骤 2：DFS 生成树与回边收集

进行 DFS，记录：

• dfs_num[v]：顶点 v 的 DFS 序号（从 1 开始）。
• parent[v]：在 DFS 树中的父节点。
• low[v]：通过 v 的后代能到达的最小 DFS 序号（用于找回边）。
  在 DFS 过程中，如果遇到边 (u, v) 且 v 已被访问但不是 u 的父亲，则这是一条回边（此时 dfs_num[v] < dfs_num[u]）。
  我们把这些回边收集起来，记为 (u, v)，其中 u 是后代，v 是祖先。

步骤 3：将回边转化为路径

对于每条回边 (u, v)，它对应的路径是：从 v 沿着树边向下走到 u，然后加上回边 (u, v)。
我们只需要关心这条路径上各顶点处的“嵌入顺序”。
实际上，我们可以把路径看作在 v 和 u 之间的一个“需求”：在 v 和 u 处，这条路径需要被插入到它们的邻接边列表中。

步骤 4：按 DFS 逆序处理路径

我们按照 DFS 完成时间的逆序（即从叶子向根）处理这些路径。
为每个顶点维护一个 嵌入列表，初始时只有树边（按 DFS 访问顺序排列）。
当我们处理一条路径 P（对应回边 (u, v)），我们需要把 P “安装”到当前嵌入中：

• 在 u 处：P 需要连接 u 到其祖先 v。我们检查 u 的嵌入列表中，其父边两侧的空位是否可用。
• 在 v 处：同样检查 v 的嵌入列表中，连接其子树的边之间的空位。
  关键点：路径 P 在 u 和 v 处会占用一个“区间”。如果这个区间已经被其他路径完全占据（即没有空位插入新的边），则发生冲突 → 图非平面。

步骤 5：冲突判断与区间管理

为了高效判断，我们为每个顶点维护一个 区间列表，表示已经被占用的位置。
当添加新路径时，我们尝试在 u 和 v 处各找一个未被占用的区间来放置这条路径。如果两边都能找到相容的区间，则将其标记为占用，并更新区间列表；否则判定非平面。

这个区间合并过程可以用 并查集 或 栈 来高效实现，确保总时间复杂度 O(|V|)。

4. 算法实现概述（伪代码）

函数 IsPlanar(G):
  如果 |V| <= 4: 返回 True   # 小图总是平面
  如果 |E| > 3|V| - 6: 返回 False
  
  对 G 进行 DFS，得到 DFS 树、回边列表 back_edges
  初始化每个顶点的嵌入列表（只有树边）
  
  按 DFS 完成时间逆序处理回边：
    对于每条回边 (u, v):
      在 u 处计算可插入的区间 Iu
      在 v 处计算可插入的区间 Iv
      如果 Iu 为空 或 Iv 为空:
        返回 False
      否则:
        在 u 和 v 的嵌入列表中标记 Iu 和 Iv 为占用
        更新相关顶点的区间信息
  
  返回 True

5. 例子演示

考虑一个 K₃,₃ 图（两边各3个顶点，是完全二分图）：
顶点集 {a,b,c} 和 {1,2,3}，所有 a,b,c 与 1,2,3 之间都有边。

• 快速检查：|V|=6，二分图，|E|=9 > 2*6-4=8，因此直接判定非平面。
  这符合 K₃,₃ 是非平面图的事实。

再考虑一个 K₅（5个顶点的完全图）：
|V|=5，|E|=10 > 3*5-6=9，因此也直接判定非平面。

考虑一个 立方体图（8个顶点，12条边）：
|V|=8，|E|=12 ≤ 3*8-6=18，通过不等式检查。
运行算法时，DFS 树会生成，回边被逐步添加。因为立方体图是平面图，算法会成功为所有回边找到插入位置，最终返回 True。

6. 复杂度分析

• 快速不等式检查：O(|V|+|E|)。
• DFS 构建树与收集回边：O(|V|+|E|)。
• 区间管理与路径插入：每个顶点和每条边只被处理常数次，总时间 O(|V|+|E|)。
  因此，整个算法是 O(|V|+|E|) 的，即线性时间。

7. 总结

图的平面性检测是一个深入的问题，但我们通过 DFS 树分解、回边路径添加与区间冲突检查，可以在线性时间内完成。
这个算法实际上是 Left-Right Planarity Test 的一个简化版本，它避免了复杂的嵌入数据结构，而是用区间占用思想来实现。
如果你希望进一步深入，可以学习 Boyer-Myrvold 平面性测试（也是线性时间），它更高效且被用在许多图库中。