跳转至

平面图

定义

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

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论