平面图：不交叉的行军地图

平面图：不交叉的行军地图

印刷电路板的布线车间里，设计师盯着屏幕上的连线眉头紧锁：导线在绝缘层内不许交叉，可芯片引脚之间的连接需求却层层叠叠——什么时候有解，什么时候无解？这类"画在平面上、边与边互不交叉"的图就是平面图。它远不只是画图美学问题：电路布线、地铁线路图、地图着色（第 8 章四色定理的舞台）全都建立在平面性之上。本节把档案柜第二格填满：欧拉公式为平面图清点户口，一连串紧约束随之倾泻而出，平面性的判定原理与对偶图的概念也在此归档。

欧拉公式：点边面的恒等式

平面图把平面切分成若干块互不连通的区域，称为面（含最外面那个无界的"外面"）。欧拉公式说：连通平面图的顶点数减边数加面数恒等于二。用归纳法证明只需看"拆边"：从生成树出发（面数为一，公式退化为顶点减边加一等于一，恰是树的性质"边数等于顶点数减一"），每加一条非树边都恰好把某个面一分为二——边数与面数同步加一，等式两边始终平衡。

公式看似只是计数游戏，威力却在于它对一切平面画法都成立——无论怎么扭曲重画，点边面的配额恒定。于是平面图是一类"骨子里稀疏"的图：把"每个面至少由三条边围成"的朴素事实（每面边界贡献至少三段边、每段边至多记入两个面）代入欧拉公式，得到边数不超过"顶点数的乘以三减去六"的紧上界（顶点数不小于三时）；平均度随之被压在六以下，且任何平面图必有度数不超过五的顶点。这些推论的证明全部是三五行的不等式换算，却个个是硬通货——第 8 章五色定理的证明第一步正是"揪出一个低度顶点"，弹药由本节供应。

不可平面性：两座界碑

平面图有边界吗？有两座著名界碑。完全图在顶点数达到五以后不可平面（它的边数太密，越过上界）；完全二分图（两阵营各三个顶点、全员交叉连接）同样不可平面。深刻之处在于这两座界碑还是"仅有的"障碍：图可平面，当且仅当它不含这两座界碑的"细分"（把边拆成路径后的变形）——这是平面性判定的 Kuratowski 定理。细分不改变交叉与否的宿命，就像扭动绳结不改变打的结；判定平面性因此转化为搜索"藏起来的界碑"，线性时间的算法确实存在（但远比想象精巧，属于进阶内容）。

import networkx as nx

# 体验两座界碑
K5 = nx.complete_graph(5)
K33 = nx.complete_bipartite_graph(3, 3)
cycle = nx.cycle_graph(9)                       # 一圈九点，显然可平面
print("K5:", nx.check_planarity(K5)[0])
print("K33:", nx.check_planarity(K33)[0])
print("九点圈:", nx.check_planarity(cycle)[0])

# 边数上界快筛：边太多直接出局
def edge_bound_screen(n):
    return 3 * n - 6

grid = nx.grid_2d_graph(3, 3)                   # 三乘三网格，典型平面图
print("网格图可平面:", nx.check_planarity(nx.convert_node_labels_to_integers(grid))[0])
print("九点网格边数:", grid.number_of_edges(), "上界:", edge_bound_screen(9))
​

边数上界是最廉价的初筛：边数越过"三倍顶点数减六"必不平面，无需任何精巧搜索。但要注意它只是必要条件——边数不超的图也未必平面（两座界碑自身的细分可以很"瘦"）。

对偶图：面与顶点的角色互换

平面嵌入还孕育一种优雅的结构：对偶图。把每个面缩成一个顶点，共享一条边的两个面之间连一条边，得到的新图也是平面图，且"顶点与面"角色互换——原图的面变新图的点，原图的点变新图的面。地图着色在对偶图里变成顶点着色（相邻区域变相邻顶点——四色问题的标准形式化正是如此）；电网的对偶里，串联与并联互相翻转。对偶不是平面图的装饰品，而是理解"面空间"的正牌语言。

应用侧的清单还能开很长：电路布线把元件网表画成图，平面性决定单层布线可行与否（不可平面就要加过孔或分层）；地图学与地理信息系统里，区域邻接结构天然是平面图的对偶；网格剖分（有限元分析的前处理）本身就是高质量平面嵌入的生成问题。第 8 章的四色定理在此回收：平面图的色数至多为四，证明的智力史与机器介入的争议当时已述，本节补上它依赖的平面图弹药库——低度顶点存在性与"删点归纳"的骨架。

动手演练：边数上界的完整推导

与其背下"边数不超过三倍顶点数减六"的结论，不如亲手把推导走一遍——这是平面图档案里最值得练手的一段不等式体操：

import networkx as nx

def planar_edge_audit(G, name):
    """核对平面图的三条硬约束：边数上界、平均度、低度顶点"""
    n, m = G.number_of_nodes(), G.number_of_edges()
    bound = 3 * n - 6 if n >= 3 else m
    avg_deg = 2 * m / n
    low_deg = [v for v in G.nodes if G.degree(v) <= 5]
    print(f"{name}: 顶点 {n}, 边 {m}, 边数上界 {bound}, "
          f"平均度 {avg_deg:.2f}, 低度顶点 {len(low_deg)} 个")
    assert m <= bound, "越过平面图边数上界——这图必不平面！"

# 三张典型平面图过一遍审计
grid = nx.convert_node_labels_to_integers(nx.grid_2d_graph(4, 4))
planar_edge_audit(grid, "四乘四网格")
planar_edge_audit(nx.cycle_graph(10), "十点圈")
planar_edge_audit(nx.complete_graph(4), "四点完全图")
​

审计函数把三条约束变成可执行的哨兵：边数越过上界立即报警（必不平面）、平均度被压在六以下、任何平面图必有度数不超过五的顶点。第三条最值得单独说说——它是反证法的小品：若人人度数不低于六，平均度就下不来，而平均度等于两倍边数除以顶点数，结合边数上界一算就矛盾。于是每个平面图都自带一个"软柿子"顶点，五色定理的归纳证明正是反复捏这个软柿子：删掉它、给小一圈的图着色、放回来时它的邻居至多占四种颜色，第五色必然有富余——平面图的整个着色理论都踩在这块垫脚石上。

对偶图也能用 networkx 直接上手玩：取一张平面图，生成它的对偶，再数一数"顶点数加面数互换"的恒等式：

def dual_demo(G):
    """平面图与对偶的规模对照（利用欧拉公式的守恒）"""
    planar, emb = nx.check_planarity(G)
    assert planar, "先确认可平面"
    n, m = G.number_of_nodes(), G.number_of_edges()
    f = m - n + 2                          # 欧拉公式反解面数
    print(f"原图: 顶点 {n}, 边 {m}, 面 {f}")
    print(f"对偶图应有: 顶点 {f}, 边 {m}, 面 {n}——点与面完整互换")
    return f

dual_demo(nx.convert_node_labels_to_integers(nx.grid_2d_graph(3, 3)))
​

欧拉公式在这里再次扮演守恒律：它让"面数"可以从点边直接算出，也让对偶的规模无需画图就能预知。档案柜里的每件工具都在互相印证，这正是数学结构最迷人的一面。

⚠️ 常见坑：以为"画出来有交叉"就不可平面。交叉可能只是画法不佳——换一种画法或许就摊平了；判定必须交给算法，肉眼只有直觉没有裁决权。反过来，边数超界的图倒是可以肉眼枪毙。

💡 关键直觉：欧拉公式是平面图的"守恒律"——像能量守恒一样，无论怎么重画变形，点边面的配额一动不动。守恒律永远是最硬的约束，从它挤出的不等式个个是定理生产线。

档案第二格就位。下一格画风一变：不再研究画得平不平，而是问——如果图是掷骰子随机长出来的，它会是什么模样？