跳转至

平面图

定义

如果图 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 - 连通平面图都是哈密顿图。


评论