跳到主要内容

平面图

定义​

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

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

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

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

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

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

欧拉公式​

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

n−m+r=2n-m+r=2

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

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

n−m+r=p+1n-m+r=p+1

可推出其他性质：

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

m≤ll−2(n−2)m \leq \frac{l}{l-2}(n-2)

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

m≤ll−2(n−p−1)m \leq \frac{l}{l-2}(n-p-1)

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

判断​

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

库拉图斯基定理​

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

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

对偶图​

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

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

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

性质​

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

应用​

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

外平面图​

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

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

性质​

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

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

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

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

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

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

中等 (500)