拓扑图论：平面性、图嵌入与 Kuratowski 定理
前置知识
- 图论基础：顶点、边、度数、连通性、基本圈等概念。建议回顾：图论基础。
- 组合几何直觉：理解"无交叉画图"的几何意义。
- 数学归纳法：Euler 公式的证明依赖归纳基础。
拓扑图论（Topological Graph Theory）研究的是图在几何或拓扑空间中的嵌入问题。它并非对图结构的纯组合描述，而是关心图的节点与边能否以某种"不交叉"的方式嵌入到特定曲面上。这一看似几何的问题，实则是多个工程与理论领域的基础。
三大应用场景
VLSI 芯片设计：芯片上不同逻辑单元之间的连线必须避免交叉。交叉意味着短路或电磁干扰——工程上需要将电路"平面化"（planarization），即在布线前判断给定的连接图能否嵌入平面。
地图着色：四色定理（Four Color Theorem）——任意平面地图相邻区域着色不超过四种——并非一个纯粹的组合命题；它的成立依赖于平面这一拓扑空间的基本性质。
网络拓扑设计：数据中心网络中，交换机之间的物理连线须避免交叉（尤其在 PCB 板级设计中）。
从数学内部看，拓扑图论将图论与拓扑学深刻地联系起来。图的可平面性是一个拓扑不变量（topological invariant）：它不依赖于图画的具体画法，只依赖于图的抽象结构与所嵌入空间的拓扑类型。这种联系使得我们可以用拓扑工具（Euler 示性数、同调论）研究纯组合对象，也使得图论中的深刻定理（如 Robertson–Seymour 定理）获得了拓扑学意义上的解释。
平面图（Planar Graph）
图 $G = (V, E)$ 称为平面图，若存在将 $G$ 画在欧氏平面 $\mathbb{R}^2$ 上的方式，使得所有边仅在端点处相交（即无交叉边）。这样的具体画法称为平面嵌入（planar embedding）。
平面嵌入将平面划分为若干连通区域，每个区域称为面（face），记面数为 $F$。无边界的无限面称为外部面（outer face），其余为内部面。
命题：平面图的度约束
设 $G$ 是简单连通平面图（无平行边、无自环），则
若进一步假设 $G$ 无三角形（即图中不包含 3-圈），则
这两条不等式是 Euler 公式的直接推论，其证明利用了平面图的每个面至少由三条边围成这一事实。
配图：平面图示意图
graph TB
subgraph "平面图示例"
A((V1)) --> B((V2))
A --> C((V3))
B --> C
B --> D((V4))
C --> D
D --> A
end
subgraph "非平面图示例"
E((V1)) --> F((V2))
E --> G((V3))
E --> H((V4))
E --> I((V5))
F --> G
F --> H
F --> I
G --> H
G --> I
H --> I
end
style E fill:#ffcccc
style F fill:#ffcccc
style G fill:#ffcccc
style H fill:#ffcccc
style I fill:#ffcccc
图示说明
左图：简单连通平面图（可嵌入平面，无边交叉）
右图（红色）：$K_5$ 完全图（5 个顶点两两相连，无论如何画必有边交叉，非平面图）
Euler 公式（Euler's Formula）
设 $G$ 为连通平面图，记顶点数为 $V$、边数为 $E$、面数为 $F$，则
这一定理最初由 Euler 于 1750 年观察到，适用于所有凸多面体（如正多面体）——多面体的顶点、边、面正好构成一个连通平面图。其拓扑本质在于：平面（以及球面）的 Euler 示性数（Euler characteristic）为 2。
归纳证明思路
对边数 $E$ 进行数学归纳：
- 基例：$E = 0$ 时，图仅有一个顶点，$F = 1$（外部面），故 $V-E+F = 1-0+1 = 2$。
- 归纳步骤：假设对边数小于 $k$ 的图成立。考虑边数为 $k$ 的图 $G$：
- 若 $G$ 为树（无圈），则 $E = V-1$，此时 $F = 1$，故 $V-E+F = V-(V-1)+1 = 2$。
- 若 $G$ 含圈，取一条非树边 $e$。$G-e$ 的边数为 $k-1$，由归纳假设满足 Euler 公式。在平面上，添加边 $e$ 恰好将一个面分裂为两个面（$F$ 增加 1），故 $V-(E-1)+(F+1) = V-E+F = 2$。
推论：平面图的边数上界
对简单连通平面图 $G$（$V \geq 3$）：$E \leq 3V - 6$。
证明：每个面由至少 3 条边围成，对所有面的边界边计数得到 $2E \geq 3F$（每条边最多被两个面共享）。结合 Euler 公式消去 $F$：
Kuratowski 定理（Kuratowski, 1930）
图 $G$ 是平面图，当且仅当 $G$ 不包含 $K_5$（5 个顶点的完全图）或 $K_{3,3}$（完全二分图）的细分（subdivision）作为子图。
细分（Subdivision）的定义
对图 $G$ 的一条边 $uv$，在边上插入一个度为 2 的新顶点 $w$，并用两条边 $(u,w)$ 和 $(w,v)$ 替换原边，这一操作称为一次细分。反复进行此操作得到的图称为原图的细分（subdivision）。直观地，subdivision 保留图的"连接结构"——在拓扑学中称为同伦等价（homotopy equivalent）。
配图：Kuratowski 障碍图
graph TB
subgraph "K₅ 完全图"
KA(( )) --> KB(( ))
KA --> KC(( ))
KA --> KD(( ))
KA --> KE(( ))
KB --> KC
KB --> KD
KB --> KE
KC --> KD
KC --> KE
KD --> KE
end
subgraph "K₃,₃ 完全二分图"
LA((A1)) --> RA((B1))
LA --> RB((B2))
LA --> RC((B3))
LB((A2)) --> RA
LB --> RB
LB --> RC
LC((A3)) --> RA
LC --> RB
LC --> RC
end
style KA fill:#ffcccc
style KB fill:#ffcccc
style KC fill:#ffcccc
style KD fill:#ffcccc
style KE fill:#ffcccc
style LA fill:#ffcccc
style LB fill:#ffcccc
style LC fill:#ffcccc
style RA fill:#ccccff
style RB fill:#ccccff
style RC fill:#ccccff
图示说明
左图：$K_5$（5 个顶点两两相连，10 条边）
右图：$K_{3,3}$（两组各 3 个顶点，组内无边，组间全连，共 9 条边）
红色顶点：左Part顶点（左组）
蓝色顶点：右Part顶点（右组）
为什么 $K_5$ 和 $K_{3,3}$ 的细分是障碍
从拓扑直观出发，平面的一个基本拓扑性质是：如果一个子图在平面上嵌入时出现交叉，那么在局部"推开"交叉点需要额外的空间。$K_5$ 的问题在于：其 5 个顶点两两相连，共 10 条边——在平面上无论怎么排列，5 个顶点的两两互联，必然导致某些边无法不相交地布设。类似地，$K_{3,3}$ 作为完全二分图，其两侧各 3 个顶点的"全面互联"同样无法在平面上实现。
Kuratowski 定理的深层意义在于：这两个图的细分（而非仅仅是它们本身）是平面性的唯一障碍。换言之，若一个图"隐藏"了 $K_5$ 或 $K_{3,3}$ 的拓扑结构（即通过细分可以展开为这两个图之一），则该图必为非平面图。
Wagner 定理（Wagner, 1937）
图 $G$ 是平面图，当且仅当 $G$ 不包含 $K_5$ 或 $K_{3,3}$ 作为图 minor（graph minor）。
图 minor 定义如下：图 $H$ 是 $G$ 的 minor，指在 $G$ 中可以通过以下操作得到 $H$：
- 删除任意边或顶点；
- 收缩任意边（即合并相邻的两个顶点）。
这与 subdivision 的区别在于：subdivision 只能添加顶点（细分边），而 minor 可以同时删除和收缩边。minor 条件比 subdivision 条件更宽松，但更利于算法处理。
对偶图（Dual Graph）
给定连通平面图 $G$ 的一个平面嵌入，取 $G^*$ 使得：
- $G^*$ 中每个顶点对应 $G$ 的一个面；
- $G^*$ 中每条边对应 $G$ 中相邻两面之间的边界边；
- 若两面共享 $k$ 条边界边，则对应的两个顶点之间有 $k$ 条平行边。
对偶运算满足自反性：$(G^*)^* \cong G$（忽略某些平凡情况如悬挂边）。
配图：对偶图构造
graph TB
subgraph "原图 G（实线）"
G1((f1)) --- G2((f2))
G2 --- G3((f3))
G3 --- G1
G2 --- G4((f4))
end
subgraph "对偶图 G*（虚线）"
D1((v1)) -.-> D2((v2))
D2 -.-> D3((v3))
D3 -.-> D1
D2 -.-> D4((v4))
end
style G1 fill:#e0e0e0
style G2 fill:#e0e0e0
style G3 fill:#e0e0e0
style G4 fill:#e0e0e0
style D1 fill:#ffe0b0
style D2 fill:#ffe0b0
style D3 fill:#ffe0b0
style D4 fill:#ffe0b0
对偶关系说明
灰色顶点：原图 $G$ 的面（f1, f2, f3, f4）
橙色顶点：对偶图 $G^*$ 的顶点（v1, v2, v3, v4），每个对应原图的一个面
虚线：对偶边，连接共享边界的相邻面
对偶图的性质
设 $G$ 是连通平面图，$G^*$ 为其对偶：
- 若 $G$ 是平面图，则 $G^*$ 必为平面图；
- 连通平面图的边数满足：$E(G) = E(G^*)$；
- 对偶图将原图的 Euler 公式映射为自身：$V(G) - E(G) + F(G) = 2$ 的对称结构。
应用：网络流与最短路径
在平面网络（带顶点容量的网络流问题）中，将原图的对偶图构造出来后，从源点到汇点的最小 cut（最小割）恰好对应对偶图中一条从外部面某边界到另一边界的光滑路径（cycle）。这一对偶关系是最大流最小割定理（Max-Flow Min-Cut Theorem）的几何形式表述。
更进一步，Hassin（1981）和 Frederickson（1997）等人的研究表明：对于带非负边权 planar graph 的单源最短路径问题（SSSP），可以通过对偶图转化为在 faces 上寻找最短路径，将时间复杂度优化至 $O(n \log n)$，甚至利用多源并行技术在某些情况下达到线性时间。
亏格（Genus）的概念
平面的亏格（genus）为 0。亏格衡量了曲面的"孔洞数"：
- 球面（sphere）：$g = 0$；
- 环面（torus）：$g = 1$（有一个"洞"）；
- 双环面（double torus）：$g = 2$，依此类推。
图 $G$ 的亏格 $g(G)$ 是使得 $G$ 能够嵌入（无交叉）到曲面 $S_g$ 上的最小整数 $g$，其中 $S_g$ 为亏格为 $g$ 的可定向闭合曲面（orientable closed surface）。
Euler–Poincaré 公式（推广）
设图 $G$ 嵌入在亏格为 $g$ 的曲面上，嵌入将曲面划分为 $F$ 个面，则
等号右侧的 $2 - 2g$ 正是亏格为 $g$ 的可定向曲面的 Euler 示性数（Euler characteristic）。
Heawood 公式（Heawood Conjecture, 1890；Ringel–Youngs, 1968）
若图 $G$ 可以嵌入亏格为 $g \geq 1$ 的曲面，则
该上界被称为 Heawood 数，记作 $H(g)$。
例题：环面上的着色（$g = 1$）
题目：当 $g = 1$（环面）时，求 Heawood 数 $H(1)$，并说明其含义。
- 代入公式：$g = 1$ 代入 $H(g) = \left\lfloor \frac{7 + \sqrt{48g + 1}}{2} \right\rfloor$
- 计算根号：$\sqrt{48 \times 1 + 1} = \sqrt{49} = 7$
- 计算分子：$7 + 7 = 14$
- 除以 2 取整：$\left\lfloor \frac{14}{2} \right\rfloor = \left\lfloor 7 \right\rfloor = 7$
答案：$H(1) = 7$。即环面上的任意地图可以用不超过 7 种颜色着色，且该上界是紧的——环面的七色定理（Heawood, 1890）已被证明，而环面上确实存在需要 7 种颜色的图（典型的六边形网格嵌入）。
当 $g = 0$（平面）时，Heawood 公式给出 $H(0) = 4$，恰好是四色定理的上界（但四色定理的紧性证明更为困难，由 Appel–Haken 于 1976 年借助计算机完成）。
Robertson–Seymour 定理（图 Minor 定理，1983–2004）
设 $\mathcal{F}$ 为一个有限图集合。若一族图 $\mathcal{C}$ 对图 minor 操作封闭（即若 $G \in \mathcal{C}$ 且 $H$ 是 $G$ 的 minor，则 $H \in \mathcal{C}$），则存在一个有限障碍图集合 $\mathcal{F}$，使得
等价表述：有限图在图 minor 关系下构成良拟序（well-quasi-ordering）。
"良拟序"（well-quasi-ordering）指：任意无穷点序列 $G_1, G_2, \ldots$ 中，必存在 $i < j$ 使得 $G_i \preceq_m G_j$（即 $G_i$ 是 $G_j$ 的 minor）。这意味着不可能有无穷的反向下链（no infinite antichain under minors）。
固定参数 Tractability（FPT）
给定图 $G$ 和任意固定图 $H$，可在 $O(f(H) \cdot n^3)$ 或更优时间内判定 $G$ 是否包含 $H$ 作为 minor。这称为 H-Minor 判定问题的 FPT 算法。
其中 $f(H)$ 是仅依赖于 $H$ 的函数，与 $|G|$ 无关。这一结果被 Courcelle 定理（1990）进一步推广：对任意可以通过 monadic second-order logic（MSo）描述的图性质，在 bounded treewidth 图类上的模型检测问题是 FPT 的。
网格定理（Robertson–Seymour, 1992）
存在一个函数 $f: \mathbb{N} \to \mathbb{N}$，使得任意树宽（treewidth）至少为 $f(k)$ 的图都包含一个 $k \times k$ 网格作为 minor。
这条定理建立了图的结构性质（treewidth）与组合障碍（网格 minor）之间的等价关系，是图 minor 理论的核心桥梁之一。
例题 1：判断图的平面性
题目：判断以下两图是否为平面图。
- 完全图 $K_5$：$V = 5$，$E = 10$
- 完全二分图 $K_{3,3}$：$V = 6$，$E = 9$
解析：
- 对于 $K_5$：由 Euler 公式推论，$E \leq 3V - 6 = 3 \times 5 - 6 = 9$。但 $K_5$ 有 $E = 10 > 9$，不满足上界，因此 $K_5$ 必为非平面图。
- 对于 $K_{3,3}$：$K_{3,3}$ 是完全二分图，无三角形（无 3-圈），使用无三角图的推论：$E \leq 2V - 4 = 2 \times 6 - 4 = 8$。但 $K_{3,3}$ 有 $E = 9 > 8$，同样不满足，因此 $K_{3,3}$ 必为非平面图。
答案：两者均为非平面图。这给出了 $K_5$ 和 $K_{3,3}$ 非平面性的第一条简洁证明。
例题 2：应用 Euler 公式
题目：设 $G$ 为简单连通平面图，有 $V = 8$ 个顶点和 $E = 18$ 条边。利用 Euler 公式求面数 $F$，并验证是否满足边数上界。
- 代入 Euler 公式：$V - E + F = 2$ → $8 - 18 + F = 2$ → $F = 12$
- 验证边数上界：对于简单连通平面图，$E \leq 3V - 6$。这里 $3V - 6 = 3 \times 8 - 6 = 18$。而 $E = 18$，恰好等于上界，说明此图是满足条件的临界图（即每个面都是三角形）。
- 验证平均度数：由 handshake lemma，$\sum \deg(v) = 2E = 36$，平均度为 $\frac{36}{8} = 4.5$。这说明图中存在度数为 5 或更高的顶点。
答案：$F = 12$，且此图恰好达到 $E = 3V - 6$ 的上界。
| 应用领域 | 拓扑图论工具 | 解决的问题 |
|---|---|---|
| VLSI 芯片设计 | 平面性判定 | 预估通孔数，优化布线层分配 |
| 网络拓扑设计 | 可平面性算法、对偶图 | 避免 PCB 板级连线交叉，最短路径优化 |
| 地图着色与 GIS | 四色定理、对偶图 | 行政区划图着色算法选择 |
| 图可视化 | 平面图画法（planar drawing） | 层次布局算法 Sugiyama 方法 |
现代 VLSI 芯片布线中，互连线的交叉是必须避免的物理约束。平面化（planarization）通过在金属层之间插入通孔实现层级跨越，但通孔数目直接影响芯片的面积与功耗。拓扑图论提供的平面性判定使得 EDA 工具能在布局阶段预估所需的通孔数，并指导优化算法在平面约束下寻找最优解。
在图绘制（graph drawing）领域，将拓扑图论的条件转化为审美约束：平面图的可嵌入性允许我们使用无交叉的"平面图画法"（planar drawing）展示网络结构，这比一般图画法更易于人类理解。
参考来源
- Kuratowski, K. (1930). Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15, 271–283.
- Diestel, R. (2017). Graph Theory (5th ed.). Graduate Texts in Mathematics, Vol. 173. Springer. 预览链接
- West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall. 第 4 章系统介绍了平面图、Euler 公式与 Kuratowski 定理。
- Robertson, N., & Seymour, P. D. (1983–2004). Graph Minors I–XX. Journal of Combinatorial Theory, Series B. 图 minor 定理的完整系列证明（历时 20 年）。
- Ringel, G., & Youngs, J. W. T. (1968). Solution of the Heawood map-coloring problem. Proceedings of the National Academy of Sciences, 60(2), 438–445.
- Hopcroft, J., & Tarjan, R. (1974). Efficient planarity testing. Journal of the ACM, 21(4), 549–568. 首个线性时间平面性检测算法。
- Appel, K., & Haken, W. (1977). Every planar map is four colorable. Illinois Journal of Mathematics, 21(3), 429–567.
- Hassin, R. (1981). Maximum flow in (s, t) planar networks. Information Processing Letters, 13(3), 107.
复习速查
- 平面图：图 $G = (V, E)$ 可嵌入平面且无边交叉。
- Euler 公式：$V - E + F = 2$（连通平面图）。
- 边数上界：简单连通平面图 $E \leq 3V - 6$；无三角图 $E \leq 2V - 4$。
- Kuratowski 定理：平面图当且仅当不含 $K_5$ 或 $K_{3,3}$ 的细分。
- Wagner 定理：平面图当且仅当不含 $K_5$ 或 $K_{3,3}$ 作为 minor。
- 对偶图：$G^*$ 的顶点对应 $G$ 的面，边对应相邻面的边界。
- Euler–Poincaré 公式：$V - E + F = 2 - 2g$（亏格 $g$ 曲面）。
- Heawood 公式：$\chi(G) \leq \left\lfloor \frac{7 + \sqrt{48g + 1}}{2} \right\rfloor$。