企业官网建设流程全解析

OI Wiki 平面图：如何判定平面性并求对偶图

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

给定一张图，你需要回答两件事：它能不能画到平面上使边互不相交（即是否为可平面图）；如果给出一个具体的平面嵌入，如何在这个嵌入上构造对偶图，并用对偶图求解诸如最小割的问题。本文的操作路径来自 OI-wiki 文档 docs/graph/planar.md，适用于图论学习、算法竞赛备赛以及需要在平面图上建立对偶结构的开发场景。整条路径是：先用边数上界做快速排除，再用禁用图条件或现成库算法给出判定结论；确认可平面后，按文档给出的两步流程构造对偶图，最后用文档中的性质核对构造结果。

判定平面性：先做边数检查，再看禁用结构

用边数上界快速排除非平面图

对可平面图，欧拉公式 给出顶点数 $|V|$、边数 $|E|$、面数 $|F|$ 之间的关系：连通平面图满足 $|V| - |E| + |F| = 2$，有 $k$ 个连通分支的平面图满足 $|V| - |E| + |F| = k + 1$。

由此可推出判定用的必要条件：设有 $k$ 个连通分支、且每个面次数都至少为 $l \ge 3$ 的平面图 $G$，则

$$ |E| \le \dfrac{l}{l-2}(|V|-k-1). $$

对最常见的情况——简单可平面图且 $|V| \ge 3$——取 $k=1$、$l=3$，得到实践中最好用的判据：

$$ |E| \le 3|V|-6. $$

使用方法：先数出图的顶点数与边数。如果 $|V| \ge 3$ 且 $|E| > 3|V|-6$，可以立即断定该图不是可平面图，不需要继续做任何事情。文档中用同一思路证明了两个经典反例：

• $K_5$：$l=3$、$|V|=5$、$|E|=10$，而 $3|V|-6 = 9$，边数超限，不可平面；
• $K_{3,3}$：$l=4$、$|V|=6$、$|E|=9$，而 $\frac{4}{4-2}(|V|-2) = 8$，边数超限，不可平面。

注意这是一个必要条件：满足不等式只能说明"可能是可平面图"，不满足才能直接下"不可平面"的结论。

用禁用图条件给出充要判定

边数上界只是排除工具，充要刻画由禁用图给出：

• Kuratowski 定理：图 $G$ 是可平面图，当且仅当 $G$ 不含与 $K_5$ 或 $K_{3,3}$同胚的子图。同胚指两图同构，或通过反复插入或消去 2 度顶点后同构。
• Wagner 定理：图 $G$ 是可平面图，当且仅当 $G$ 中没有可以收缩到 $K_5$ 或 $K_{3,3}$ 的子图（收缩指重复将一条边收缩为一个点）。

对于小图，判定操作路径就是在这两张图上搜索同胚于 $K_5$ 或 $K_{3,3}$ 的子图：找不到则图可平面，找到则不可平面。由于同胚到 $K_5$/$K_{3,3}$ 的子图一定能收缩到它们，反之不然，Kuratowski 条件比 Wagner 条件更容易人工检验。

左：$K_5$；右：$K_{3,3}$，两者都是不可平面图，也是使图不可平面的最小结构。

程序化判定：使用现成库的线性算法

如果图规模大、需要程序判定，文档指出现有线性时间平面性判定算法的实现通常都比较复杂、几乎不出现在算法竞赛中，实际工程上直接使用已实现这些算法的库即可：

• Python 的 NetworkX 库：实现了 de Fraysseix–Ossona de Mendez–Rosenstiehl 算法（LR 平面性算法），该算法改进了 Hopcroft–Tarjan 算法的流程，是目前最优秀的平面性判定算法之一，源码位于networkx/algorithms/planarity.py。
• C++ 的 Boost 库：实现了 Boyer–Myrvold 算法。它在线性时间内判定给定图是否可平面；若图可平面，算法输出一个平面嵌入；若不可平面，算法输出一个 Kuratowski 子图（与 $K_5$ 或 $K_{3,3}$ 同胚的子图）。

文档没有给出具体 API 调用代码，只说明上述库完成了实现，使用时以对应库自身的接口文档为准。选型建议：需要同时拿到"平面嵌入"或"反例子图"作为后续构造对偶图的输入时，Boyer–Myrvold 的实现（Boost）提供的信息更完整。

构造对偶图：两步流程与结果核对

前提：对偶图只对具体的平面嵌入（平面图）定义，不能定义在任意的可平面图上。同一个图的不同平面嵌入，其对偶图可能并不同构——文档举了两个同构平面图的例子，右图含一次面，其对偶图有一度顶点，而左图的对偶图没有。所以执行本节前，必须先选定（或从判定算法输出中取得）一个具体的平面嵌入。

设 $G$ 是平面图，对偶图 $G^*$ 的绘制流程如下：

1. 在 $G$ 的每个面 $f_i$ 内部都绘制一个点 $v_i^*$；
2. 对 $G$ 的每条边 $e$，如果 $e$ 在面 $f_i$ 和 $f_j$ 的公共边界上，就绘制一条连接 $v_i^$ 和 $v_j^$ 的边 $e^$，使之与 $e$ 恰相交一次，且不与其他图 $G$ 或图 $G^$ 的边相交；特别地，当 $e$ 只出现在一个面 $f_i$ 的边界上（割边）时，需要绘制一条与 $v_i^*$ 关联的自环，使之与 $e$ 相交。

构造结果的核对方式（均出自文档定理）：

• 构造出的 $G^*$ 必须是连通的平面图——这是构造正确性的直接检查项；
• 当且仅当 $G$ 是连通图时，$G^{**}$（$G^*$ 的对偶图）与 $G$ 同构。对连通图可以做"双重对偶"验证；
• 结构对应关系必须逐条成立：$G$ 的面对应 $G^$ 的点，$G$ 的边对应 $G^$ 的边，$G$ 的点对应 $G^$ 的面；$G$ 中的自环对应 $G^$ 中的割边，反之亦然；$G$ 中的边割集对应 $G^*$ 中的回路，反之亦然。

同时记住面的基本计数：每条割边在面的次数中算两次，因此平面图中所有面的次数之和等于 $2|E|$；顶点数 $|V| \ge 3$ 的简单连通平面图中，所有面次数都至少为 3。

典型应用：把平面图最小割转化为对偶图最短路

对偶图的实际价值在于把可平面图上的割问题转化到对偶图上的最短路问题（相关文档见 最小割 与 最短路）。设 $G$ 是带边权的可平面图，$s, t$ 是它的两个顶点，需求最小 $s$-$t$ 割，转化流程如下：

1. 选取合适的平面嵌入，使 $s, t$ 都出现在外部面边界上；
2. 添加自 $s$ 和 $t$ 延伸出去的射线，将外部面分为 $f_+$ 和 $f_-$ 两部分；
3. 基于该图建立对偶图，并把边权赋给对偶图中的对应边；
4. 对偶图 $G^*$ 中面 $f_+$ 与 $f_-$ 所对应顶点之间的最短路径，与图 $G$ 的 $s$-$t$ 边割集一一对应，且二者权值相同。

执行前必须先验证适用条件：转化只适用于存在 $G$ 的平面嵌入使 $s, t$ 共面的情形。文档给出的判定定理是：

对于可平面图 $G=(V,E)$ 的两个顶点 $s,t$，存在 $G$ 的平面嵌入使得 $s,t$ 处于同一个面上，当且仅当 $(V, E \cup {(s,t)})$ 是可平面图。

也就是说，把边 $(s,t)$ 加进图里，再跑一次平面性判定（上一节的边数检查、禁用图检查或库算法均可）：判定通过才执行转化；判定不通过则转化不适用。文档的反例是：某图中添加边 $(s,t)$ 后得到 $K_5$，故不存在这样的平面嵌入。常见误区是据上述转化宣称"平面图最小割等于对偶图最短路"，事实上它只在 $s, t$ 可共面的嵌入存在时才成立——竞赛题目中给出的图往往附带满足该条件的平面嵌入，但不能默认一般情形成立。

限制与边界

• 对偶图概念仅对具体的平面图（选定嵌入后可平面图）成立；两个同构的平面图的对偶图未必同构，求对偶图前必须先固定嵌入。
• 线性时间平面性判定算法实现复杂，竞赛中通常直接使用题目给定的平面嵌入；库算法（NetworkX / Boost）适合离线判定和嵌入提取。
• 与本文任务直接相关的延伸结果是外平面图判定：$G$ 是外平面图当且仅当 $G$ 不含与 $K_4$ 或 $K_{2,3}$ 同胚的子图，判定方式与 Kuratowski 条件相同，只是禁用图不同。
• 文档给出的练习题方向包括平面图判定与平面图上割/最短路转化的题目（如 HNOI2010 平面图判定、WC2013 平面图、ICPC-Beijing 2006 狼抓兔子），可作为上述判定与对偶转化流程的检验材料。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki