平面图

平面图的基本概念

平面图：若能将无向图 $G$ 无边相交地画在平面上，称 $G$ 为平面图或可平面图。
平面嵌入：画出的无边相交的平面图称为平面嵌入。
非平面图：不能画出无边相交的平面图的图称为非平面图。

面与次数

面：由 $G$ 的平面嵌入所分割出的区域称为面。
- 无限面或外部面：无穷大的面。用 $R_{0}$ 表示。
- 有限面或内部面：有限大的面。用 $R_{1}, R_{2}, \dots$ 表示。
边界：面 $R_{i}$ 是包围它的边的组成的回路组。
次数：面 $R_{i}$ 的次数是与边界的长度，即边数，记作 $d e g (R_{i})$ 。

握手定理

在平面图中，各面的次数之和等于边数的两倍。

\sum_{i = 1}^{n} d e g (R_{i}) = 2 m

极大平面图

极大平面图：在平面图 $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 = m i n {d e g (R_{i})}$ 。

证明：

2 m = \sum_{i = 1}^{r} d e g (R_{i}) \geq r \cdot l \geq (n - k - 1) \cdot l

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

m = 3 n - 6

若 $G$ 为 $n (n \geq 3)$ 阶 $m$ 条边的简单平面图，则

m \leq 3 n - 6

注意，此推论为简单平面图的必要条件，不是充分条件。

设 $G$ 为简单平面图，则

δ (G) \leq 5

用反证法证明。

平面图的判断

插入 $2$ 度顶点与消去 $2$ 度顶点

插入 $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$ 。

$插入2度顶点与消去2度顶点$

同胚

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

平面图判定定理

$G$ 是平面图 $\Leftrightarrow$ $G$ 不含同胚于 $K_{5}$ 或 $K_{3, 3}$ 的子图。
$G$ 是平面图 $\Leftrightarrow$ $G$ 中无可收缩的 $K_{5}$ 或 $K_{3, 3}$ 子图。

平面图的对偶图

设 $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^{*}$ 也是平面图，且是平面嵌入。
$G^{*}$ 是连通图。
若 $G$ 是连通图，则 $G^{*^{*}} ≅ G$ 。
$G$ 中的环对应 $G^{*}$ 中的桥， $G$ 中的桥对应 $G^{*}$ 中的环。
$n^{*} = r, m^{*} = m, r^{*} = n - k + 1$ 。
设 $G^{*}$ 中的顶点 $v_{i}^{*}$ 位于 $G$ 的面 $R_{i}$ 的内部，则 $d (v_{i}^{*}) = d e g (R_{i})$ 。

若 $G^{*} ≅ G$ ，则称 $G$ 是自对偶图。

轮图

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

当 $n$ 为奇数时，称为 奇阶轮图。
当 $n$ 为偶数时，称为 偶阶轮图。

轮图是自对偶图

平面图 ​

平面图的基本概念 ​

面与次数 ​

握手定理 ​

极大平面图 ​

极大平面图的性质 ​

极小非平面图 ​

欧拉公式 ​

欧拉公式的推论 ​

平面图的判断 ​

插入 2 度顶点与消去 2 度顶点 ​

同胚 ​

平面图判定定理 ​

平面图的对偶图 ​

对偶图的性质 ​

轮图 ​

平面图