平面图

定义

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

$K_{3,3}$ 和不是平面图。其中，指的是点数为的完全图，而 $K_{3,3}$ 指的是两边各有三个点的完全二分图。

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

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

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

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

欧拉公式

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

其中，，分别为的阶数，边数和面数。

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

可推出其他性质：

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

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

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

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

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

判断

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

库拉图斯基定理

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

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

对偶图

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

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

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

性质

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

应用

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

外平面图

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

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

性质

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

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

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

中至少有 3 个顶点的度数小于等于 3
中至少有 2 个顶点的度数为 2
的点连通度 $\kappa$ 为 2

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

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

本页面最近更新：2024/8/2 18:28:30，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：AlphaDrawer, Enter-tainer, HeRaNO, Ir1d
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用