1. 平面图简介
在本文中，我们将介绍平面图（Planar Graph）的基本概念及其关键性质。这类图结构在图论中非常重要，尤其在地图着色、电路布线等实际问题中具有广泛应用。
2. 平面图定义
平面图是指可以绘制在平面上，使得其边（edges）仅在端点处相交的图。 这种无交叉的绘制方式称为平面嵌入（planar embedding）或平面图表示（plane graph）。
注意区分两个概念：
- 平面图（Planar Graph）：可以被绘制为平面嵌入的图，但当前可能不是无交叉的表示。
- 平面图表示（Plane Graph）：已经绘制在平面上，且边之间没有交叉。
举个例子：
上图中：
是一个平面图，但不是平面图表示（因为边有交叉）。
是一个平面图表示（边无交叉）。- 由于 与 同构（isomorphic），因此它是平面图。
2.1. 同构性（Isomorphism）
形式上：一个平面图与某个平面图表示是同构的。
两个图 
和 
同构，当且仅当存在一个一一映射 
，使得：
例如：
这三个图彼此同构。左上角和下方的图使用恒等映射（即 
），右上角的图使用如下映射：
3. 平面图的性质
下面是一些平面图的重要特性。
3.1. 面（Faces）
在平面图中，图的边将平面划分为多个区域，这些区域称为面（faces）。每个面由图中的边和顶点构成其边界。
例如：
图中展示了三个面 
、
和 
，它们的度数（degree）均为 3。
此外，每个平面图都有一个外部面（exterior face），即无限大的区域。
3.2. 色数（Chromatic Number）
根据四色定理：
✅ 任何平面图的色数不超过 4。
也就是说，最多只需要四种颜色就可以给图的顶点着色，使得任意两个相邻顶点颜色不同。
例如：
该图的色数为 4。
3.3. 判断一个图是否为平面图
我们可以使用以下性质来判断一个图是否为平面图：
- 若一个连通平面图有
条边、
个面，则 
- 若一个连通平面图有
个顶点、 条边、 个面，则 
（欧拉公式） - 若一个连通平面图有 个顶点、 条边，则
- 完全图
是平面图 ⇔ 
- 完全二分图
是平面图 ⇔ 
或 
- 一个图是平面图 ⇔ 它不包含与
或 
同胚的子图。
⚠️ 这些条件中，前三个只是必要条件，不能单独用于判断图是平面图。换句话说，满足这些条件的图可能是非平面图。
✅ 第六条是充分必要条件（Kuratowski 定理），是判断图是否为平面图的核心依据。
3.4. 非平面图（Non-Planar Graphs）
非平面图无法在平面上绘制而不出现边交叉。
两个经典的非平面图是：
- 完全图
- 完全二分图
例如：
这两个图是判断非平面图的基础，任何非平面图都包含与它们同胚的子图。
4. 小结
平面图是图论中的重要概念，其核心特征是可以在平面上无交叉地绘制。我们介绍了：
- 平面图和平面图表示的区别
- 同构性的定义
- 平面图的几个关键性质（如面、色数、欧拉公式等）
- 判断图是否为平面图的依据（特别是 Kuratowski 定理）
✅ 判断一个图是否为平面图的关键是：是否包含与 或 同胚的子图。
这为我们后续在算法设计、图绘制、地图着色等领域的应用打下了基础。