平面图
定义
如果图 能画在平面 上，即除顶点处外无边相交，则称 可平面嵌入 ， 为可平面图或平面图。画出的没有边相交的图称为 的平面表示或平面嵌入。
和 不是平面图。其中， 指的是点数为 的完全图，而 指的是两边各有三个点的完全二分图。
设 是平面图，由 的边将 所在的平面划分成若干个区域，每个区域称为 的一个面，其中面积无限的面称为无限面或外部面，面积有限的称为有限面或内部面。包围每个面的所有边组成的回路称为该面的边界，边界的长度称为该面的次数。
平面图中所有面的次数之和等于边数 的 2 倍。
若在简单平面图 的任意不相邻顶点间添加边，所得图为非平面图，称 为极大平面图。
若 为 阶简单的连通平面图， 为极大平面图当且仅当 的每个面的次数均为 3。
欧拉公式
对于任意的连通的平面图 ，有：
其中，，分别为 的阶数，边数和面数。
推论：对于有 个连通分支的平面图 ，有
可推出其他性质：
设 是连通的平面图，且 的各面的次数至少为 ，则有：
推论：对于有 个连通分支的平面图 ，有
推论：设 是 阶 条边的简单平面图，则
判断
若两个图 与 同构，或通过反复插入或消去 2 度顶点后是同构的，则称二者是同胚的。
库拉图斯基定理
图 是平面图当且仅当 不含与 或 同胚的子图。
图 是平面图当且仅当 中没有可以收缩到 或 的子图。
对偶图
设 是平面图的某一个平面嵌入，构造图 ：
- 在 的每个面 中放置 的一个顶点
- 设 为 的一条边，若 在 的面 和 的公共边界上，做 的边 与 相交，且 关联 的顶点 ，即 ， 不与其他任何边相交。若 为 中桥且在 的边界上，则 是以 中顶点 为端点的环，即
称 为 的对偶图。
性质
- 为平面图，且是平面嵌入。
- 中自环在 中对应桥， 中桥在 中对应自环。
- 是连通的。
- 若 的面 的边界上至少有两条公共边，则关联 的边有平行边， 多半是多重图。
- 同构的图的对偶图不一定是同构的。
- 与 同构当且仅当 是连通图。
应用
平面图最小割转对偶图最短路：BZOJ 1001 狼抓兔子
外平面图
设 为平面图，若 存在平面嵌入 ，使得 中所有顶点都在 的一个面的边界上，则称 为外可平面图，简称外平面图。
设 是简单的外平面图，若对于 中任二不相邻顶点 ，令 ，则 不是外平面图，称 为极大外平面图。
性质
所有顶点都在外部面边界上的 阶外可平面图是极大外可平面图当且仅当 的每个外部面的边界都是长为 3 的圈，外部面的边界是一个长为 的圈。
阶极大外平面图有 个内部面。
设 是 阶极大外平面图，则：
- 中至少有 3 个顶点的度数小于等于 3
- 中至少有 2 个顶点的度数为 2
- 的点连通度 为 2
一个图 是外平面图有当且仅当 中不含与 或 同胚的子图。
任何 4 - 连通平面图都是哈密顿图。
最后更新: 2024年8月2日
创建日期: 2019年1月22日