平面图

一、平面图的基本概念

1.1 平面图的定义

平面图：能把所有的点和边都画在同一个平面上，而且边除了在端点外不会相交的图。

注意：有时看起来不是平面的图，可以重新画成平面图的形式。一个图是否为平面图，取决于其本质结构，而非具体的画法。

1.2 面的概念

面：连通平面图的边所包围起来的区域，且区域中不包含图的结点和边。

无限面（外部面）：在图形之外，不受边界约束的面。

面的边界：包围一个面的各边所构成的回路。

面的次数：面的边界的回路长度（边的数目），记作 $\deg(R)$。

二、平面图的定理

2.1 面的次数定理

定理1：有限平面图中，面的次数之和等于其边数的两倍。

$\sum_{i=1}^{r} \deg(R_i) = 2e$

其中 $r$ 为面数，$e$ 为边数。

注意：此定理与欧拉图无关。

2.2 欧拉公式

定理2（欧拉定理）：连通平面图 $G$，有 $v$ 个结点，$e$ 条边，$r$ 个面，则有：

$v - e + r = 2$

注意：此公式适用于带环、重边的连通平面图。

证明方法：对 $e$（或 $v$、$r$）进行归纳。

2.3 连通简单平面图的边数限制

定理3：连通简单平面图 $G$，共有 $v$ 个结点，$e$ 条边，若 $v \geq 3$，则有：

$e \leq 3v - 6$

推导：此定理强化了欧拉定理的条件——必须是简单图（没有环、重边），所以每一面的次数不小于3，代入欧拉公式，消去面数，得到点与边之间的关系。

用途：

1. 证明一些公式或结论
2. 证明一个图不是平面图（否定连通简单图是平面图的必要条件）

注意：$e \leq 3v - 6$ 是连通简单平面图的必要条件，而非充分条件。满足此条件的图不一定是平面图。

2.4 二分平面图的边数限制

定理4：若连通简单平面图 $G$ 中不存在长度为3的回路（即无三角形），则：

$e \leq 2v - 4$

推导：因为无三角形，每个面的次数至少为4，代入欧拉公式可得。

三、非平面图与库拉托夫斯基定理

3.1 典型的非平面图

$K_5$（5阶完全图）：有5个结点、10条边。若为平面图，则 $e \leq 3v - 6 = 9$，但 $10 > 9$，矛盾。因此 $K_5$ 不是平面图。

$K_{3,3}$（完全二分图）：有6个结点、9条边，不含三角形。若为平面图，则 $e \leq 2v - 4 = 8$，但 $9 > 8$，矛盾。因此 $K_{3,3}$ 不是平面图。

3.2 库拉托夫斯基图

库拉托夫斯基图：$K_5$ 和 $K_{3,3}$ 称为库拉托夫斯基图，是最基本的非平面图。

3.3 库拉托夫斯基定理

定理5（库拉托夫斯基定理）：一个图是平面图，当且仅当它不包含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。

同胚：一个图可以通过在边上插入度为2的顶点（或反过来删除度为2的顶点并合并相邻边）变成另一个图，则称这两个图同胚。

3.4 边收缩

边收缩：将一条边的两个端点合并为一个顶点，删除产生的环和平行边。

推论：一个图是平面图，当且仅当它不包含可以收缩为 $K_5$ 或 $K_{3,3}$ 的子图。

四、平面图的判定方法

4.1 判断平面图的解题思路

是平面图：画出其平面图的形式（边不交叉的画法）。

不是平面图（三种方法）：

• 方法一：连通简单图，不满足 $e \leq 3v - 6$（或 $e \leq 2v - 4$）
• 方法二：包含了库拉托夫斯基图（$K_5$ 或 $K_{3,3}$）的同胚子图
• 方法三：证明经边收缩后，可以变成库拉托夫斯基图

4.2 常见误解

误解：一个图在某种画法下边有交叉，就不是平面图。

正解：边有交叉只是画法问题，一个图是否为平面图取决于能否找到一种边不交叉的画法。需要证明的是不存在这样的画法，而非当前画法有交叉。

五、对偶图与图的着色

5.1 对偶图

定义：在平面图中，用点替代一个面，用边表示两个面之间的相邻关系（即两个面之间有公共边），得到的图叫原图的对偶图。

构造方法：

1. 在每个面内放置一个顶点
2. 若两个面有公共边，则在对应的两个顶点间连一条边
3. 边穿过原图的公共边

5.2 地图着色问题

对于地图的着色问题，可转化为其对偶图的结点着色问题：使邻接的点有不同的颜色。

5.3 四色定理

四色定理：对于任何形状的地图，对相邻的国家着以不同的颜色，只需四种颜色即可。

图论表述：任何平面图的点色数不超过4，即 $\chi(G) \leq 4$。

历史：四色定理由 Haken 和 Appel 通过穷举计算机搜索证明。

六、图的着色

6.1 点着色

正常着色：对图的每个顶点赋予一种颜色，使得相邻的顶点颜色不同。

点色数 $\chi(G)$：对图 $G$ 进行正常着色所需的最少颜色数。

6.2 着色与图的关系

本节小结

• 平面图：能画在平面上且边不交叉的图
• 面：边包围的区域，面的次数为边界回路长度
• 面的次数定理：面的次数之和 = 2 × 边数
• 欧拉公式：$v - e + r = 2$（连通平面图）
• 边数限制：连通简单平面图 $e \leq 3v - 6$；无三角形时 $e \leq 2v - 4$
• $K_5$ 和 $K_{3,3}$：不是平面图（库拉托夫斯基图）
• 库拉托夫斯基定理：平面图当且仅当不包含 $K_5$ 或 $K_{3,3}$ 的同胚子图
• 判定方法：画平面图形式 / 不满足边数限制 / 包含库拉托夫斯基子图 / 边收缩
• 对偶图：用点替代面，用边表示面的相邻关系
• 四色定理：任何平面图点色数不超过4

关键术语速查

思考题

题目：证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。

提示：利用握手定理和 $e \leq 3v - 6$ 条件。

练习题

练习1：平面图判定

题目：判断以下图是否为平面图：

(1) $K_5$（5阶完全图，5个顶点，10条边）

(2) $K_{3,3}$（完全二分图，6个顶点，9条边）

(3) 6个顶点、12条边的简单连通图

解：

(1) 若 $K_5$ 是平面图，则 $e \leq 3v - 6 = 3 \times 5 - 6 = 9$，但 $e = 10 > 9$，矛盾。不是平面图。

(2) $K_{3,3}$ 是二分图，不含三角形，若为平面图则 $e \leq 2v - 4 = 2 \times 6 - 4 = 8$，但 $e = 9 > 8$，矛盾。不是平面图。

(3) 若为平面图，则 $e \leq 3v - 6 = 3 \times 6 - 6 = 12$。$e = 12$ 恰好等于上界，满足必要条件，但必要条件不是充分条件，不能确定，需要进一步分析（可能需要检查是否包含 $K_5$ 或 $K_{3,3}$ 的同胚子图）。

练习2：欧拉公式应用

题目：连通平面图有6个顶点、10条边，求面的个数。

解：由欧拉公式 $v - e + r = 2$：

$6 - 10 + r = 2$，解得 $r = 6$。

该图有6个面（包括无限面）。

练习3：点色数求解

题目：求以下图的点色数 $\chi(G)$：

(1) 5阶完全图 $K_5$

(2) 长度为6的圈 $C_6$

(3) 长度为5的圈 $C_5$

(4) 零图（无边的图）

解：

(1) $K_5$ 中任意两个顶点相邻，每个顶点需要不同颜色。$\chi(K_5) = 5$。

(2) $C_6$ 是偶圈，可用2种颜色交替着色。$\chi(C_6) = 2$。

(3) $C_5$ 是奇圈，2种颜色不够（首尾相邻会冲突），需要3种。$\chi(C_5) = 3$。

(4) 零图无边，所有顶点互不相邻，只需1种颜色。$\chi(G) = 1$。