平面图

平面图的基本概念

面：由 $G$ 的平面嵌入所分割出的区域称为面。
- 无限面或外部面：无穷大的面。用 $R_0$ 表示。
- 有限面或内部面：有限大的面。用 $R_1, R_2, \cdots$ 表示。
边界：面 $R_i$ 是包围它的边的组成的回路组。
次数：面 $R_i$ 的次数是与边界的长度，即边数，记作 $deg(R_i)$。

在平面图中，各面的次数之和等于边数的两倍。 $$\sum_{i=1}^{n} deg(R_i) = 2m$$

极大平面图：在平面图 $G$ 中再加一条边，就会使 $G$ 变成非平面图的图称为极大平面图。

极大平面图是连通的，且 $n(n \geq 3)$ 阶极大平面图中不可能有割点和桥。

$G$ 为 $n(n \geq 3)$ 阶极大平面图当且仅当 $G$ 是简单平面图，且 $G$ 的每个面的次数都为 $3$。

极小非平面图：在非平面图 $G$ 中去掉一条边，就会使 $G$ 变成平面图的图称为极小非平面图。

极小非平面图必为简单图。

设 $G$ 是一个 $n$ 阶 $m$ 条边 $r$ 个面的连通平面图，则 $$n - m + r = 2$$

若 $G$ 为 $k$ 个连通分支的平面图，则 $$n - m + r = k + 1$$

由握手定理可得，对于联通的平面图，有 $$m \leq \frac{l}{l-2}(n-2)$$ $$m \leq \frac{l}{l-2}(n-k-1)$$ 其中 $l = min\lbrace deg(R_i) \rbrace$。

证明： $$2m = \sum_{i=1}^{r} deg(R_i) \geq r \cdot l \geq (n - k - 1) \cdot l$$

根据握手定理和极大平面图的性质，可得设 $G$ 为 $n$ 阶 $m$ 条边的极大平面图，则 $$m = 3n - 6$$

若 $G$ 为 $n(n \geq 3)$ 阶 $m$ 条边的简单平面图，则 $$m \leq 3n - 6$$ 注意，此推论为简单平面图的必要条件，不是充分条件。

设 $G$ 为简单平面图，则 $$\delta(G) \leq 5$$ 用反证法证明。

插入 $2$ 度顶点：设 $e = (u, v)$ 为 $G$ 的一条边，$u$ 与 $v$ 之间插入一个顶点 $w$，并将 $e$ 替换为 $(u, w)$ 和 $(w, v)$ 两条边，称作在 $G$ 中插入 $2$ 度顶点 $w$。
消去 $2$ 度顶点：设 $w$ 为 $G$ 的一个 $2$ 度顶点，$w$ 与 $u$ 和 $v$ 相连，将 $w$ 与 $u$ 和 $v$ 相连的两条边替换为一条边 $e = (u, v)$，并删除 $w$，称作在 $G$ 中消去 $2$ 度顶点 $w$。

若 $G_1$ 与 $G_2$ 在反复进行插入 $2$ 度顶点和消去 $2$ 度顶点的操作后同构，则称 $G_1$ 与 $G_2$ 同胚。

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

$G$ 的每个面 $R_i$ 对应 $G^*$ 的一个顶点 $v_i$。
$G$ 的每条边对应 $G^*$ 的一条边。即若 $e$ 是 $R_i$ 和 $R_j$ 的边界，则 $v_i$ 和 $v_j$ 之间有一条边。
- 若 $e$ 是 $R_i$ 的边界且是桥，即 $e$ 只属于 $R_i$，则 $v_i$ 与自身有一条边。

$G^*$ 是 $G$ 的对偶图，则

若 $G^* \cong G$，则称 $G$ 是自对偶图。

轮图定义如下：在 $C_{n-1}$（$n \geq 4$）边形内放置一个顶点，使得这个顶点与 $C_{n-1}$ 上的所有顶点均相邻。所得的 $n$ 阶简单图称为 n阶轮图，常记为 $W_n$。

轮图是自对偶图