平面图

基本概念

如果能把图 $G$ 画在平面上，使得除顶点外边与边之间没有交叉，称 $G$ 可以嵌入平面，或称 $G$ 是可平面图。可平面图 $G$ 的边不交叉的一种画法称为 $G$ 的一种平面嵌入， $G$ 的平面嵌入表示的图称为平面图。

非平面图：无平面嵌入的无向图。

结论：

面：由 $G$ 的平面嵌入的边将平面划分成的区域。无限面（外部面）面积无限，有限面（内部面）面积有限。

面的边界是包围该面的回路组。面的次数是边界的长度，记作 $de g (R)$ 。

定理：平面图各面次数之和等于边数的两倍，即 $\sum de g (R_{j}) = 2 m$ 。

欧拉公式：设 $G = (n, m)$ 是连通平面图， $r$ 是 $G$ 的面数，则： $n - m + r = 2$

推广：设 $G$ 是具有 $r$ 个面、 $k$ 个连通分支的平面图，则： $n - m + r = k + 1$

推论：

设 $G$ 是具有 $n$ 个点 $m$ 条边 $r$ 个面的连通平面图，若对 $G$ 的每个面有 $de g (R) \geq l \geq 3$ ，则 $m \leq l (n - 2) / (l - 2)$ 。
设 $G$ 是具有 $n$ 个点 $m$ 条边的简单平面图，则 $m \leq 3 n - 6$ 。
设 $G$ 是具有 $n$ 个点 $m$ 条边的简单平面图，则 $δ (G) \leq 5$ 。

定义：若在简单平面图 $G$ 中的任意两个不相邻的顶点之间加一条新边所得图为非平面图，则称 $G$ 为极大平面图。 $K_{1}, K_{2}, K_{3}, K_{4}$ 都是极大平面图。

性质：

推论：设 $G$ 是 $n$ 个点、 $m$ 条边、 $r$ 个面的极大平面图，且 $n \geq 3$ ，则 $m = 3 n - 6$ ， $r = 2 n - 4$ 。

同胚：若 $G_{1} ≅ G_{2}$ ，或反复插入或消去 $2$ 度顶点后 $G_{1} ≅ G_{2}$ ，则称 $G_{1}$ 与 $G_{2}$ 同胚。

库拉托夫斯基定理：图 $G$ 是可平面的当且仅当它不含 $K_{5}$ 或 $K_{3, 3}$ 同胚的子图。

等价叙述：图 $G$ 是非可平面的当且仅当它含有 $K_{5}$ 或 $K_{3, 3}$ 同胚的子图。

瓦格纳定理：简单图 $G$ 是可平面图当且仅当它不含有可收缩到 $K_{5}$ 或 $K_{3, 3}$ 的子图。

块：没有割点的连通图。若 $∣ V (G) ∣ \geq 3$ ，则 $G$ 是块当且仅当 $G$ 无环且任意两顶点位于同一圈上。

定理：点 $v$ 是图 $G$ 的割点当且仅当 $v$ 至少属于 $G$ 的两个不同的块。

定理：图 $G$ 是可平面图当且仅当它的基础简单图是可平面的，且图 $G$ 是可平面图当且仅当 $G$ 的每个块是可平面图。

设 $G$ 是某平面图的某个平面嵌入，构造 $G$ 的对偶图 $G^{*}$ 如下：

在 $G$ 的面 $R_{i}$ 中放置 $G^{*}$ 的顶点 $v_{i}^{*}$ 。
设 $e$ 为 $G$ 的任意一条边。若 $e$ 在 $G$ 的面 $R_{i}$ 与 $R_{j}$ 的公共边界上，做 $G^{*}$ 的边 $e^{*}$ 与 $e$ 相交，且 $e^{*}$ 关联 $G^{*}$ 的位于 $R_{i}$ 与 $R_{j}$ 中的顶点 $v_{i}^{*}$ 与 $v_{j}^{*}$ 。
若 $e$ 为 $G$ 中的桥且在面 $R_{i}$ 的边界上，则 $e^{*}$ 是以 $R_{i}$ 中 $G^{*}$ 的顶点 $v_{i}^{*}$ 为端点的环。