平面图检查器

平面图检查器

平面图检查器判定一个简单的无向图是否为平面图（即是否可以画在平面上且没有任何两条边相交）。当图未能通过测试时，它会查找并可视化库拉托夫斯基见证（Kuratowski witness）：即 K₅（5个顶点的完全图）或 K₃,₃（3 + 3 个顶点的完全二部图）的细分。该工具专为教学、竞赛性编程热身以及快速检查小型图结构而设计。

什么是“平面”？

如果一个图 G = (V, E) 可以嵌入平面，使得各边仅在它们的共同端点处相交（无交叉），则该图是平面图。等效地，G 可以画在球面上而没有交叉。平面性是一种纯粹的拓扑属性：它不取决于你如何绘制该图，而仅取决于是否存在某种无交叉的绘制方式。

平面图随处可见 —— 道路和公用事业网络、印刷电路板（PCB）布线、正多面体的边图以及多面体的面结构。然而，许多“自然”的图确实是非平面的：任何时候你尝试将 3 个房子连接到 3 个公用事业设施而没有交叉，你都会遇到 K₃,₃ 障碍。

库拉托夫斯基定理 —— 检查器的核心

卡齐米日·库拉托夫斯基（Kazimierz Kuratowski）在 1930 年证明了平面性具有纯粹的组合特征：

一个图 H 的细分是通过将 H 的某些边替换为较长的路径而获得的，这些路径的内部顶点都是全新的 2 度顶点。因此，库拉托夫斯基定理说明 K₅ 和 K₃,₃ 是平面性的唯一阻碍 —— 每个非平面图都以某种“拉伸”的形式包含其中之一。

禁止图

欧拉公式与快速必要条件

在运行（相对昂贵的）细分搜索之前，检查器会应用由欧拉公式导出的两个快速必要条件：对于在平面上绘制的任何连通平面图，设其有 V 个顶点、E 条边和 F 个面（包括无界的外部面），我们有：

结合简单平面图的每个面在其边界上至少有 3 条边的观察，我们得到了边的上限：

任何违反这些不等式的图立即被判定为非平面，无需进行细分搜索。K₅ 有 m = 10, n = 5 ⇒ 3n − 6 = 9，因为 10 > 9，违反了界限。K₃,₃ 有 m = 9, n = 6 ⇒ 2n − 4 = 8，因为 9 > 8，违反了二部图界限。

细分搜索的工作原理

在低成本的欧拉检查之后，检查器会直接搜索细分：

1. 快速判定 —— 检测作为字面子图的 K₅ 或 K₃,₃。 如果 5 个顶点两两相邻，那它本身就是 K₅。如果 6 个顶点分为 3 + 3 且 9 条跨组边全部存在，那它本身就是 K₃,₃。
2. K₅ 细分搜索。 对于每组候选的 5 个“分支”顶点（G 中每个度数 ≥ 4），尝试找到 10 条路径（每对分支一条），这些路径是内部顶点不相交的（除分支顶点外的顶点不会出现在多条路径中），并且避免使用其他分支作为内部顶点。一旦匹配成功即证明非平面性。
3. K₃,₃ 细分搜索。 选取 6 个分支（每个度数 ≥ 3）并进行 3 + 3 二部划分。搜索具有相同内部顶点不相交要求的 9 条跨组路径。
4. 无见证 ⇒ 平面。 如果在尺寸限制内未找到任何细分，库拉托夫斯基定理保证该图是平面图。

寻找顶点不相交路径通常是 NP 困难的，因此检查器使用了受限随机贪婪搜索：每次迭代根据难度对所需路径对进行排序，首先使用随机化 BFS 为最难的路径对选取路径，移除这些内部顶点，然后继续。如果该特定排序失败，它将使用洗牌后的顺序重试 —— 每个分支配置最多尝试 40 次。在所有测试过的小型图（最多 16 个顶点）上，这足以在见证存在时定位到它。

如何使用此计算器

1. 使用顶部的选项卡选择输入格式：边列表或邻接列表。两者都编码相同的图。
2. 输入您的图。该图被视为无向图，因此 A-B 和 B-A 是同一条边。
3. 点击检查平面性。该工具报告结论，显示逐步推理（欧拉、二部、库拉托夫斯基），并渲染图。
4. 对于非平面图，可视化会将 K₅ 或 K₃,₃ 细分着色，并列出 10 条（或 9 条）顶点不相交路径。点击路径行可将其隔离显示。
5. 对于平面图，将报告面数 F = m − n + 1 + c 以及图结构。

范例 1 —— K₄ 是平面图

K₄ 有 n = 4, m = 6。任何 ≤ 4 个顶点的图都是平面的，实际上 K₄ 可以嵌入为一个三角形，其内部有一个顶点连接到所有三个角。欧拉公式表明 F = 6 − 4 + 2 = 4 个面：三个三角形内面加上外部面。

范例 2 —— K₃,₃ 是非平面图

K₃,₃ 有 n = 6, m = 9。它是二部图，因此适用二部图界限： m = 9 > 2n − 4 = 8。仅此一项就证明了其非平面性。其见证是显而易见的 —— K₃,₃ 本身就是禁止子图。该工具随后会突出显示 3 + 3 划分和 9 条直接边。

范例 3 —— 彼得森图（Petersen graph）

彼得森图有 n = 10, m = 15，因此 m ≤ 3n − 6 = 24，快速欧拉检查通过。然而它是著名的非平面图。检查器定位到一个 K₃,₃ 细分：从外五边形和内五角星中选取六个顶点，使得每个跨组对都可以通过剩余的四个顶点通过顶点不相交路径进行路由。该工具绘制了该见证，使 1930 年代的几何理论变得触手可及。

平面性的应用

• VLSI 和 PCB 布线。 只有当连接图是平面的，单层电路才是可行的；非平面网络迫使使用过孔或额外的层。
• 图绘制与可视化。 平面图支持清晰、无交叉的布局 —— 适用于地铁线路图、调用图和原理图。
• 算法设计。 许多 NP 困难问题（最大剪切、顶点覆盖、图同构）在限制为平面图时变为多项式时间可解。
• 图着色。 四色定理保证每个平面图都是 4 色可染的 —— 这是一个经典的结论，其陈述依赖于平面性。
• 组合优化。 平面最短路径、最大流和最小剪切都有专门的快速算法。
• 分子化学。 苯环芳香烃图是平面的；某些笼型分子则不是。

常见问题解答

图的平面性是什么意思？

如果一个图可以画在平面上，使得除了共享顶点外没有两条边相互交叉，那么该图就是平面图。等效地，一个图是平面图当且仅当它可以画在球面上而没有交叉。树、环、立方体图和正多面体都是平面图，而 K₅ 和 K₃,₃ 是典型的非平面图示例。

什么是库拉托夫斯基定理？

库拉托夫斯基定理指出，一个有限图是平面图当且仅当它不包含作为 K₅ 或 K₃,₃ 细分的子图。细分是通过将某些边替换为较长的路径而获得的，每条路径都经过全新的 2 度顶点。这为非平面性提供了具体的组合证明。

K₅ 和 K₃,₃ 有什么区别？

K₅ 有 5 个顶点，每对顶点都由一条边连接，总共有 10 条边。K₃,₃ 有 6 个顶点，分为两组，每组 3 个，其中一组的每个顶点都与另一组的每个顶点相连，总共有 9 条边。两者都是同类中最小的非平面图，根据库拉托夫斯基定理，它们共同构成了平面性的禁止子图。

欧拉不等式有什么帮助？

平面连通图的欧拉公式 V − E + F = 2 结合简单平面图的每个面至少有 3 条边的实事，得出 m ≤ 3n − 6。任何违反此界限的简单图立即判定为非平面。对于二部平面图，每个面至少有 4 条边，从而得出更紧凑的界限 m ≤ 2n − 4。检查器将这两者作为快速拒绝规则应用。

尺寸限制是多少？

检查器最多处理 16 个顶点和 60 条边。这涵盖了典型的教学和竞赛风格的图，包括彼得森图、莫比乌斯-坎托图、小型超立方体和完全图 K₇。更大的图需要线性时间专用平面性测试，如 Hopcroft-Tarjan 或左右平面性测试。

见证细分是如何绘制的？

当图为非平面时，找到的 K₅ 的 5 个分支顶点 —— 或 K₃,₃ 的 6 个分支顶点（分为 A 和 B 两组）—— 会在内环上突出显示。所需的 10 条（或 9 条）内部顶点不相交路径各以不同颜色绘制，以便您可以视觉追踪 K₅ 或 K₃,₃ 拓扑。不属于细分的顶点和边将被淡化显示。

延伸阅读

• 平面图 — 维基百科
• 库拉托夫斯基定理 — 维基百科
• 欧拉示性数 — 维基百科
• 彼得森图 — 维基百科
• 瓦格纳定理（子图版本） — 维基百科