xxx 无向图的平面性检测（Left-Right Planarity Test） 题目描述 给定一个无向图 G=(V, E)，判断它是否是平面图。平面图是指可以画在平面上，并且任意两条边都只在顶点处相交的图。本题目要求理解并实现一个经典的平面性检测算法——Left-Right Planarity Test（左右平面性测试），该算法基于深度优先搜索（DFS）生成树和回溯路径（lowpoint）的概念，并利用“左右约束”来高效判断平面性。 ** 解题过程**** 1. 基本概念与背景 平面图判定是图论中的一个经典问题。一个图是平面图当且仅当它不包含K5（5个顶点的完全图）或K3,3（完全二分图，两边各有3个顶点）的细分（subdivision）作为子图（Kuratowski定理）。但直接检测这些子图是困难的。Left-Right Planarity Test 是一种基于DFS的线性时间算法（O(|V|)），由Shih和Hsu在1990年代提出，它结合了DFS树、回溯边（back edge）的方向性以及“左右”约束条件。 2. 算法核心思想 算法的主要步骤： 对图进行深度优先搜索（DFS），生成一棵DFS树。在DFS过程中，为每条边分配一个方向：树边（tree edge）和回溯边（back edge，即连接当前顶点与DFS树中祖先的边）。 回溯边会形成“环”结构。平面图要求这些环在嵌入时不能交叉。算法的核心是检查这些环能否被“左右”分配到两个不同的面（face）中而不冲突。 3. 详细步骤 步骤1：执行DFS，计算每个顶点的DFS编号和低点（lowpoint） 从任意顶点开始DFS，为每个顶点v记录其DFS编号dfn[ v ]（即访问顺序）。 同时计算每个顶点v的“低点”low[ v ]：在DFS树中，从v出发通过0条或更多条树边，然后通过至多一条回溯边能达到的最小DFS编号。这帮助识别环结构。 步骤2：构建“约束图” 在DFS树中，每条回溯边(u, v)（假设dfn[ u] > dfn[ v ]，即u是后代，v是祖先）会与DFS路径上从v到u的树边形成一个环。 考虑两条回溯边e1和e2。它们可能“冲突”，即如果它们的环在嵌入时必须交叉，则图是非平面的。算法通过构建一个二分约束图来建模这些冲突：每个约束图顶点对应一条回溯边，如果两条回溯边冲突，则在它们之间连一条边，表示它们必须被分配到不同的“左右”面。 步骤3：左右分配与检查 约束图是一个二分图检测问题：如果约束图是二分图，则可以将回溯边分配到“左”或“右”面，从而图是平面图；否则为非平面图。 具体地，算法在DFS过程中动态维护一个“左右”数据结构，对于每条回溯边，记录它必须相对于其他回溯边位于左侧还是右侧。这可以通过并查集（union-find）或类似结构高效实现，以合并约束条件。 步骤4：递归处理双连通分量 平面性检测可以简化为对每个双连通分量（biconnected component）独立检测。因为图是平面图当且仅当所有双连通分量都是平面图。 在DFS过程中，当遇到割点（articulation point）时，递归检测每个双连通分量的平面性。如果所有分量都是平面图，则原图是平面图。 5. 算法复杂度 算法在O(|V| + |E|)时间内运行，即线性时间。这是因为DFS是线性的，约束图的大小是O(|E|)，而二分图检测（通过BFS/DFS）也是线性的。 6. 示例演示 考虑一个小图：顶点集{1,2,3,4}，边集{(1,2), (2,3), (3,4), (4,1), (1,3)}（即一个四边形加一条对角线）。 DFS从顶点1开始，生成树边：1-2, 2-3, 3-4。回溯边：4-1和3-1。 回溯边(4,1)形成环1-2-3-4-1，(3,1)形成环1-2-3-1。这两个环在平面嵌入中必须交叉（因为边(1,3)会穿过四边形内部），因此约束图指示冲突，检测为非二分图，所以原图是非平面的（实际上它包含K3,3的细分）。 总结 Left-Right Planarity Test 是一个高效的平面性检测算法，它避免了显式寻找Kuratowski子图，而是通过DFS和约束图二分性来判定。掌握这个算法需要理解DFS树、低点、回溯边和平面嵌入的基本性质。