OI-wiki 平面图Planar Graph完全指南从欧拉公式、对偶图到平面性判定算法【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文是 OI-wiki 图论模块中 平面图 一文的完整展开。平面图planar graph是图论与算法竞赛中一类结构优美、应用广泛的图从欧拉公式 $|V|-|E||F|2$ 到平面图最小割化为对偶图最短路这一经典技巧再到 Kuratowski / Wagner 禁用图刻画与线性时间的平面性判定算法本文将系统梳理这些概念、定理及其证明并结合本仓库图论模块的相关文档图论基础概念、最小割、最短路 等说明其在解题实战中的落地方式。读完本文你将能够准确区分可平面图与平面图、熟练运用欧拉公式推导边数上界、构造平面图的对偶图并完成最小割到最短路的转化同时了解平面性判定的理论与算法脉络。平面图的基本概念如果图 $G$ 能画在平面 $S$ 上即除顶点处外无边相交则称 $G$ 可嵌入平面 $S$$G$ 为可平面图planar graph。画出的没有边相交的图称为 $G$ 的平面表示或平面嵌入planar embedding。可平面图的这个平面嵌入也称为平面图plane graph。[!info] 「平面图」的术语辨析 不同中文文本中「平面图」的含义可能不同。在本文的定义中可平面图是一个图论对象它可能以不同的方式嵌入平面中平面图则是一个几何对象除了图论结构外它还需要指定图的绘制方式。同一个可平面图往往对应着多个平面图。因此如果结论只依赖于图论结构就使用「可平面图」一词如果还依赖于图的平面嵌入方式就使用「平面图」一词。以下是平面图的简单例子左蝴蝶图右$4$ 阶完全图 $K_4$以下是不可平面图的简单例子左$5$ 阶完全图 $K_5$右两部分各 $3$ 个顶点的完全二分图 $K_{3,3}$在 OI-wiki 的图论基础概念一节中平面图也被简要定义为可以画在一个平面上且没有两条边在非端点处相交的图并直接给出了两个重要结论简单连通平面图满足 $|E|\le 3|V|-6$以及 Kuratowski 定理。本文将对这两条结论给出完整的推导与证明。平面图的性质面及其次数设 $G$ 是平面图由 $G$ 的边将 $G$ 所在的平面划分成若干个区域每个区域称为 $G$ 的一个面face。其中无界的面称为无限面unbounded face或外部面external face有界的称为有限面或内部面。每一个平面图有且仅有一个外部面。包围每个面的所有边组成的回路称为该面的边界boundary并称边界中的边与该面关联incident。边界的长度称为该面的次数degree。计算面的次数时每条割边都算作两次。由此可以得到平面图中所有面的次数之和等于边数 $|E|$ 的 $2$ 倍。平面图中$1$ 次面的边界对应于图的自环$2$ 次面的边界通常对应于图的一对重边但这并非唯一的可能——两个嵌套的自环也会形成二次面另外有二次面未必意味着图不是简单的例如一个只有一条边的图中唯一的面即外部面也是二次的。顶点数 $|V|\ge 3$ 的简单连通平面图中所有面次数都至少为 $3$。欧拉公式平面图的一个重要性质是欧拉公式Eulers formula它给出了图的顶点数 $|V|$、边数 $|E|$ 和面数 $|F|$ 之间的关系。[!note] 欧拉公式 对于连通的平面图 $G$有 $$ |V| - |E| |F| 2. $$证明对面数 $|F|$ 应用数学归纳法。归纳起点是 $|F|1$。此时平面图有且只有一个外部面全部边都是割边所以图 $G$ 是一棵树必然有 $|E||V|-1$代入欧拉公式即可发现它成立。假设欧拉公式对于面数 $|F|k$ 的平面图成立。对于面数 $|F|k1$ 的平面图 $G$必然存在非割边 $e$它是两个不同的面的公共边。将边 $e$ 从图中删除得到图 $G-e$它有 $|V|$ 个顶点、$|E|-1$ 条边和 $|F|-1$ 个面。由归纳假设对图 $G-e$ 成立欧拉公式即 $|V|-(|E|-1)(|F|-1)2$整理即得关于图 $G$ 的欧拉公式。根据数学归纳法欧拉公式对所有平面图都成立。$\blacksquare$[!note] 推论多连通分支情形 对于有 $k$ 个连通分支的平面图 $G$有 $$ |V| - |E| |F| k 1. $$证明图 $G$ 的每个连通分支都是平面图但这些连通分支共用同一个外部面。直接对这些连通分支应用欧拉公式并累加总顶点数和总边数都是正确的但总面数多了 $k-1$因为唯一的外部面总共计数了 $k$ 次。将这一修正考虑在内就得到 $|V|-|E||F| 2k - (k-1) k1$。$\blacksquare$由此可以推出平面图的边与顶点的数量关系。[!note] 定理面次数下界导出边数上界 对于有 $k$ 个连通分支的平面图 $G$如果图 $G$ 的每个面次数都至少为 $l \ge 3$那么有 $$ |E| \le \dfrac{l}{l-2}(|V|-k-1). $$证明因为 $G$ 的各面次数至少为 $l$所以所有面的次数和至少为 $l|F|$亦即 $2|E| \ge l|F|$。代入欧拉公式的推论 $|V|-|E||F|k1$得到 $2|E| \ge l(k1-|V||E|)$。利用 $l\ge 2$ 解出 $|E|$即得 $|E| \le \dfrac{l}{l-2}(|V|-k-1)$。$\blacksquare$[!note] 推论稀疏性 设 $G$ 是简单可平面图且 $|V|\ge 3$那么有 $$ |E| \le 3|V|-6. $$证明当 $G$ 连通时所有面次数都至少是 $3$在上述定理中取 $k1$ 且 $l3$即得 $|E|\le 3|V|-6$。当 $G$ 不连通时分为两种情形如果存在连通分支顶点数至少是 $3$那么对这些连通分支可分别建立 $|E_i|\le 3|V_i|-6$顶点数小于 $3$ 的连通分支一定有 $|E_i|\le |V_i|\le 3|V_i|$。将所有不等式相加就得到 $|E|\le 3|V|-6$。如果所有连通分支顶点数都小于 $3$那么整体有 $|E|\le |V|$又因为 $|V|\ge 3$ 时 $|V|\le 3|V|-6$所以结论仍成立。$\blacksquare$这一推论说明简单可平面图是稀疏图——这也是很多平面图算法可以做到线性复杂度的结构性原因后面介绍的线性平面性判定算法正是建立在这一稀疏性之上。对偶图平面图都有相应的几何对偶图dual graph这也是平面图理论中最重要的工具之一。设 $G$ 是平面图可以按下述步骤绘制图 $G^*$在 $G$ 的每个面 $f_i$ 内部都绘制一个点 $v_i^*$对 $G$ 的每条边 $e$如果 $e$ 在面 $f_i$ 和 $f_j$ 的公共边界上就绘制一条连接 $v_i^$ 和 $v_j^$ 的边 $e^$使之与 $e$ 恰相交一次且不与其他图 $G$ 或图 $G^$ 的边相交。特别地当 $e$ 只出现在一个面 $f_i$ 的边界上时需要绘制一条与 $v_i^*$ 关联的自环使之与 $e$ 相交。这样得到的图 $G^*$ 就称作图 $G$ 的对偶图。[!note] 定理 设图 $G^$ 是平面图 $G$ 的对偶图。那么图 $G^$ 是连通的平面图。而且图 $G^{**}$ 与 $G$ 同构当且仅当 $G$ 是连通图。证明图 $G^$ 的平面性由构造过程保证。连通性方面对图 $G^$ 中任意两个顶点 $v_i^,v_j^$设平面中连接它们的直线段经过图 $G$ 的面和边依次为 $f_i,e_{s_1},f_{s_1},\cdots,f_{s_{r-1}},e_{s_r},f_j$它们分别对应对偶图中的顶点和边 $v_i^,e_{s_1}^,v_{s_1}^,\cdots,v_{s_{r-1}}^,e_{s_r}^,v_j^$。由构造可知序列中相邻的顶点和边是相关联的因此这描述了图 $G^$ 中的一条途径所以 $G^$ 连通。由于 $G^{}$ 是 $G^*$ 的对偶图必然连通所以 $G$ 与 $G^{}$ 同构的必要条件是 $G$ 连通。为证明充分性只需证明当 $G$ 连通时$G$ 满足 $G^$ 的对偶图的构造要求。因为 $G^$ 的边与 $G$ 的边天然对应只需证明 $G^$ 的每一个面都恰好包含 $G$ 的一个顶点。对 $G^$ 的任一个面 $f^$设 $e^$ 是其边界上的一条边那么 $G$ 中对应的边 $e$ 的端点之一必然在面 $f^$ 之内故面 $f^$ 中至少存在 $G$ 的一个顶点。由于 $G^$ 和 $G$ 都连通欧拉公式成立而 $G$ 与 $G^$ 边数相同、$G$ 的面数等于 $G^$ 的顶点数所以 $G$ 的顶点数等于 $G^$ 的面数。于是 $G^*$ 的每个面恰好只有 $G$ 的一个顶点。$\blacksquare$平面图与其对偶图的结构之间有很多对应关系这些对应关系是对偶化解题思路的理论基础$G$ 中的面对应 $G^$ 中的点$G$ 中的边对应 $G^$ 中的边$G$ 中的点对应 $G^*$ 中的面$G$ 中的自环对应 $G^$ 中的割边$G^$ 中的自环对应 $G$ 中的割边$G$ 中的边割集对应 $G^$ 中的回路$G^$ 中的回路对应 $G$ 中的边割集。需要注意的是对偶图的概念仅对具体的平面图成立无法定义在任意可平面图上。事实上两个同构的平面图的对偶图未必是同构的——同一个图的不同平面嵌入的对偶图可能并不相同。[!example] 例子 下图画了两个同构的平面图它们的对偶图并不同构。对偶图不同构的原因是右图有一次面它的对偶图有一度顶点而左图没有。在 OI-wiki 的计算几何模块中对偶图思想也有直接体现文档 Delaunay 三角剖分 指出Voronoi 图是 Delaunay 三角剖分的对偶图可以用构造 Delaunay 三角剖分的分治算法求出三角网再用最左转线算法求出其对偶图从而在 $O(n\log n)$ 时间内构造 Voronoi 图。这说明面与点互换的对偶构造在计算几何与图论中是通用的核心思想。实战转化平面图最小割 → 对偶图最短路将可平面图的问题转化到对偶图上有时更容易解决。一个典型的例子是可平面图最小割问题可以转化为对偶图最短路问题。设 $G$ 是带边权的可平面图$s,t$ 是它的两个顶点需要求最小的 $s$-$t$ 割。具体做法是选取合适的平面嵌入使 $s,t$ 出现在图 $G$ 外部面边界上添加自 $s$ 和 $t$ 延伸出去的射线将外部面分为两部分 $f_{}$ 和 $f_{-}$基于该图建立对偶图并将边权赋给对偶图中的对应边。那么对偶图 $G^*$ 中面 $f_{}$ 和 $f_{-}$ 对应顶点之间的路径红色粗线就和图 $G$ 的 $s$-$t$ 边割集黑色粗线一一对应且二者权值相同。这样求解对偶图中的最短路就得到了图 $G$ 中的最小 $s$-$t$ 割。一个常见的误区是根据上述转化方法宣称平面图最小割等于对偶图最短路。事实上它只适用于存在 $G$ 的平面嵌入使得 $s,t$ 共面的情况只是在考察此知识点的算法竞赛题目中给出的图往往具有并且附带这样的平面嵌入。下面给出一个可以用于判定该条件存在性的定理。[!note] 定理 对于可平面图 $G(V,E)$ 的两个顶点 $s,t$存在 $G$ 的平面嵌入使得 $s,t$ 处于同一个面上当且仅当 $(V,E\cup{(s,t)})$ 是可平面图。证明如果存在 $G$ 的平面嵌入使得 $s,t$ 处于同一个面上那么就可以在这个面内添加一条边 $(s,t)$保持图的平面性。反之如果 $(V,E\cup{(s,t)})$ 是可平面图那么任取它的一个平面嵌入$s,t$ 都同处边 $(s,t)$ 所处的面删除 $(s,t)$ 之后$s,t$ 仍然同处一面。$\blacksquare$例如下图展示的情形中添加边 $(s,t)$ 之后得到非平面图 $K_5$故而不存在使 $s,t$ 共面的平面嵌入上述转化不适用。关于最小割问题本身的建模与求解如最大流最小割定理、Dinic 实现、最小割方案输出、割边数量最小化、二者选其一与最大权闭合图等经典模型可进一步参考 OI-wiki 的 最小割文档 及其配套参考代码docs/graph/code/flow/下的实现。更多著名结果平面图还有很多著名的结果本节仅作列举不展开讨论[!note] 四色定理 没有自环的平面图都是可 $4$-着色的。[!note] Fáry 定理 简单可平面图总是存在一种平面嵌入使得图的所有边都是直线段。[!note] 定理Wood 可平面图至多只有 $8|V|-16$ 个极大团。[!note] 定理Tutte $4$-点连通的可平面图都是哈密顿图。可平面性判定给定一个图如何判定它是不是可平面图本节介绍理论基础与实用算法。禁用图刻画可平面图最经典的刻画方式是利用禁用图forbidden graph给出的。首先$K_5$ 和 $K_{3,3}$ 不是可平面图。[!note] 定理 $K_5$ 和 $K_{3,3}$ 不是可平面图。证明前文已说明$|V|\ge 3$ 的简单连通平面图都需要满足 $|E| \le \dfrac{l}{l-2}(|V|-2)$其中 $l$ 是面次数的最小值。对于 $K_5$有 $l3,\ |V|5,\ |E|10$代入得 $10 \le \frac{3}{1}\cdot 3 9$ 不成立所以 $K_5$ 不可能画成平面图。对于 $K_{3,3}$有 $l4,\ |V|6,\ |E|9$代入得 $9 \le \frac{4}{2}\cdot 4 8$ 不成立所以 $K_{3,3}$ 不可能画成平面图。$\blacksquare$事实上它们就是使得一个图不可平面的最小结构只要图不以某种方式包含这两个图为子结构该图就一定是可平面的。第一个可平面性判定定理是Kuratowski 定理它用到了图同胚的概念若两个图 $G_1$ 与 $G_2$ 同构或通过反复插入或消去 $2$ 度顶点后是同构的则称二者是同胚的homeomorphic。[!note] Kuratowski 定理 图 $G$ 是可平面图当且仅当 $G$ 不含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。与此相关的另一个定理是Wagner 定理它利用收缩操作刻画可平面图收缩操作是指重复多次将图的一条边收缩为一个点。[!note] Wagner 定理 图 $G$ 是可平面图当且仅当 $G$ 中没有可以收缩到 $K_5$ 或 $K_{3,3}$ 的子图。可平面图不包含这些类型的子图相对显然所以这两个定理的关键部分都在于相应禁用图条件的充分性。由于与 $K_5$ 或 $K_{3,3}$ 同胚的子图一定可以收缩到它们反过来却未必成立所以Kuratowski 定理提供了一个更弱也更容易检验的判定条件。OI-wiki 的图论基础概念一节也以不存在与 $K_5$ 或 $K_{3,3}$ 同胚的子图的形式引用了 Kuratowski 定理两处表述一致。平面性判定算法尽管看起来并不容易平面性判定问题实际上有很多线性时间算法。但由于这些算法的实现通常都比较复杂它们几乎从未出现在算法竞赛中更多出现在算法工程与图算法库的实现层面。Hopcroft–Tarjan 算法最早的线性时间平面性判定算法但其实现相当复杂。de Fraysseix–Ossona de Mendez–Rosenstiehl 算法也称LR 平面性算法进一步改进了 Hopcroft–Tarjan 算法的流程是目前最优秀的平面性判定算法之一。Python 的 NetworkX 库中就实现了这一算法networkx/algorithms/planarity.py。Boyer–Myrvold 算法同样优秀的线性时间算法。它可以在线性时间内判定给定图是否可平面而且如果图是可平面的算法将输出一个平面嵌入否则算法将输出一个 Kuratowski 子图即与 $K_5$ 或 $K_{3,3}$ 同胚的子图。C 的 Boost 库实现了这一算法boost/graph/planar_detail/boyer_myrvold_impl.hpp。更多相关算法可参考文末提供的文献。特殊的平面图极大平面图平面三角剖分对于简单可平面图 $G$如果在它的任意不相邻顶点间添加边所得图都不再是可平面图就称 $G$ 为极大可平面图maximal planar graph。极大可平面图的平面嵌入称为极大平面图。[!note] 定理 极大可平面图 $G$ 必然连通。而且当顶点数 $|V|\ge 3$ 时图 $G$ 没有割边。证明如果可平面图 $G$ 不连通任选它的一个平面嵌入都可以选择属于不同连通分支的两个顶点在外部面内连接起来所得图显然仍是平面图这与 $G$ 的极大性矛盾所以极大可平面图必连通。若 $|V|\ge 3$ 且 $G$ 有割边 $e(u,v)$则删去 $e$ 后 $G-e$ 恰有两个连通分支$u,v$ 分属不同分支。假设 $v$ 所在分支至少有两个顶点可先将 $u$ 所在分支 $G_1$ 画在平面上选取 $G_1$ 中边界含 $u$ 的任意面 $f$将另一分支 $G_2$ 画在面 $f$ 中。由于 $G_2$ 是简单图其外部面边界不是自环故至少存在另一个顶点 $w\neq u,v$。将 $v,w$ 分别连接到 $u$ 上就得到包含 $G$ 为子图的平面图与极大性矛盾。因此 $|V|\ge 3$ 的极大可平面图一定没有割边。$\blacksquare$极大平面图的结构可以更准确地描述。[!note] 定理 对于顶点数 $|V|\ge 3$ 的平面图 $G$它是极大平面图当且仅当它是简单图且它的每个面次数均为 $3$。证明充分性显然。必要性设极大平面图 $G$ 的某个面 $f$ 的边界长度至少是 $4$。由于 $G$ 无割边该边界只能是一个环 $v_1v_2v_3v_4\cdots v_1$。若 $v_1$ 与 $v_3$ 不相邻则在面 $f$ 内连接 $v_1$ 和 $v_3$ 不会破坏平面性与极大性矛盾所以 $v_1$ 与 $v_3$ 相邻同理 $v_2$ 与 $v_4$ 相邻。但边 $(v_1,v_3)$ 和 $(v_2,v_4)$ 都不会出现在面 $f$ 中即两条边必然在面 $f$ 的外部而无论如何绘制这两条边都必然相交矛盾。所以极大平面图中不存在高于 $3$ 次的面。$\blacksquare$[!note] 推论 对于顶点数 $|V|\ge 3$ 的极大平面图 $G$总有边数 $|E|3|V|-6$ 且面数 $|F|2|V|-4$。由于极大平面图中每个面都是由三条边围成极大平面图也称为平面三角剖分plane triangulation。这一概念与计算几何中的三角剖分参见 OI-wiki 的 三角剖分文档在结构上一脉相承。外平面图设 $G$ 为可平面图若 $G$ 存在平面嵌入 $\tilde{G}$使得 $G$ 中所有顶点都在 $\tilde{G}$ 的一个面的边界上则称 $G$ 为外可平面图outerplanar graph。这一嵌入也称为外平面嵌入或外平面图。通常将边界经过所有顶点的那个面绘制为外部面。外可平面图都是可平面图反之未必成立。外可平面图同样可以使用禁用图刻画[!note] 定理 一个图 $G$ 是外平面图当且仅当 $G$ 中不含与 $K_4$ 或 $K_{2,3}$ 同胚的子图。对于外可平面图同样可以讨论极大外可平面图的概念对于简单外可平面图 $G$如果在它的任意不相邻顶点间添加边所得图都不再是外可平面图就称 $G$ 为极大外可平面图maximal outerplanar graph其外平面嵌入称为极大外平面图。直观上看极大外平面图其实就是平面上多边形的三角剖分。[!note] 定理 对于顶点数 $|V|\ge 3$ 的极大外平面图 $G$且所有顶点都在外部面的边界上那么图 $G$ 恰有 $|V|-2$ 个内部面。证明对 $|V|$ 应用数学归纳法。归纳起点 $|V|3$ 时$G$ 是三元环只有 $1$ 个内部面命题成立。假设命题对 $|V|k$ 成立考虑 $|V|k1$ 的情形。首先证明图 $G$ 一定存在 $2$ 度顶点。反设不然将外部面边界上的顶点顺次编号对每个 $i1,2,\cdots,k1$定义 $f(i)$ 为与顶点 $i$ 连接且编号不与之相邻的顶点的最小编号。首先 $1f(1)$。由于点 $1$ 已经与 $f(1)$ 连接点 $2$ 与 $f(2)$ 的连线不能越过边 $(1,f(1))$就必然有 $12f(2)f(1)$。同理 $23f(3)f(2)$。由于顶点只有有限多个这个逐渐缩小的过程必然在有限步后终止。令 $i^$ 为满足 $1\cdotsi-1if(i)f(i-1)\cdotsf(1)$ 的编号 $i$ 的最大值那么由于点 $i^$ 和点 $f(i^)$ 不相邻必然有 $i^i^1f(i^)$而重复之前的论述仍应有 $i^i^1f(i^1)f(i^)$这与 $i^*$ 的最大性矛盾。故 $G$ 必然存在 $2$ 度顶点。设 $v$ 是一个 $2$ 度顶点删除 $v$ 得到顶点数为 $k$ 的外平面图 $G-v$它必然是极大外平面图否则在其上合法添加边的方法对 $G$ 也适用。由归纳假设$G-v$ 恰有 $k-2$ 个内部面而删去 $v$ 恰好减少了一个 $G$ 的内部面所以 $G$ 的内部面数目为 $k-1$。$\blacksquare$[!note] 定理 对于顶点数 $|V|\ge 3$ 的外平面图 $G$且所有顶点都在外部面的边界上那么 $G$ 是极大外平面图当且仅当 $G$ 的外部面边界是长为 $|V|$ 的环且所有内部面边界均是长为 $3$ 的环。证明充分性显然——连接外部面边界上的两个不相邻顶点若连接发生在外部面中则所有顶点无法都出现在一个面的边界上否则连线必然与内部面的边界相交。必要性假设外部面边界 $v_1v_2v_3\cdots v_nv_1\ (n|V|)$ 不是环则存在 $i\neq j$ 且 $i-j\neq\pm 1\pmod{n}$ 使得 $v_iv_j$。不妨设 $1ijn$。此时与 $v_{i-1}$ 相关联的边只能出现在回路 $v_jv_{j1}\cdots v_nv_1\cdots v_{i-1}v_i$ 围成的有界区域内部与 $v_{i1}$ 相关联的边只能出现在回路 $v_iv_{i1}\cdots v_{j-1}v_j$ 围成的有界区域内部所以 $v_{i-1}$ 和 $v_{i1}$ 无法相邻。可以在外部面内添加连接 $v_{i-1}$ 和 $v_{i1}$ 的边 $e$所得 $Ge$ 显然仍是平面图且外部面边界包含所有顶点这与极大外平面性矛盾。所以外部面必是长度为 $|V|$ 的环内部面边界均为长为 $3$ 的环的原因与极大平面图一致。$\blacksquare$[!note] 推论 对于顶点数 $|V|\ge 3$ 的极大外平面图 $G$有$|E|2|V|-3$$G$ 中至少有 $3$ 个顶点度数小于等于 $3$且至少有 $2$ 个顶点度数为 $2$$G$ 的点连通度为 $2$。仓库内的知识脉络本仓库图论模块围绕平面图展开的知识体系相当完整可将本文与以下文档对照阅读形成闭环图论基础概念平面图的最简定义、$|E|\le 3|V|-6$ 边数上界与 Kuratowski 定理的速查条目最小割最小割的定义、最大流最小割定理、Dinic 参考代码对应文件位于docs/graph/code/flow/以及二者选其一最大权闭合图等经典建模是平面图对偶化转化的求解端最短路对偶图最短路转化中的求解目标三角剖分Delaunay 三角剖分与 Voronoi 图互为对偶图的应用实例插头 DP其中提到当 $n,m\le 100$ 时可用 FKT 算法计算平面图的完美匹配数可见平面性在更广泛算法问题中的价值。习题以下为与本主题配套的经典练习题目名称整理自原文档可在各 OJ 上检索Luogu P3209 [HNOI2010] 平面图判定Luogu P3249 [HNOI2016] 矿区Luogu P4001 [ICPC-Beijing 2006] 狼抓兔子经典的平面图最小割转对偶图最短路模板题Luogu P4073 [WC2013] 平面图Luogu P7295 [USACO21JAN] Paint by Letters P参考资料Planar graph / Planarity testingWikipedia 相关词条Bondy, John Adrian, and Uppaluri Siva Ramachandra Murty.Graph Theory with Applications. Vol. 290. London: Macmillan, 1976.Diestel, Reinhard.Graph Theory. Vol. 173. Springer Nature, 2025.Patrignani, Maurizio. Planarity Testing and Embedding. (2013): 1-42.Hopcroft, John, and Robert Tarjan. Efficient planarity testing.Journal of the ACM (JACM)21, no. 4 (1974): 549-568.De Fraysseix, Hubert, Patrice Ossona De Mendez, and Pierre Rosenstiehl. Trémaux trees and planarity.International Journal of Foundations of Computer Science17, no. 05 (2006): 1017-1029.De Fraysseix, Hubert. Trémaux trees and planarity.Electronic Notes in Discrete Mathematics31 (2008): 169-180.Brandes, Ulrik. The left-right planarity test. Manuscript submitted for publication 3 (2009).Boyer, John M., and Wendy J. Myrvold. Stop Minding Your ps and qs: A Simplified O(n) Planar Embedding Algorithm. InSODA, vol. 99, pp. 140-146. 1999.Boyer, John M., and Wendy J. Myrvold. Simplified O(n) planarity by edge addition.Graph Algorithms and Applications5 (2006): 241.【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
OI-wiki 平面图Planar Graph完全指南从欧拉公式、对偶图到平面性判定算法【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文是 OI-wiki 图论模块中 平面图 一文的完整展开。平面图planar graph是图论与算法竞赛中一类结构优美、应用广泛的图从欧拉公式 $|V|-|E||F|2$ 到平面图最小割化为对偶图最短路这一经典技巧再到 Kuratowski / Wagner 禁用图刻画与线性时间的平面性判定算法本文将系统梳理这些概念、定理及其证明并结合本仓库图论模块的相关文档图论基础概念、最小割、最短路 等说明其在解题实战中的落地方式。读完本文你将能够准确区分可平面图与平面图、熟练运用欧拉公式推导边数上界、构造平面图的对偶图并完成最小割到最短路的转化同时了解平面性判定的理论与算法脉络。平面图的基本概念如果图 $G$ 能画在平面 $S$ 上即除顶点处外无边相交则称 $G$ 可嵌入平面 $S$$G$ 为可平面图planar graph。画出的没有边相交的图称为 $G$ 的平面表示或平面嵌入planar embedding。可平面图的这个平面嵌入也称为平面图plane graph。[!info] 「平面图」的术语辨析 不同中文文本中「平面图」的含义可能不同。在本文的定义中可平面图是一个图论对象它可能以不同的方式嵌入平面中平面图则是一个几何对象除了图论结构外它还需要指定图的绘制方式。同一个可平面图往往对应着多个平面图。因此如果结论只依赖于图论结构就使用「可平面图」一词如果还依赖于图的平面嵌入方式就使用「平面图」一词。以下是平面图的简单例子左蝴蝶图右$4$ 阶完全图 $K_4$以下是不可平面图的简单例子左$5$ 阶完全图 $K_5$右两部分各 $3$ 个顶点的完全二分图 $K_{3,3}$在 OI-wiki 的图论基础概念一节中平面图也被简要定义为可以画在一个平面上且没有两条边在非端点处相交的图并直接给出了两个重要结论简单连通平面图满足 $|E|\le 3|V|-6$以及 Kuratowski 定理。本文将对这两条结论给出完整的推导与证明。平面图的性质面及其次数设 $G$ 是平面图由 $G$ 的边将 $G$ 所在的平面划分成若干个区域每个区域称为 $G$ 的一个面face。其中无界的面称为无限面unbounded face或外部面external face有界的称为有限面或内部面。每一个平面图有且仅有一个外部面。包围每个面的所有边组成的回路称为该面的边界boundary并称边界中的边与该面关联incident。边界的长度称为该面的次数degree。计算面的次数时每条割边都算作两次。由此可以得到平面图中所有面的次数之和等于边数 $|E|$ 的 $2$ 倍。平面图中$1$ 次面的边界对应于图的自环$2$ 次面的边界通常对应于图的一对重边但这并非唯一的可能——两个嵌套的自环也会形成二次面另外有二次面未必意味着图不是简单的例如一个只有一条边的图中唯一的面即外部面也是二次的。顶点数 $|V|\ge 3$ 的简单连通平面图中所有面次数都至少为 $3$。欧拉公式平面图的一个重要性质是欧拉公式Eulers formula它给出了图的顶点数 $|V|$、边数 $|E|$ 和面数 $|F|$ 之间的关系。[!note] 欧拉公式 对于连通的平面图 $G$有 $$ |V| - |E| |F| 2. $$证明对面数 $|F|$ 应用数学归纳法。归纳起点是 $|F|1$。此时平面图有且只有一个外部面全部边都是割边所以图 $G$ 是一棵树必然有 $|E||V|-1$代入欧拉公式即可发现它成立。假设欧拉公式对于面数 $|F|k$ 的平面图成立。对于面数 $|F|k1$ 的平面图 $G$必然存在非割边 $e$它是两个不同的面的公共边。将边 $e$ 从图中删除得到图 $G-e$它有 $|V|$ 个顶点、$|E|-1$ 条边和 $|F|-1$ 个面。由归纳假设对图 $G-e$ 成立欧拉公式即 $|V|-(|E|-1)(|F|-1)2$整理即得关于图 $G$ 的欧拉公式。根据数学归纳法欧拉公式对所有平面图都成立。$\blacksquare$[!note] 推论多连通分支情形 对于有 $k$ 个连通分支的平面图 $G$有 $$ |V| - |E| |F| k 1. $$证明图 $G$ 的每个连通分支都是平面图但这些连通分支共用同一个外部面。直接对这些连通分支应用欧拉公式并累加总顶点数和总边数都是正确的但总面数多了 $k-1$因为唯一的外部面总共计数了 $k$ 次。将这一修正考虑在内就得到 $|V|-|E||F| 2k - (k-1) k1$。$\blacksquare$由此可以推出平面图的边与顶点的数量关系。[!note] 定理面次数下界导出边数上界 对于有 $k$ 个连通分支的平面图 $G$如果图 $G$ 的每个面次数都至少为 $l \ge 3$那么有 $$ |E| \le \dfrac{l}{l-2}(|V|-k-1). $$证明因为 $G$ 的各面次数至少为 $l$所以所有面的次数和至少为 $l|F|$亦即 $2|E| \ge l|F|$。代入欧拉公式的推论 $|V|-|E||F|k1$得到 $2|E| \ge l(k1-|V||E|)$。利用 $l\ge 2$ 解出 $|E|$即得 $|E| \le \dfrac{l}{l-2}(|V|-k-1)$。$\blacksquare$[!note] 推论稀疏性 设 $G$ 是简单可平面图且 $|V|\ge 3$那么有 $$ |E| \le 3|V|-6. $$证明当 $G$ 连通时所有面次数都至少是 $3$在上述定理中取 $k1$ 且 $l3$即得 $|E|\le 3|V|-6$。当 $G$ 不连通时分为两种情形如果存在连通分支顶点数至少是 $3$那么对这些连通分支可分别建立 $|E_i|\le 3|V_i|-6$顶点数小于 $3$ 的连通分支一定有 $|E_i|\le |V_i|\le 3|V_i|$。将所有不等式相加就得到 $|E|\le 3|V|-6$。如果所有连通分支顶点数都小于 $3$那么整体有 $|E|\le |V|$又因为 $|V|\ge 3$ 时 $|V|\le 3|V|-6$所以结论仍成立。$\blacksquare$这一推论说明简单可平面图是稀疏图——这也是很多平面图算法可以做到线性复杂度的结构性原因后面介绍的线性平面性判定算法正是建立在这一稀疏性之上。对偶图平面图都有相应的几何对偶图dual graph这也是平面图理论中最重要的工具之一。设 $G$ 是平面图可以按下述步骤绘制图 $G^*$在 $G$ 的每个面 $f_i$ 内部都绘制一个点 $v_i^*$对 $G$ 的每条边 $e$如果 $e$ 在面 $f_i$ 和 $f_j$ 的公共边界上就绘制一条连接 $v_i^$ 和 $v_j^$ 的边 $e^$使之与 $e$ 恰相交一次且不与其他图 $G$ 或图 $G^$ 的边相交。特别地当 $e$ 只出现在一个面 $f_i$ 的边界上时需要绘制一条与 $v_i^*$ 关联的自环使之与 $e$ 相交。这样得到的图 $G^*$ 就称作图 $G$ 的对偶图。[!note] 定理 设图 $G^$ 是平面图 $G$ 的对偶图。那么图 $G^$ 是连通的平面图。而且图 $G^{**}$ 与 $G$ 同构当且仅当 $G$ 是连通图。证明图 $G^$ 的平面性由构造过程保证。连通性方面对图 $G^$ 中任意两个顶点 $v_i^,v_j^$设平面中连接它们的直线段经过图 $G$ 的面和边依次为 $f_i,e_{s_1},f_{s_1},\cdots,f_{s_{r-1}},e_{s_r},f_j$它们分别对应对偶图中的顶点和边 $v_i^,e_{s_1}^,v_{s_1}^,\cdots,v_{s_{r-1}}^,e_{s_r}^,v_j^$。由构造可知序列中相邻的顶点和边是相关联的因此这描述了图 $G^$ 中的一条途径所以 $G^$ 连通。由于 $G^{}$ 是 $G^*$ 的对偶图必然连通所以 $G$ 与 $G^{}$ 同构的必要条件是 $G$ 连通。为证明充分性只需证明当 $G$ 连通时$G$ 满足 $G^$ 的对偶图的构造要求。因为 $G^$ 的边与 $G$ 的边天然对应只需证明 $G^$ 的每一个面都恰好包含 $G$ 的一个顶点。对 $G^$ 的任一个面 $f^$设 $e^$ 是其边界上的一条边那么 $G$ 中对应的边 $e$ 的端点之一必然在面 $f^$ 之内故面 $f^$ 中至少存在 $G$ 的一个顶点。由于 $G^$ 和 $G$ 都连通欧拉公式成立而 $G$ 与 $G^$ 边数相同、$G$ 的面数等于 $G^$ 的顶点数所以 $G$ 的顶点数等于 $G^$ 的面数。于是 $G^*$ 的每个面恰好只有 $G$ 的一个顶点。$\blacksquare$平面图与其对偶图的结构之间有很多对应关系这些对应关系是对偶化解题思路的理论基础$G$ 中的面对应 $G^$ 中的点$G$ 中的边对应 $G^$ 中的边$G$ 中的点对应 $G^*$ 中的面$G$ 中的自环对应 $G^$ 中的割边$G^$ 中的自环对应 $G$ 中的割边$G$ 中的边割集对应 $G^$ 中的回路$G^$ 中的回路对应 $G$ 中的边割集。需要注意的是对偶图的概念仅对具体的平面图成立无法定义在任意可平面图上。事实上两个同构的平面图的对偶图未必是同构的——同一个图的不同平面嵌入的对偶图可能并不相同。[!example] 例子 下图画了两个同构的平面图它们的对偶图并不同构。对偶图不同构的原因是右图有一次面它的对偶图有一度顶点而左图没有。在 OI-wiki 的计算几何模块中对偶图思想也有直接体现文档 Delaunay 三角剖分 指出Voronoi 图是 Delaunay 三角剖分的对偶图可以用构造 Delaunay 三角剖分的分治算法求出三角网再用最左转线算法求出其对偶图从而在 $O(n\log n)$ 时间内构造 Voronoi 图。这说明面与点互换的对偶构造在计算几何与图论中是通用的核心思想。实战转化平面图最小割 → 对偶图最短路将可平面图的问题转化到对偶图上有时更容易解决。一个典型的例子是可平面图最小割问题可以转化为对偶图最短路问题。设 $G$ 是带边权的可平面图$s,t$ 是它的两个顶点需要求最小的 $s$-$t$ 割。具体做法是选取合适的平面嵌入使 $s,t$ 出现在图 $G$ 外部面边界上添加自 $s$ 和 $t$ 延伸出去的射线将外部面分为两部分 $f_{}$ 和 $f_{-}$基于该图建立对偶图并将边权赋给对偶图中的对应边。那么对偶图 $G^*$ 中面 $f_{}$ 和 $f_{-}$ 对应顶点之间的路径红色粗线就和图 $G$ 的 $s$-$t$ 边割集黑色粗线一一对应且二者权值相同。这样求解对偶图中的最短路就得到了图 $G$ 中的最小 $s$-$t$ 割。一个常见的误区是根据上述转化方法宣称平面图最小割等于对偶图最短路。事实上它只适用于存在 $G$ 的平面嵌入使得 $s,t$ 共面的情况只是在考察此知识点的算法竞赛题目中给出的图往往具有并且附带这样的平面嵌入。下面给出一个可以用于判定该条件存在性的定理。[!note] 定理 对于可平面图 $G(V,E)$ 的两个顶点 $s,t$存在 $G$ 的平面嵌入使得 $s,t$ 处于同一个面上当且仅当 $(V,E\cup{(s,t)})$ 是可平面图。证明如果存在 $G$ 的平面嵌入使得 $s,t$ 处于同一个面上那么就可以在这个面内添加一条边 $(s,t)$保持图的平面性。反之如果 $(V,E\cup{(s,t)})$ 是可平面图那么任取它的一个平面嵌入$s,t$ 都同处边 $(s,t)$ 所处的面删除 $(s,t)$ 之后$s,t$ 仍然同处一面。$\blacksquare$例如下图展示的情形中添加边 $(s,t)$ 之后得到非平面图 $K_5$故而不存在使 $s,t$ 共面的平面嵌入上述转化不适用。关于最小割问题本身的建模与求解如最大流最小割定理、Dinic 实现、最小割方案输出、割边数量最小化、二者选其一与最大权闭合图等经典模型可进一步参考 OI-wiki 的 最小割文档 及其配套参考代码docs/graph/code/flow/下的实现。更多著名结果平面图还有很多著名的结果本节仅作列举不展开讨论[!note] 四色定理 没有自环的平面图都是可 $4$-着色的。[!note] Fáry 定理 简单可平面图总是存在一种平面嵌入使得图的所有边都是直线段。[!note] 定理Wood 可平面图至多只有 $8|V|-16$ 个极大团。[!note] 定理Tutte $4$-点连通的可平面图都是哈密顿图。可平面性判定给定一个图如何判定它是不是可平面图本节介绍理论基础与实用算法。禁用图刻画可平面图最经典的刻画方式是利用禁用图forbidden graph给出的。首先$K_5$ 和 $K_{3,3}$ 不是可平面图。[!note] 定理 $K_5$ 和 $K_{3,3}$ 不是可平面图。证明前文已说明$|V|\ge 3$ 的简单连通平面图都需要满足 $|E| \le \dfrac{l}{l-2}(|V|-2)$其中 $l$ 是面次数的最小值。对于 $K_5$有 $l3,\ |V|5,\ |E|10$代入得 $10 \le \frac{3}{1}\cdot 3 9$ 不成立所以 $K_5$ 不可能画成平面图。对于 $K_{3,3}$有 $l4,\ |V|6,\ |E|9$代入得 $9 \le \frac{4}{2}\cdot 4 8$ 不成立所以 $K_{3,3}$ 不可能画成平面图。$\blacksquare$事实上它们就是使得一个图不可平面的最小结构只要图不以某种方式包含这两个图为子结构该图就一定是可平面的。第一个可平面性判定定理是Kuratowski 定理它用到了图同胚的概念若两个图 $G_1$ 与 $G_2$ 同构或通过反复插入或消去 $2$ 度顶点后是同构的则称二者是同胚的homeomorphic。[!note] Kuratowski 定理 图 $G$ 是可平面图当且仅当 $G$ 不含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。与此相关的另一个定理是Wagner 定理它利用收缩操作刻画可平面图收缩操作是指重复多次将图的一条边收缩为一个点。[!note] Wagner 定理 图 $G$ 是可平面图当且仅当 $G$ 中没有可以收缩到 $K_5$ 或 $K_{3,3}$ 的子图。可平面图不包含这些类型的子图相对显然所以这两个定理的关键部分都在于相应禁用图条件的充分性。由于与 $K_5$ 或 $K_{3,3}$ 同胚的子图一定可以收缩到它们反过来却未必成立所以Kuratowski 定理提供了一个更弱也更容易检验的判定条件。OI-wiki 的图论基础概念一节也以不存在与 $K_5$ 或 $K_{3,3}$ 同胚的子图的形式引用了 Kuratowski 定理两处表述一致。平面性判定算法尽管看起来并不容易平面性判定问题实际上有很多线性时间算法。但由于这些算法的实现通常都比较复杂它们几乎从未出现在算法竞赛中更多出现在算法工程与图算法库的实现层面。Hopcroft–Tarjan 算法最早的线性时间平面性判定算法但其实现相当复杂。de Fraysseix–Ossona de Mendez–Rosenstiehl 算法也称LR 平面性算法进一步改进了 Hopcroft–Tarjan 算法的流程是目前最优秀的平面性判定算法之一。Python 的 NetworkX 库中就实现了这一算法networkx/algorithms/planarity.py。Boyer–Myrvold 算法同样优秀的线性时间算法。它可以在线性时间内判定给定图是否可平面而且如果图是可平面的算法将输出一个平面嵌入否则算法将输出一个 Kuratowski 子图即与 $K_5$ 或 $K_{3,3}$ 同胚的子图。C 的 Boost 库实现了这一算法boost/graph/planar_detail/boyer_myrvold_impl.hpp。更多相关算法可参考文末提供的文献。特殊的平面图极大平面图平面三角剖分对于简单可平面图 $G$如果在它的任意不相邻顶点间添加边所得图都不再是可平面图就称 $G$ 为极大可平面图maximal planar graph。极大可平面图的平面嵌入称为极大平面图。[!note] 定理 极大可平面图 $G$ 必然连通。而且当顶点数 $|V|\ge 3$ 时图 $G$ 没有割边。证明如果可平面图 $G$ 不连通任选它的一个平面嵌入都可以选择属于不同连通分支的两个顶点在外部面内连接起来所得图显然仍是平面图这与 $G$ 的极大性矛盾所以极大可平面图必连通。若 $|V|\ge 3$ 且 $G$ 有割边 $e(u,v)$则删去 $e$ 后 $G-e$ 恰有两个连通分支$u,v$ 分属不同分支。假设 $v$ 所在分支至少有两个顶点可先将 $u$ 所在分支 $G_1$ 画在平面上选取 $G_1$ 中边界含 $u$ 的任意面 $f$将另一分支 $G_2$ 画在面 $f$ 中。由于 $G_2$ 是简单图其外部面边界不是自环故至少存在另一个顶点 $w\neq u,v$。将 $v,w$ 分别连接到 $u$ 上就得到包含 $G$ 为子图的平面图与极大性矛盾。因此 $|V|\ge 3$ 的极大可平面图一定没有割边。$\blacksquare$极大平面图的结构可以更准确地描述。[!note] 定理 对于顶点数 $|V|\ge 3$ 的平面图 $G$它是极大平面图当且仅当它是简单图且它的每个面次数均为 $3$。证明充分性显然。必要性设极大平面图 $G$ 的某个面 $f$ 的边界长度至少是 $4$。由于 $G$ 无割边该边界只能是一个环 $v_1v_2v_3v_4\cdots v_1$。若 $v_1$ 与 $v_3$ 不相邻则在面 $f$ 内连接 $v_1$ 和 $v_3$ 不会破坏平面性与极大性矛盾所以 $v_1$ 与 $v_3$ 相邻同理 $v_2$ 与 $v_4$ 相邻。但边 $(v_1,v_3)$ 和 $(v_2,v_4)$ 都不会出现在面 $f$ 中即两条边必然在面 $f$ 的外部而无论如何绘制这两条边都必然相交矛盾。所以极大平面图中不存在高于 $3$ 次的面。$\blacksquare$[!note] 推论 对于顶点数 $|V|\ge 3$ 的极大平面图 $G$总有边数 $|E|3|V|-6$ 且面数 $|F|2|V|-4$。由于极大平面图中每个面都是由三条边围成极大平面图也称为平面三角剖分plane triangulation。这一概念与计算几何中的三角剖分参见 OI-wiki 的 三角剖分文档在结构上一脉相承。外平面图设 $G$ 为可平面图若 $G$ 存在平面嵌入 $\tilde{G}$使得 $G$ 中所有顶点都在 $\tilde{G}$ 的一个面的边界上则称 $G$ 为外可平面图outerplanar graph。这一嵌入也称为外平面嵌入或外平面图。通常将边界经过所有顶点的那个面绘制为外部面。外可平面图都是可平面图反之未必成立。外可平面图同样可以使用禁用图刻画[!note] 定理 一个图 $G$ 是外平面图当且仅当 $G$ 中不含与 $K_4$ 或 $K_{2,3}$ 同胚的子图。对于外可平面图同样可以讨论极大外可平面图的概念对于简单外可平面图 $G$如果在它的任意不相邻顶点间添加边所得图都不再是外可平面图就称 $G$ 为极大外可平面图maximal outerplanar graph其外平面嵌入称为极大外平面图。直观上看极大外平面图其实就是平面上多边形的三角剖分。[!note] 定理 对于顶点数 $|V|\ge 3$ 的极大外平面图 $G$且所有顶点都在外部面的边界上那么图 $G$ 恰有 $|V|-2$ 个内部面。证明对 $|V|$ 应用数学归纳法。归纳起点 $|V|3$ 时$G$ 是三元环只有 $1$ 个内部面命题成立。假设命题对 $|V|k$ 成立考虑 $|V|k1$ 的情形。首先证明图 $G$ 一定存在 $2$ 度顶点。反设不然将外部面边界上的顶点顺次编号对每个 $i1,2,\cdots,k1$定义 $f(i)$ 为与顶点 $i$ 连接且编号不与之相邻的顶点的最小编号。首先 $1f(1)$。由于点 $1$ 已经与 $f(1)$ 连接点 $2$ 与 $f(2)$ 的连线不能越过边 $(1,f(1))$就必然有 $12f(2)f(1)$。同理 $23f(3)f(2)$。由于顶点只有有限多个这个逐渐缩小的过程必然在有限步后终止。令 $i^$ 为满足 $1\cdotsi-1if(i)f(i-1)\cdotsf(1)$ 的编号 $i$ 的最大值那么由于点 $i^$ 和点 $f(i^)$ 不相邻必然有 $i^i^1f(i^)$而重复之前的论述仍应有 $i^i^1f(i^1)f(i^)$这与 $i^*$ 的最大性矛盾。故 $G$ 必然存在 $2$ 度顶点。设 $v$ 是一个 $2$ 度顶点删除 $v$ 得到顶点数为 $k$ 的外平面图 $G-v$它必然是极大外平面图否则在其上合法添加边的方法对 $G$ 也适用。由归纳假设$G-v$ 恰有 $k-2$ 个内部面而删去 $v$ 恰好减少了一个 $G$ 的内部面所以 $G$ 的内部面数目为 $k-1$。$\blacksquare$[!note] 定理 对于顶点数 $|V|\ge 3$ 的外平面图 $G$且所有顶点都在外部面的边界上那么 $G$ 是极大外平面图当且仅当 $G$ 的外部面边界是长为 $|V|$ 的环且所有内部面边界均是长为 $3$ 的环。证明充分性显然——连接外部面边界上的两个不相邻顶点若连接发生在外部面中则所有顶点无法都出现在一个面的边界上否则连线必然与内部面的边界相交。必要性假设外部面边界 $v_1v_2v_3\cdots v_nv_1\ (n|V|)$ 不是环则存在 $i\neq j$ 且 $i-j\neq\pm 1\pmod{n}$ 使得 $v_iv_j$。不妨设 $1ijn$。此时与 $v_{i-1}$ 相关联的边只能出现在回路 $v_jv_{j1}\cdots v_nv_1\cdots v_{i-1}v_i$ 围成的有界区域内部与 $v_{i1}$ 相关联的边只能出现在回路 $v_iv_{i1}\cdots v_{j-1}v_j$ 围成的有界区域内部所以 $v_{i-1}$ 和 $v_{i1}$ 无法相邻。可以在外部面内添加连接 $v_{i-1}$ 和 $v_{i1}$ 的边 $e$所得 $Ge$ 显然仍是平面图且外部面边界包含所有顶点这与极大外平面性矛盾。所以外部面必是长度为 $|V|$ 的环内部面边界均为长为 $3$ 的环的原因与极大平面图一致。$\blacksquare$[!note] 推论 对于顶点数 $|V|\ge 3$ 的极大外平面图 $G$有$|E|2|V|-3$$G$ 中至少有 $3$ 个顶点度数小于等于 $3$且至少有 $2$ 个顶点度数为 $2$$G$ 的点连通度为 $2$。仓库内的知识脉络本仓库图论模块围绕平面图展开的知识体系相当完整可将本文与以下文档对照阅读形成闭环图论基础概念平面图的最简定义、$|E|\le 3|V|-6$ 边数上界与 Kuratowski 定理的速查条目最小割最小割的定义、最大流最小割定理、Dinic 参考代码对应文件位于docs/graph/code/flow/以及二者选其一最大权闭合图等经典建模是平面图对偶化转化的求解端最短路对偶图最短路转化中的求解目标三角剖分Delaunay 三角剖分与 Voronoi 图互为对偶图的应用实例插头 DP其中提到当 $n,m\le 100$ 时可用 FKT 算法计算平面图的完美匹配数可见平面性在更广泛算法问题中的价值。习题以下为与本主题配套的经典练习题目名称整理自原文档可在各 OJ 上检索Luogu P3209 [HNOI2010] 平面图判定Luogu P3249 [HNOI2016] 矿区Luogu P4001 [ICPC-Beijing 2006] 狼抓兔子经典的平面图最小割转对偶图最短路模板题Luogu P4073 [WC2013] 平面图Luogu P7295 [USACO21JAN] Paint by Letters P参考资料Planar graph / Planarity testingWikipedia 相关词条Bondy, John Adrian, and Uppaluri Siva Ramachandra Murty.Graph Theory with Applications. Vol. 290. London: Macmillan, 1976.Diestel, Reinhard.Graph Theory. Vol. 173. Springer Nature, 2025.Patrignani, Maurizio. Planarity Testing and Embedding. (2013): 1-42.Hopcroft, John, and Robert Tarjan. Efficient planarity testing.Journal of the ACM (JACM)21, no. 4 (1974): 549-568.De Fraysseix, Hubert, Patrice Ossona De Mendez, and Pierre Rosenstiehl. Trémaux trees and planarity.International Journal of Foundations of Computer Science17, no. 05 (2006): 1017-1029.De Fraysseix, Hubert. Trémaux trees and planarity.Electronic Notes in Discrete Mathematics31 (2008): 169-180.Brandes, Ulrik. The left-right planarity test. Manuscript submitted for publication 3 (2009).Boyer, John M., and Wendy J. Myrvold. Stop Minding Your ps and qs: A Simplified O(n) Planar Embedding Algorithm. InSODA, vol. 99, pp. 140-146. 1999.Boyer, John M., and Wendy J. Myrvold. Simplified O(n) planarity by edge addition.Graph Algorithms and Applications5 (2006): 241.【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
)
)
