平面图

定义¶

如果图 \(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^{*}\)：

在 \(G\) 的每个面 \(R_i\) 中放置 \(G^{*}\) 的一个顶点 \(v_i^{*}\)
设 \(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\) 的对偶图。

\(G^{*}\) 为平面图，且是平面嵌入。
\(G\) 中自环在 \(G^{*}\) 中对应桥，\(G\) 中桥在 \(G^{*}\) 中对应自环。
\(G^{*}\) 是连通的。
若 \(G\) 的面 \(R_i, R_j\) 的边界上至少有两条公共边，则关联 \(v_i^*, v_j^*\) 的边有平行边，\(G^*\) 多半是多重图。
同构的图的对偶图不一定是同构的。
\(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)\) 阶极大外平面图，则：

一个图 \(G\) 是外平面图有当且仅当 \(G\) 中不含与 \(K_4\) 或 \(K_{2,3}\) 同胚的子图。

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