

平面图

定义

如果图 $G$ 能画在平面 $S$ 上，即除顶点处外无边相交，则称 $G$ 可平面嵌入 $S$ ， $G$ 为可平面图或平面图。画出的没有边相交的图称为 $G$ 的平面表示或平面嵌入。

$K_{3,3}$ 和 $K_5$ 不是平面图。

设 $G$ 是平面图，由 $G$ 的边将 $G$ 所在的平面划分成若干个区域，每个区域称为 $G$ 的一个面，其中面积无限的面称为无限面或外部面，面积有限的称为有限面或内部面。包围每个面的所有边组成的回路称为该面的边界，边界的长度称为该面的次数。

平面图中所有面的次数之和等于边数 $m$ 的 2 倍。

若在简单平面图 $G$ 的任意不相邻顶点间添加边，所得图为非平面图，称 $G$ 为极大平面图。

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

欧拉公式

对于任意的连通的平面图 $G$ ，有：

$n-m+r=2$

其中， $n, m, r$ ，分别为 $G$ 的阶数，边数和面数。

推论：对于有 $p (p \geq 2)$ 个连通分支的平面图 $G$ ，有

$n-m+r=p+1$

可推出其他性质：

设 $G$ 是连通的平面图，且 $G$ 的各面的次数至少为 $l(l \geq 3)$ ，则有：

$m \leq \frac{l}{l-2}(n-2)$

推论：对于有 $p (p \geq 2)$ 个连通分支的平面图 $G$ ，有

$m \leq \frac{l}{l-2}(n-p-1)$

推论：设 $G$ 是 $n \geq 3$ 阶 $m$ 条边的简单平面图，则 $m \leq 3n-6$

判断

若两个图 $G_1$ 与 $G_2$ 同构，或通过反复插入或消去 2 度顶点后是同构的，则称二者是同胚的。

库拉图斯基定理

图 $G$ 是平面图当且仅当 $G$ 不含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。

图 $G$ 是平面图当且仅当 $G$ 中没有可以收缩到 $K_5$ 或 $K_{3,3}$ 的子图。

对偶图

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

1. 在 $G$ 的每个面 $R_i$ 中放置 $G^{*}$ 的一个顶点 $v_i^{*}$
2. 设 $e$ 为 $G$ 的一条边，若 $e$ 在 $G$ 的面 $R_i$ 和 $R_j$ 的公共边界上，做 $G^{*}$ 的边 $e^{*}$ 与 $e$ 相交，且 $e^*$ 关联 $G^{*}$ 的顶点 $v_i^*, v_j^*$ ，即 $e^*=(v_i^*, v_j^*)$ ， $e^*$ 不与其他任何边相交。若 $e$ 为 $G$ 中桥且在 $R_i$ 的边界上，则 $e^*$ 是以 $R_i$ 中顶点 $v_i^*$ 为端点的环，即 $e^*=(v_i^*,v_j^*)$

称 $G^{*}$ 为 $G$ 的对偶图。

性质

1. $G^{*}$ 为平面图，且是平面嵌入。
2. $G$ 中自环在 $G^{*}$ 中对应桥， $G$ 中桥在 $G^{*}$ 中对应自环。
3. $G^{*}$ 是连通的。
4. 若 $G$ 的面 $R_i, R_j$ 的边界上至少有两条公共边，则关联 $v_i^*, v_j^*$ 的边有平行边， $G^*$ 多半是多重图。
5. 同构的图的对偶图不一定是同构的。
6. $G^{**}$ 与 $G$ 同构当且仅当 $G$ 是连通图。

应用

平面图最小割转对偶图最短路：BZOJ 1001 狼抓兔子

外平面图

设 $G$ 为平面图，若 $G$ 存在平面嵌入 $\tilde{G}$ ，使得 $G$ 中所有顶点都在 $\tilde{G}$ 的一个面的边界上，则称 $G$ 为外可平面图，简称外平面图。

设 $G$ 是简单的外平面图，若对于 $G$ 中任二不相邻顶点 $u, v$ ，令 $G'=G \cup (u, v)$ ，则 $G'$ 不是外平面图，称 $G$ 为极大外平面图。

性质

所有顶点都在外部面边界上的 $n (n \geq 3)$ 阶外可平面图是极大外可平面图当且仅当 $G$ 的每个外部面的边界都是长为 3 的圈，外部面的边界是一个长为 $n$ 的圈。

$n (n \geq 3)$ 阶极大外平面图有 $n-2$ 个内部面。

设 $G$ 是 $n (n \geq 3)$ 阶极大外平面图，则：

1. $m=2n-3$
2. $G$ 中至少有 3 个顶点的度数小于等于 3
3. $G$ 中至少有 2 个顶点的度数为 2
4. $G$ 的点连通度 $\kappa$ 为 2

一个图 $G$ 是外平面图有当且仅当 $G$ 中不含与 $K_4$ 或 $K_{2,3}$ 同胚的子图。

任何 4 - 连通平面图都是哈密顿图。

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论