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$——取 $k1$、$l3$得到实践中最好用的判据$$ |E| \le 3|V|-6. $$使用方法先数出图的顶点数与边数。如果 $|V| \ge 3$ 且 $|E| 3|V|-6$可以立即断定该图不是可平面图不需要继续做任何事情。文档中用同一思路证明了两个经典反例$K_5$$l3$、$|V|5$、$|E|10$而 $3|V|-6 9$边数超限不可平面$K_{3,3}$$l4$、$|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^*$ 的绘制流程如下在 $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$ 是连通图时$G^{**}$$G^*$ 的对偶图与 $G$ 同构。对连通图可以做双重对偶验证结构对应关系必须逐条成立$G$ 的面对应 $G^$ 的点$G$ 的边对应 $G^$ 的边$G$ 的点对应 $G^$ 的面$G$ 中的自环对应 $G^$ 中的割边反之亦然$G$ 中的边割集对应 $G^*$ 中的回路反之亦然。同时记住面的基本计数每条割边在面的次数中算两次因此平面图中所有面的次数之和等于 $2|E|$顶点数 $|V| \ge 3$ 的简单连通平面图中所有面次数都至少为 3。典型应用把平面图最小割转化为对偶图最短路对偶图的实际价值在于把可平面图上的割问题转化到对偶图上的最短路问题相关文档见 最小割 与 最短路。设 $G$ 是带边权的可平面图$s, t$ 是它的两个顶点需求最小 $s$-$t$ 割转化流程如下选取合适的平面嵌入使 $s, t$ 都出现在外部面边界上添加自 $s$ 和 $t$ 延伸出去的射线将外部面分为 $f_$ 和 $f_-$ 两部分基于该图建立对偶图并把边权赋给对偶图中的对应边对偶图 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI Wiki 平面图：如何判定平面性并求对偶图
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$——取 $k1$、$l3$得到实践中最好用的判据$$ |E| \le 3|V|-6. $$使用方法先数出图的顶点数与边数。如果 $|V| \ge 3$ 且 $|E| 3|V|-6$可以立即断定该图不是可平面图不需要继续做任何事情。文档中用同一思路证明了两个经典反例$K_5$$l3$、$|V|5$、$|E|10$而 $3|V|-6 9$边数超限不可平面$K_{3,3}$$l4$、$|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^*$ 的绘制流程如下在 $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$ 是连通图时$G^{**}$$G^*$ 的对偶图与 $G$ 同构。对连通图可以做双重对偶验证结构对应关系必须逐条成立$G$ 的面对应 $G^$ 的点$G$ 的边对应 $G^$ 的边$G$ 的点对应 $G^$ 的面$G$ 中的自环对应 $G^$ 中的割边反之亦然$G$ 中的边割集对应 $G^*$ 中的回路反之亦然。同时记住面的基本计数每条割边在面的次数中算两次因此平面图中所有面的次数之和等于 $2|E|$顶点数 $|V| \ge 3$ 的简单连通平面图中所有面次数都至少为 3。典型应用把平面图最小割转化为对偶图最短路对偶图的实际价值在于把可平面图上的割问题转化到对偶图上的最短路问题相关文档见 最小割 与 最短路。设 $G$ 是带边权的可平面图$s, t$ 是它的两个顶点需求最小 $s$-$t$ 割转化流程如下选取合适的平面嵌入使 $s, t$ 都出现在外部面边界上添加自 $s$ 和 $t$ 延伸出去的射线将外部面分为 $f_$ 和 $f_-$ 两部分基于该图建立对偶图并把边权赋给对偶图中的对应边对偶图 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考