无向图的平面性检测（Left-Right Planarity Test）
字数 2537 2025-12-08 15:45:34

无向图的平面性检测（Left-Right Planarity Test）

好的，我们来详细讲解一个经典的图论算法：无向图的平面性检测。这个问题是判断一个给定的无向图能否在平面上绘制，使得任意两条边除了在顶点处外都不相交。我们将重点介绍一种基于深度优先搜索（DFS）生成树和嵌入思想的左-右平面性测试算法（Left-Right Planarity Test），它是基于路径添加（path addition）方法的一种高效实现。

1. 问题描述

给定一个无向连通图 \(G = (V, E)\)（若不连通，则对每个连通分量分别处理），判断 \(G\) 是否是平面图。
平面图：可以在平面上画出该图，使得没有两条边在非顶点处交叉。

目标：设计一个算法，输入图的顶点和边，输出“是平面图”或“不是平面图”。

2. 算法基础概念准备

在进入算法前，我们需要理解几个关键概念：

  • Kuratowski 定理：一个图是非平面图当且仅当它包含 \(K_5\)（5个顶点的完全图）或 \(K_{3,3}\)（完全二分图，两边各3个顶点）的细分（即边上可以插入额外顶点）。

  • 平面图性质（欧拉公式）：对连通平面图，有 \(V - E + F = 2\)，其中 \(F\) 是面数。由此可推出 \(E \le 3V - 6\)（当 \(V \ge 3\) 且无三角形时，\(E \le 2V - 4\)）。这可以用来快速排除一些非平面图，但不能判定。

  • DFS 生成树：算法首先对图做一次深度优先搜索，得到一棵生成树。树边（tree edges）形成树结构，回边（back edges）指向祖先。

  • 剩余图：去掉树边后，剩下的回边形成一组“剩余边”，每条回边对应 DFS 树中从一个顶点到其祖先的一条路径（在树上的路径）。

  • 路径添加方法（path addition method）：平面性测试算法（如左-右算法）的核心是，尝试将剩余边对应的路径一条一条嵌入到 DFS 树所在的平面上，并检查是否会引起交叉冲突。

3. 左-右平面性测试算法核心思想

左-右算法（由 H. de Fraysseix, P. Rosenstiehl 等提出）是一种基于 DFS 树和回边路径的平面性判定算法，其时间复杂度为 \(O(|V|)\)。

基本步骤：

  1. 对图进行深度优先搜索（DFS），得到一棵生成树，并为每个顶点分配 DFS 序号（dfn）。
  2. 识别出所有的回边（back edge），每条回边对应 DFS 树中从一个顶点到其祖先的一条“返祖路径”。
  3. 将这些回边（或它们对应的路径）转化为“约束”，用“左右约束”表示：当尝试在平面中嵌入一条回边路径时，它必须位于某条树边路径的“左侧”或“右侧”，才能避免交叉。
  4. 构造一个“左右约束图”，其中顶点是“面”的占位符（对应 DFS 树中每条树边两侧的两个“半边”），约束是“边必须放在某个面的某一侧”。
  5. 检查这些约束是否相容（即是否可同时满足而不冲突），这等价于检查一个二分性（2-SAT 可满足性问题的一种特殊情形）。

实际上，左-右算法在实现时，可以更直接地用“嵌入冲突检测”来理解，下面我们分步骤详述。

4. 算法详细步骤

步骤 1：DFS 生成树与低点编号

  • 对图做 DFS，记录每个顶点的 dfn[u]（DFS 序号）。
  • 定义 lowpt[u]：在 DFS 树中，从 u 出发通过 0 条或多条树边，再经过最多一条回边，能到达的最小 DFS 序号。这有助于识别回边。

步骤 2：回边与路径分类

  • 在 DFS 中，当遇到边 (u, v) 且 v 已被访问过且不是父亲，则 (u, v) 是回边，v 是 u 的祖先。
  • 这条回边对应 DFS 树上从 v 到 u 的路径（包含树边），我们把它看作一个“段”（segment）。

步骤 3：建立“左右约束”

  • 考虑 DFS 树以根为起点，树边已嵌入平面（可以想象树是自上而下画出的）。
  • 每个回边路径在嵌入时，可以选择附着在它所连接的树路径的“左侧”或“右侧”。
  • 不同回边路径之间的相对顺序（谁在左谁在右）如果冲突，图就是非平面的。

关键观察：
如果两个回边路径在 DFS 树上有“交错”的端点区间（一个路径的端点区间包含另一个路径的某个内点但不完全包含），则它们的左右选择必须一致（都左或都右）才不会交叉，否则必须一左一右。
这种约束可以通过区间包含关系来形式化。

步骤 4：构建约束图并检查

  • 为每个回边路径创建一个变量，表示它嵌入在“左侧”（L）还是“右侧”（R）。
  • 根据路径之间的区间包含关系，产生约束条件。
  • 这些约束可转化为一个二分性检查：约束图（其中变量是结点，约束是边）必须是二分图（2-可着色），即可满足。
  • 如果是二分图，则图是平面图；否则，非平面。

实际实现：
经典的左-右算法在递归处理 DFS 树的孩子子树时，维护一个“可行嵌入顺序”的栈，合并孩子的约束，并实时检查冲突，若冲突则直接返回“非平面”。

5. 示例演示

假设有一个简单图：\(K_{3,3}\) 的某个细分。

  1. 做 DFS，得到生成树。
  2. 找到回边路径。
  3. 分析路径区间：在 \(K_{3,3}\) 中，会有三条路径相互交错，导致任何左右赋值都会冲突。
  4. 约束图出现奇环，不是二分图，因此判定为非平面。

6. 时间复杂度与扩展

  • 左-右算法是线性时间 \(O(|V|)\) 的平面性判定算法。
  • 它比经典的 Hopcroft-Tarjan 平面性测试（1974）在概念上更直观（基于左右约束）。
  • 算法不仅能判断平面性，还能在平面时给出一个组合嵌入（各边在顶点处的循环次序）。

7. 总结

无向图的平面性检测 是一个深刻而优美的问题，左-右算法通过 DFS 树、回边路径和左右约束，将几何嵌入问题转化为图着色问题，高效解决。
核心：

  1. 用 DFS 树将图分解为树边和回边路径。
  2. 将嵌入选择建模为左右变量。
  3. 通过区间包含关系得到约束。
  4. 约束图的二分性等价于平面性。

该算法是理论图论在算法设计中的一个典范，结合了 DFS 生成树、区间分析和二分图判定。

无向图的平面性检测（Left-Right Planarity Test） 好的，我们来详细讲解一个经典的图论算法： 无向图的平面性检测 。这个问题是判断一个给定的无向图能否在平面上绘制，使得任意两条边除了在顶点处外都不相交。我们将重点介绍一种基于深度优先搜索（DFS）生成树和嵌入思想的 左-右平面性测试算法 （Left-Right Planarity Test），它是基于路径添加（path addition）方法的一种高效实现。 1. 问题描述 给定一个 无向连通图 \( G = (V, E) \)（若不连通，则对每个连通分量分别处理），判断 \( G \) 是否是 平面图 。 平面图：可以在平面上画出该图，使得没有两条边在非顶点处交叉。 目标 ：设计一个算法，输入图的顶点和边，输出“是平面图”或“不是平面图”。 2. 算法基础概念准备 在进入算法前，我们需要理解几个关键概念： Kuratowski 定理 ：一个图是非平面图当且仅当它包含 \( K_ 5 \)（5个顶点的完全图）或 \( K_ {3,3} \)（完全二分图，两边各3个顶点）的 细分 （即边上可以插入额外顶点）。 平面图性质 （欧拉公式）：对连通平面图，有 \( V - E + F = 2 \)，其中 \( F \) 是面数。由此可推出 \( E \le 3V - 6 \)（当 \( V \ge 3 \) 且无三角形时，\( E \le 2V - 4 \)）。这可以用来快速排除一些非平面图，但不能判定。 DFS 生成树 ：算法首先对图做一次深度优先搜索，得到一棵生成树。树边（tree edges）形成树结构，回边（back edges）指向祖先。 剩余图 ：去掉树边后，剩下的回边形成一组“剩余边”，每条回边对应 DFS 树中从一个顶点到其祖先的一条路径（在树上的路径）。 路径添加方法 （path addition method）：平面性测试算法（如左-右算法）的核心是，尝试将剩余边对应的路径一条一条嵌入到 DFS 树所在的平面上，并检查是否会引起交叉冲突。 3. 左-右平面性测试算法核心思想 左-右算法（由 H. de Fraysseix, P. Rosenstiehl 等提出）是一种基于 DFS 树和回边路径的平面性判定算法，其时间复杂度为 \( O(|V|) \)。 基本步骤 ： 对图进行深度优先搜索（DFS），得到一棵生成树，并为每个顶点分配 DFS 序号（ dfn ）。 识别出所有的回边（back edge），每条回边对应 DFS 树中从一个顶点到其祖先的一条“返祖路径”。 将这些回边（或它们对应的路径）转化为“约束”，用“左右约束”表示：当尝试在平面中嵌入一条回边路径时，它必须位于某条树边路径的“左侧”或“右侧”，才能避免交叉。 构造一个“左右约束图”，其中顶点是“面”的占位符（对应 DFS 树中每条树边两侧的两个“半边”），约束是“边必须放在某个面的某一侧”。 检查这些约束是否相容（即是否可同时满足而不冲突），这等价于检查一个二分性（2-SAT 可满足性问题的一种特殊情形）。 实际上，左-右算法在实现时，可以更直接地用“嵌入冲突检测”来理解，下面我们分步骤详述。 4. 算法详细步骤 步骤 1：DFS 生成树与低点编号 对图做 DFS，记录每个顶点的 dfn[u] （DFS 序号）。 定义 lowpt[u] ：在 DFS 树中，从 u 出发通过 0 条或多条树边，再经过最多一条回边，能到达的最小 DFS 序号。这有助于识别回边。 步骤 2：回边与路径分类 在 DFS 中，当遇到边 (u, v) 且 v 已被访问过且不是父亲，则 (u, v) 是回边，v 是 u 的祖先。 这条回边对应 DFS 树上从 v 到 u 的路径（包含树边），我们把它看作一个“段”（segment）。 步骤 3：建立“左右约束” 考虑 DFS 树以根为起点，树边已嵌入平面（可以想象树是自上而下画出的）。 每个回边路径在嵌入时，可以选择附着在它所连接的树路径的“左侧”或“右侧”。 不同回边路径之间的相对顺序（谁在左谁在右）如果冲突，图就是非平面的。 关键观察 ： 如果两个回边路径在 DFS 树上有“交错”的端点区间（一个路径的端点区间包含另一个路径的某个内点但不完全包含），则它们的左右选择必须一致（都左或都右）才不会交叉，否则必须一左一右。 这种约束可以通过区间包含关系来形式化。 步骤 4：构建约束图并检查 为每个回边路径创建一个变量，表示它嵌入在“左侧”（L）还是“右侧”（R）。 根据路径之间的区间包含关系，产生约束条件。 这些约束可转化为一个二分性检查：约束图（其中变量是结点，约束是边）必须是二分图（2-可着色），即可满足。 如果是二分图，则图是平面图；否则，非平面。 实际实现 ： 经典的左-右算法在递归处理 DFS 树的孩子子树时，维护一个“可行嵌入顺序”的栈，合并孩子的约束，并实时检查冲突，若冲突则直接返回“非平面”。 5. 示例演示 假设有一个简单图：\( K_ {3,3} \) 的某个细分。 做 DFS，得到生成树。 找到回边路径。 分析路径区间：在 \( K_ {3,3} \) 中，会有三条路径相互交错，导致任何左右赋值都会冲突。 约束图出现奇环，不是二分图，因此判定为非平面。 6. 时间复杂度与扩展 左-右算法是线性时间 \( O(|V|) \) 的平面性判定算法。 它比经典的 Hopcroft-Tarjan 平面性测试（1974）在概念上更直观（基于左右约束）。 算法不仅能判断平面性，还能在平面时给出一个组合嵌入（各边在顶点处的循环次序）。 7. 总结 无向图的平面性检测 是一个深刻而优美的问题，左-右算法通过 DFS 树、回边路径和左右约束，将几何嵌入问题转化为图着色问题，高效解决。 核心 ： 用 DFS 树将图分解为树边和回边路径。 将嵌入选择建模为左右变量。 通过区间包含关系得到约束。 约束图的二分性等价于平面性。 该算法是理论图论在算法设计中的一个典范，结合了 DFS 生成树、区间分析和二分图判定。