平面图

定义

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

不是平面图。

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

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

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

阶简单的连通平面图, 为极大平面图当且仅当 的每个面的次数均为 3。

欧拉公式

对于任意的连通的平面图 ,有:

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

推论:对于有 个连通分支的平面图 ,有

可推出其他性质:

是连通的平面图,且 的各面的次数至少为 ,则有:

推论:对于有 个连通分支的平面图 ,有

推论:设 条边的简单平面图,则

判断

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

库拉图斯基定理

是平面图当且仅当 不含与 同胚的子图。

是平面图当且仅当 中没有可以收缩到 的子图。

对偶图

是平面图的某一个平面嵌入,构造图

  1. 的每个面 中放置 的一个顶点
  2. 的一条边,若 的面 的公共边界上,做 的边 相交,且 关联 的顶点 ,即 不与其他任何边相交。若 中桥且在 的边界上,则 是以 中顶点 为端点的环,即

的对偶图。

性质

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

应用

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

外平面图

为平面图,若 存在平面嵌入 ,使得 中所有顶点都在 的一个面的边界上,则称 为外可平面图,简称外平面图。

是简单的外平面图,若对于 中任二不相邻顶点 ,令 ,则 不是外平面图,称 为极大外平面图。

性质

所有顶点都在外部面边界上的 阶外可平面图是极大外可平面图当且仅当 的每个外部面的边界都是长为 3 的圈,外部面的边界是一个长为 的圈。

阶极大外平面图有 个内部面。

阶极大外平面图,则:

  1. 中至少有 3 个顶点的度数小于等于 3
  2. 中至少有 2 个顶点的度数为 2
  3. 的点连通度 为 2

一个图 是外平面图有当且仅当 中不含与 同胚的子图。

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