平面图判定与性质

可视化演示

交互演示平面图的欧拉公式V-E+F=2，以及K5和K3,3两个不可平面化的禁止子图，切换模式查看边交叉情况。

平面图定义——纸上画路的艺术

小林拿起铅笔，在图纸上画出第一版路网：五个广场两两相连。他越画越不对劲——当画到连接第五对广场的那条路时，铅笔无论如何都绕不开已经画好的路。他沮丧地意识到，这份规划如果不修立交桥，就永远无法画完。他的困惑，正是图论中“平面性”这一核心问题的开端。

数学上，如果一个图能画在平面上，使得所有边只在顶点处相交，就称它为平面图。注意关键词是“存在一种画法”：五角星图案的直观画法有交叉，但只要把五个顶点重新排列成五边形，再画对角线，所有交叉都消失了——所以它是平面图。而小林画的“五个广场两两相连”（即完全图 K5），无论怎样重排，总有一条线要横穿别人，这是平面性的“结构性障碍”。

判定平面性有两个层次的工具。一个来自欧拉公式的必要条件：连通平面图满足 E ≤ 3V−6。用这个式子可以一票否决 K5：V=5 时上界是 9，而 K5 有 10 条边，直接出局。但注意这只是必要条件——K3,3 满足 9 ≤ 12，仍然不是平面图，真正的“照妖镜”是下一节的库拉托夫斯基定理。

小林把这个不等式当作“体检指标”，快速筛查掉明显不靠谱的方案。他明白，在纸上画路的艺术，既考验手艺，更考验对结构规律的洞察。一张图能不能平铺，不是看运气，而是看它的“筋骨”是否触碰了边界。

欧拉公式——规划师的验算神器

小林画了一百张设计图后，忽然发现一个铁律：每张图的路口数减去道路段数，再加上街区数，永远等于 2。他一开始以为是巧合，直到他在图纸角落写下了那个平凡的恒等式——V−E+F=2。这个公式后来以“欧拉公式”之名传遍数学界。

这里的 V 是顶点数，E 是边数，F 是面数。面数包括最外面的“无限大街区”——想象城市之外就是空旷荒野，那也算一个面。公式只对连通平面图成立：一旦有孤立的“飞地”（多个连通分量），常数 2 就变成 1+C（C 为连通分量数）。

证明并不困难，用对边数的归纳法。基础情形只有 1 个顶点、0 条边时，1−0+1=2，成立。添加一条新边时分类讨论：若新边连接两个已有顶点，则封闭一个新面，E 和 F 同时加 1；若新边连入一个新顶点，则 V 和 E 同时加 1。两种情况下 V−E+F 都保持不变，于是公式对所有连通平面图成立。

小林用这个公式轻松算出任意路网的街区数：只要数清楚路口和道路段。他甚至由此推导出边数天花板 E ≤ 3V−6——正是他用来“体检”规划的法宝。欧拉公式不仅是一道算术题，更像一把钥匙，打开了整个平面图理论的大门。

库拉托夫斯基定理——两条无法逾越的天堑

欧拉公式能筛掉很多非平面图，但小林遇到了一个漏网之鱼：三个电厂各拉三条线到三个工厂，总共 9 条线、6 个顶点，完全满足 9 ≤ 12。但他无论如何都画不出无交叉的布线图。最终他明白了：有些结构障碍不是“量”的问题，而是“形”的问题。

图论中，K5（五个顶点两两相连）和 K3,3（左右各三个顶点，两两全连）是两座不可逾越的“天堑”。波兰数学家库拉托夫斯基证明了一个漂亮的充要条件：一个图是平面图，当且仅当它不含 K5 或 K3,3 的“细分”。细分就像在一条路中间增设几个并不改变交通拓扑的“环岛”——把一条边替换成一条更长的路径。只要能找到这样的“加站变体”，原图就注定非平面。

判定算法可以这样理解：先把所有度为 2 的顶点“压缩”回原来的边，再看压缩后的图是否藏有 K5 或 K3,3 的影子。现代线性时间平面性检测算法（如 Hopcroft-Tarjan）正是基于这一理论，用深度优先搜索和复杂的括号结构高效判别，而非暴力枚举子图。

对小林来说，“天堑”结构就像道路规划中的地质断层带：一旦探测到，就该立即调整方案，而不是徒劳地继续画线。他甚至学会了一种新思维——把复杂图“瘦身”成核心骨架，再检查骨架是否触碰红线。

对偶图构造——街区的社交网络

小林决定换个视角看问题。他不再盯着道路，而是把每个街区当作一个“点”，两个街区共享一条街就连接一条“友谊线”。当他这样重绘时，原本的道路网消失不见，取而代之的是一张全新的图——这就是对偶图。

严格地说，给定平面图 G，它的对偶图 G* 这样构造：G 的每个面对应 G* 的一个顶点；G 中每一条边 e 两侧各有一个面（复边情形可能是同一面），在 G* 中连接这两个面对应的顶点。于是 G* 的顶点数等于 G 的面数，G* 的边数等于 G 的边数。更妙的是，对于连通平面图，双重对偶 (G*)* 又变回原图 G。

小林把这张“街区社交网络”拿给同事看，同事们恍然大悟：原来城市的地图还可以这样读。对偶图的价值不只是视角切换——它把“给面涂色”这个略显别扭的问题，翻译成了图论中最成熟的“给顶点涂色”问题，为下一节的五色定理铺平了道路。

五色定理——五种颜色永远够用

小林接到新任务：给城市的每个街区涂上颜色，要求相邻街区（共享道路）颜色必须不同。省油漆的他问：最少需要几种颜色？五色定理斩钉截铁地回答：5 种颜色，永远够用。

证明的关键是一步“低度引理”：每个平面图都至少存在一个连了不超过 5 条边的顶点。这由欧拉公式和握手定理联手推出——所有顶点度数之和等于 2E，结合 E ≤ 3V−6 可知平均度数小于 6，所以必然存在度数不超过 5 的顶点。

证明思路用归纳法。先平面嵌入图，去掉这个低度顶点 v，给剩下的图涂 5 色，然后把 v 加回来。如果 v 的邻居们没用满 5 色，直接涂剩余色即可。麻烦在于 v 恰好有 5 个邻居且涂满了 5 色。这时用 Kempe 链技术：观察邻居 v₁ 与 v₃ 所在的两条“1-3 双色链”，若这两条链不相连，则可以把某条链上所有 1、3 颜色整体交换，硬是腾出一种颜色给 v。这就是五色定理的核心思想——证明比四色定理简单得多，且 Kempe 链本身成为后世无数算法的积木。

小林长舒一口气：五种颜色足够，意味着他不需要准备一打油漆桶。他甚至忍不住想，能不能用更少的颜色？答案在几十年后被计算机验证——四色定理，四种颜色就够。但那把钥匙，依然是从 Kempe 链这把“旧锁”里提炼出来的。

应用场景——从画纸走进硅片与地图

小林的图纸被一家芯片工厂看中了。他们把道路抽象成导体，把街区抽象成元件，要求所有导线在同一层板上不交叉——这不就是平面图吗？平面图理论从纸面走向了真实的硅片世界。

在超大规模集成电路（VLSI）中，平面性检测是布线阶段的第一道关卡：如果电路图非平面，工程师就必须设计过孔、跳线或改用多层板，成本随之上升。地图着色更是直接受益者：四色定理保证 4 种颜色足够区分任何国家的邻接关系，地图册的印刷成本和配图美观度因此大幅改善。在社交网络和知识图谱的可视化中，平面嵌入算法让复杂的实体关系图在屏幕上层次分明、不缠不乱。

从城市规划师的铅笔，到芯片工厂的蚀刻机，平面图理论横跨了数学与工程。读懂一张图能否“平铺”，你就掌握了一种“在硬约束下优雅布局”的思维模式——这种模式在算法设计、资源分配和可视化表达中价值无穷。

AI 应用场景

Python 演示

import itertools  class Graph:    """无向图: V 为顶点数, edges 为 (u, v) 边列表"""    def __init__(self, V, edges):        self.V = V        self.Edges = set(frozenset((u, v)) for u, v in edges)     def edge_count(self):        return len(self.Edges)     def has_k5_sub(self):        for comb in itertools.combinations(range(self.V), 5):            need = {frozenset(p) for p in itertools.combinations(comb, 2)}            if need.issubset(self.Edges):                return True        return False     def has_k33_sub(self):        for six in itertools.combinations(range(self.V), 6):            six = set(six)            for left in itertools.combinations(six, 3):                left = set(left)                right = six - left                cross = {frozenset((a, b)) for a in left for b in right}                if cross.issubset(self.Edges):                    return True        return False  def analyze(name, g):    V = g.V    E = g.edge_count()    bound = 3 * V - 6    print("[%s] V=%d  E=%d  3V-6=%d" % (name, V, E, bound))    print("  E <= 3V-6 : %s" % (E <= bound))    print("  K5 细分    : %s" % g.has_k5_sub())    print("  K3,3 细分  : %s" % g.has_k33_sub())    if g.has_k5_sub() or g.has_k33_sub():        print("  结论: 非平面图")    elif E <= bound:        print("  结论: 可能为平面图")    else:        print("  结论: 违反必要条件, 非平面图")  def main():    k4 = Graph(4, itertools.combinations(range(4), 2))    analyze("四面体 K4", k4)     k5 = Graph(5, itertools.combinations(range(5), 2))    analyze("完全图 K5", k5)     k33 = Graph(6, [(a, b + 3) for a in range(3) for b in range(3)])    analyze("完全二分图 K3,3", k33)  if __name__ == "__main__":    main()

1. self.Edges = set(frozenset((u, v)) for u, v in edges)用 frozenset 统一边，消除 (u,v) 与 (v,u) 的顺序差异，让“无向”语义成立。
2. need.issubset(self.Edges)检查 5 个点两两之间的 10 条边是否全部存在于图中，这是 K5 的精确判据。
3. for left in itertools.combinations(six, 3)枚举 6 个顶点中的 3 个作为二分图左侧，剩余 3 个自动成为右侧。
4. cross = {frozenset((a, b)) for a in left for b in right}构造跨组所有 9 条边，若全部在图中则找到 K3,3。
5. if __name__ == "__main__":入口保护，保证脚本被其他模块导入时不会自动执行测试。

常见误区

面试题