平面图

如果能把图 $G$ 画在平面上，使得除顶点外，边与边之间没有交叉，称 $G$ 可嵌入平面，或称 $G$ 是可平面图。

可平面图 $G$ 的边不交叉的一种画法，称为 $G$ 的一种平面嵌入， $G$ 的平面嵌入表示的图称为平面图。

可平面图概念和平面图概念有时可以等同看待；

图的平面性问题主要涉及如下几个方面：

平面图的性质
平面图的判定
平面嵌入方法(平面性算法)
涉及图的平面性问题的拓扑不变量

平面图的性质¶

一个平面图 $G$ 把平面分成若干连通片，这些连通片称为 $G$ 的区域，或 $G$ 的一个面。$G$ 的面组成的集合用 $\Phi$ 表示。

面积有限的区域称为平面图 $G$ 的内部面，否则称为 $G$ 的外部面。

在 $G$ 中，顶点和边都与某个给定区域关联的子图，称为该面的边界。某面 $f$ 的边界中含有的边数 (割边计算 2 次) 称为该面 $f$ 的次数, 记 $\deg f$。

平面图的次数公式¶

设 $G=(n,m)$ 是平面图，则：

\[ \sum_{f\in\Phi}\deg(f)=2m \]

证明：

对 $G$ 的任意一条边 $e$, 如果 $e$ 是某面割边，那么由面的次数定义，该边给 $G$ 的总次数贡献 2 次；如果 $e$ 不是割边，那么，它必然是两个面的公共边，因此，由面的次数定义，它也给总次数贡献 2 次。

连通平面图的欧拉公式¶

设 $G=(n,m)$ 是连通平面图，$\varphi$ 是 $G$ 的面数，则：

\[ n-m+\varphi=2 \]

证明：

情形 1，如果 $G$ 是树。

那么 $m=n-1$, $𝜑=1$。在这种情况下，容易验证，定理中的恒等式是成立的。

情形 2， $G$ 不是树的连通平面图。

假设在这种情形下，欧拉恒等式不成立。则存在一个含有最少边数的连通平面图 $G$，使得它不满足欧拉恒等式。设这个最少边数连通平面图 $G=(n,m)$，面数为 $𝜑$，则：

\[ n-m+\varphi\neq2 \]

因为 $G$ 不是树，所以存在非割边 $e$。显然，$G-e$ 是连通平面图，边数为 $m-1$，顶点数为 $n$，面数为 $𝜑-1$。由最少性假设，$G-e$ 满足欧拉等式：

\[ \begin{aligned} n-(m-1)+(\varphi-1)&=2\\ n-m+\varphi&=2 \end{aligned} \]

于是矛盾，假设不成立。

非连通平面图的欧拉公式¶

设 $G=(n,m)$ 是 $k$ 个连通分支的平面图，$\varphi$ 是 $G$ 的面数，则：

\[ n-m+\varphi=k+1 \]

证明：

对第 $i(1≤i≤k)$ 个分支来说，设顶点数为 $n_i$，边数为 $m_i$，面数为 $𝜑_i$，由欧拉公式：

\[ \begin{aligned} n_i-m_i+\varphi_i&=2\\ \sum_{i=1}^{k}(n_i-m_i+\varphi_i)&=2k\\ \sum_{i=1}^{k}n_i-\sum_{i=1}^{k}m_i+\sum_{i=1}^{k}\varphi_i&=2k \end{aligned} \]

同时：（扣除重复计算的 $k-1$ 个外部面）

\[ \sum_{i=1}^{k}n_i=n,\ \ \sum_{i=1}^{k}m_i=m,\ \ \sum_{i=1}^{k}\varphi_i=\varphi+k-1 \]

于是得到：

\[ \begin{aligned} n-m+(\varphi+k-1)&=2k\\ n-m+\varphi&=k+1 \end{aligned} \]

设 $G$ 是具有 $n$ 个点 $m$ 条边 $𝜑$ 个面的连通平面图，如果对 $G$ 的每个面 $f$，有 $\deg f≥l≥3$，则：

\[ m\leq\frac{l}{l-2}(n-2) \]

Warning

这是连通平面图的必要条件，不是充分条件！

设 $G$ 是具有 $n$ 个点 $m$ 条边 $𝜑$ 个面的连通平面图，有：

\[ m\leq3n-6 \]

设 $G$ 是具有 $n$ 个点 $m$ 条边 $𝜑$ 个面的连通平面图，如果对 $G$ 的每个面 $f$，有 $\deg f=l$，则：

\[ m(l-2)=l(n-2) \]

设 $G$ 是具有 $n$ 个点 $m$ 条边 $𝜑$ 个面的连通平面图，有：

\[ \delta\leq5 \]

Abstract

该结论是证明“5 色定理”的出发点

一个连通平面图是 $2$ 连通的，当且仅当它的每个面的边界是圈。

图的嵌入性问题¶

曲面嵌入¶

球面嵌入¶

$G$ 可球面嵌入与 $G$ 可平面嵌入等价。

我们实际上对图的嵌入性问题也只考虑这两个。

环面嵌入¶

略

定向曲面嵌入¶

略

3 维空间嵌入¶

所有图均可嵌入 $R^3$ 中。

凸多面体与平面图¶

一个多面体称为凸多面体，如果在体上任取两点，其连线均在体上。

凸多面体的一维骨架：把一个凸多面体压缩在平面上，得到一个对应的平面图，该平面图称为该凸多面体的一维骨架。

存在且只存在 5 种正多面体：它们是正四、六、八、十二、二十面体

平面图的判定¶

同胚¶

在图 $G$ 的边上插入一个新的 $2$ 度顶点，使一条边分成两条边，则称将图 $G$ 在 2 度顶点内扩充；
去掉图的一个 $2$ 度顶点，使这个 $2$ 度顶点关联的两条边合成一条边，则称将 $G$ 在 2 度顶点内收缩

两个图 $G_1$ 和 $G_2$，如果 $G_1\cong G_2$，或者通过反复在 $2$ 度顶点内扩充和收缩它们能变成同构的，则称 $G_2$ 和 $G_2$ 是同胚的，或 $G_1$ 和 $G_2$ 在 $2$ 度顶点内是同构的

图的可平面性在同胚意义下不变。

库拉托夫斯基定理¶

图 $G$ 是可平面的当且仅当它不含与 $K_5$ 或 $K_{3,3}$ 同胚的子图

库拉托夫斯基定理可以等价叙述为：「图 $G$ 是非可平面的当且仅当它含有与 $K_5$ 或 $K_{3,3}$ 同胚的子图」

给定图 $G$，去掉 $G$ 中的环 (若有的话)，将 $G$ 中的重边 (若有的话) 用单边代替，称这样所得的图为 $G$ 的基础简单图

图 $G$ 是可平面图当且仅当其基础简单图是可平面图
图 $G$ 是可平面图当且仅当它的每个块是可平面图

初等收缩¶

设 $uv$ 是简单图 $G$ 的一条边。去掉该边，重合其端点，再删去由此产生的环和重边。这一过程称为图 $G$ 的初等收缩或收缩边 $uv$ 的运算，并记所得之图为 $G/uv$。

一个图 $G$ 可收缩到 $H$，是指 $H$ 可从 $G$ 通过一系列初等收缩而得到。

瓦格纳定理¶

简单图 $G$ 是可平面图当且仅当它不含可收缩到 $K_5$ 或 $K_{3,3}$ 的子图。

该定理和库拉托夫斯基定理是等价的。

至少有 9 个点的简单可平面图的补图是不可平面的，而 9 是这种数目中最小的一个

平面性的拓扑不变量¶

亏格¶

环柄¶

在边交叉处建立的“立交桥”，通过环柄使得一条边经过“桥下”，另一条边经过“桥上”，使二者分开。

亏格定义¶

若通过加上 $k$ 个环柄可将图 $G$ 嵌入球面，则 $k$ 得最小值称为 $G$ 的亏格，记为：

\[ \gamma(G) \]

若 $G$ 是可平面图，则 $\gamma(G)=0$；
同胚的图是亏格相等；
$\gamma(K_5)=1$；

引入亏格的欧拉公式¶

对一个亏格为 $\gamma$，有 $n$ 个顶点，$m$ 条边和 $\varphi$ 个面的多面体或连通图，有：

\[ n-m+\varphi=2-2\gamma \]

结论¶

$G$ 是一个有 $n$ 个顶点，$m$ 条边和 $\varphi$ 个面的多面体或连通图，有：

$\gamma\geq\frac{m}{6}-\frac{n-2}{2}$；
若 $G$ 无三角形，则 $\gamma\geq\frac{m}{4}-\frac{n-2}{2}$；
若 $G$ 每个面是三角形，则 $m=3(n-2+2\gamma)$；
若 $G$ 每个面是四边形，则 $m=2(n-2+2\gamma)$；

厚度¶

若图 $G$ 的 $k$ 个可平面子图的并等于，则称 $k$ 的最小值为 $G$ 的厚度，记为

$G$ 是可平面图当且仅当 $\theta(G)=1$。

叉数¶

将 $G$ 画在平面上时相交的边对的最少数目称为 $G$ 的叉数，记为：

\[ \eta(G) \]

$G$ 是可平面图当且仅当 $\eta(G)=0$。

糙度¶

图 $G$ 中边不重的不可平面子图的最多数目称为 $G$ 的糙度，记为：

\[ \zeta(G) \]

平面性算法¶

设 $H$ 是图 $G$ 的一个子图，在 $E(G)\backslash E(H)$ 上定义关系 $\sim$ 如下：$e_1\sim e_2$ 当且仅当存在一条途径 $W$，使得：

$W$ 的第一条边与最后一条边分别是 $e_1$ 与 $e_2$；
$W$ 的内部顶点与 $H$ 不相交

易证关系 $\sim$ 具有自反性，对称性和传递性，从而是 $E(G)\backslash E(H)$ 上的一个等价关系。

此等价关系的等价类导出的 $G-E(H)$ 的边导出子图称为 $H$-片段，或者 $G$ 关于 $H$ 的桥。片段或桥与 $H$ 的公共顶点称为附着顶点。

若 $B$ 是 $H$-片段，则 $B$ 是连通图
$B$ 的任何两个顶点都有和 $H$ 的内部不相交的路相连接
不计 $H$ 的顶点，任意两 $H$-片段没有公共顶点

设 $H$ 是图 $G$ 的一个圈，图 $G$ 的两个 $H$-片段 $B_1$ 和 $B_2$ 是冲突的，如果

$B_1$ 和 $B_2$ 在 $H$ 上有三个公共的附着顶点；或
在 $H$ 上存在四个顺序排列的顶点 $v_1,v_2,v_3,v_4$ 使得 $v_1,v_3$ 是 $B_1$ 的附着顶点并且 $v_2,v_4$ 是 $B_2$ 的附着顶点

冲突的两个片段无法同时平面嵌入到同一个面中

设 $H$ 是图 $G$ 的一个圈，以图 $G$ 的 $H$-片段为顶点，顶点间连一条边当且仅当对应的 $H$-片段是冲突的，把这样得到的图称为 $H$ 的冲突图

设 $H$ 是图 $G$ 的可平面子图，是 $\tilde H$ 的一种平面嵌入。若 $G$ 也是可平面图，且存在 $G$ 的一个平面嵌入 $\tilde H$，使得：

\[ \tilde H\subseteq\tilde G \]

则称 $\tilde H$ 是 $G$ 容许的。

图 $G$ 是可平面的当且仅当对 $G$ 的每个圈 $H$，其冲突图是二部图

设 $H$ 是图 $G$ 的一个可平面子图，$H'$ 是 $H$ 的一个平面嵌入。假定 $B$ 是子图 $H$ 的任一片段，若 $B$ 对 $H$ 的所有附着顶点都位于 $H'$ 中某个面 $f$ 的边界上，则称 $B$ 在 $H'$ 的面 $f$ 中是可画入的，否则，称为不可画入的。令：

\[ F(B,H)=\{f|f\text{是}H'\text{的面且}B\text{在}f\text{中可画入}\} \]

假定 $H'$ 如实线所示，则片段 $B_3$ 在外部面上是可画入的，而 $B_2$ 对面 $f_2$ 和 $f_3$ 均为不可画入的，且 $F(B_1,H)=\{f_1,f_3\}$。

$可画入示例$

算法流程¶

如果 $G$ 非可平面，通过算法可以得到判定；如果 $G$ 是可平面图，通过算法，可以给出一种平面嵌入形式。

设 $G$ 是至少有三个顶点的简单块，取 $G$ 的任意一个圈 $H$，求出 $H$ 的一个平面嵌入。若无圈，则 $G$ 是一棵树，一定可平面。

初始取 $G$ 的一个圈 $H _1$，并作平面嵌入 $\tilde H_1$。假设 $H_i$ 已确定，下面确定 $H_{i+1}$，算法流程如下：

判断 $E(G)\backslash E(H_i)=\varnothing$：
若是空集
- 则停，返回 $G$ 可平面。
否则
1. 确定 $H_i$ 的所有片段(桥)，
2. 对每个片段(桥) $B$，求集合 $F(B,H_i)$，
判断是否存在片段 $B$，使 $F(B,\tilde H_i)=\varnothing$：
若存在
- 则停，返回 $G$ 不可平面。
否则
1. 在 $H_i$ 的所有片段中确定一个使 $|F(B,\tilde H_i)|$ 最小的片段 $B$，
  - (这 2 步的选取具有随机性，算法的随机性来自于这一步)
2. 并取 $f\in F(B,\tilde H_i)$，
3. 在片段 $B$ 上取一条连接 $H_i$ 上两个附着点的路 $P_i$，
4. 把 $P_i$ 画在 $\tilde H_i$ 的面 $f$ 内得到 $H_{i+1}=H_i\cup P_i$，
令 $i=i+1$，转第 1 步