平面图

定义

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

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments