LinhoNotes

外观

平面图 学习笔记 ​

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

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

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

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

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

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

欧拉公式 ​

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

n−m+r=2

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

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

n−m+r=p+1

可推出其他性质：

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

m≤ll−2(n−2)

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

m≤ll−2(n−p−1)

推论：设 G 是 n≥3 阶 m 条边的简单平面图，则 m≤3n−6

判断 ​

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

库拉图斯基定理 ​

图 G 是平面图当且仅当 G 不含与 K5 或 K3,3 同胚的子图。

图 G 是平面图当且仅当 G 中没有可以收缩到 K5 或 K3,3 的子图。

对偶图 ​

设 G 是平面图的某一个平面嵌入，构造图 G∗：

  1. 在 G 的每个面 Ri 中放置 G∗ 的一个顶点 vi∗
  2. 设 e 为 G 的一条边，若 e 在 G 的面 Ri 和 Rj 的公共边界上，做 G∗ 的边 e∗ 与 e 相交，且 e∗ 关联 G∗ 的顶点 vi∗,vj∗，即 e∗=(vi∗,vj∗)，e∗ 不与其他任何边相交。若 e 为 G 中桥且在 Ri 的边界上，则 e∗ 是以 Ri 中顶点 vi∗ 为端点的环，即 e∗=(vi∗,vi∗)

称 G∗ 为 G 的对偶图。

性质 ​

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

应用 ​

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

外平面图 ​

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

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

性质 ​

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

n(n≥3) 阶极大外平面图有 n−2 个内部面。

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

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

一个图 G 是外平面图有当且仅当 G 中不含与 K4 或 K2,3 同胚的子图。

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