# 平面图 (planar graph)

设 G=(V,E) 是无向图，

如果图 G 的任意两条边都不在非结点处相交，则称图 G 为平面图；
如果存在着图 G 的一种图示，能够使得它的任意两条边都不在非结点处相交，则称图 G 为可平面图 (planargraph)。可平面图是平面图。
如果怎么图示都不能使图 G 的所有边对在非结点处不相交，则称图 G 为非平面图 (nonplanar graph)。

这里所说的图示，是在如下拓扑意义上的图形：

结点可处于 (可画于) 平面上的任何位置 (当然是在有限内)；

两点间的边可画成平面上连接两点的一条具有任何形状的、自身不相交的连续曲线－著名的若当 (Jordan) 曲线；

封闭的若当曲线 (J) 将平面 () 分成了内 (int J) 外 (ext J) 两个部分；关于若当曲线，有如下著名的若当定理：

$int J \cap ext J= J \qquad int J \cup ext J=\pi$

连接封闭的若当曲线 J 内部 int J 一点和外部 ext J 一点的任何若当曲线 $J'$ 必在某点与 J 相交 (穿过 J)；并且穿过 J 的次数必为奇数；

连接封闭的若当曲线 J 外部 ext J 两点的任何若当曲线 $J''$ 必偶数次的穿过 J。

$k_{3,3},k_5$ 是两个有名的非平面图 (恶例)；许多复杂图的平面性判定都归结于它们 (参见 K - 定理)
$k_{3,3}$ 是 3+3 节点的完全二分图
$k_5$ 是 5 个节点的完全无向图

# 平面图的几个概念术语

在平面图的图示中

区域 (regions)：由一条极小的初级圈所包围的面称为平面图的一个 (有限)
区域；
边界 (boundary)：构成区域的初级圈中的边称为此区域的边界；
无限区域 (infinite regions)：最大的初级圈之外部称为平面图的无穷区域；
相邻 (adjacent)：有公共边界的区域称为相邻。

所谓极小初级圈是指：在此圈内不再含有其它更小的初级圈，但不排
斥圈内可以有其它结点；
当图中无任何圈时 (比如树图)，整个平面即为无穷区域；
一个平面图有且仅有一个无穷区域；
区域又称为面，区域数又称为面数。

# 定理 1.(Euler 公式 (1750)).

设 G=(V, E) 是连通的平面图，其结点数 | V|=n，边数 | E|=m，区域 (面) 数 | R|=r，则它们必满足如下的 Euler 公式：

$n-m+r=2$

有些书的 Euler 公式写成:n-m+f=2 ，这里 f= |F | 是面数 (face) ；
还有些书的 Euler 公式写成: n-m+ r =1 或 n-m+f=1 ，他们在区域 (面) 数中
不计无穷区域。
事实上，Euler 当年提出 Euler 公式并不是针对平面图的，而是针对空间
凸多面体的 (那时还没有平面图的概念)；
Euler 公式证明使用类比推理法

# 空间凸多面体的平面嵌入 (同胚)

空间凸多面体和平面图服从同一规律 —Euler 公式，说明它们之间有着某种本质方面的联系，这就是：
任何空间凸多面体都可拓扑的嵌入平面而成为一平面图，称为平面嵌入或平面展开。
平面嵌入的实现是靠一种拓扑变换过程，称为球极平面投影，它能将球面上的任何图形拓扑映射到平面上而成为一平面图形。而空间凸多面体在拓扑学的意义上实际是一球面图形，因此能够经球极平面投影而实现平面嵌入。

# 平面图的必要性判定方法

# 推论 1

设 G=(V,E) 是 (n,m) 简单连通平面图，即 | V|=n, |E|=m，那么

$m\leq 3n-6 (m\geq 3) 。$

注意到图 G 是简单图，无平行边、无自环，因而图 G 中的每个区域都至少由三条边围成，故诸区域边界边数总和 $\geq 3r$
又因为一条边至多是两个区域的公共边界，故诸区域边界边数总和 $\leq 2m$ ，
所以 $2m \geq 3r$ ，于是 $r\leq m$ ，
代入 Euler 公式 $n-m+r=2$ ，得 $n-m+ m\geq 2$ ，
即 $3n-3m+2m\geq 6$ ，从而有 $3n-m\geq 6$ ，
所以 $m\leq 3n-6$ 。

# 推论 2

设 G=(V,E) 是 (n,m) 简单连通平面图，即 | V|=n,|E|=m，且图 G 中的每个区域都至少由四条边围成，那么

$m\leq 2n-4 (m\geq 4)$

# 推论 3

设 G=(V,E) 是 (n,m) 简单连通平面图，即 | V|=n,|E|=m，且图 G 中的每个区域都至少由五条边围成，那么

$m\leq \frac{5}{3} n-\frac{10}{3}$

平面图的定义 (拉边法) 是充分性判定方法，只能判断图是平面图，因为这只需用拉边法给出一种成功的图示即可；
平面图的定义 (拉边法) 不能判断图是非平面图，因为你给不出成功的图示，并不等于别人也给不出成功的图示，以及并不等价于该图本身就是非平面图；所以还需发展理论证明。

拉边法

有一些图刚好是推论 1、推论 2 的边缘情况，故不好用它们来判定，只
好仍用拉边法 (平面图的定义) 来判定了。

# K - 技术

在一图中两结点间，增加平行边 (重复边) 或删去平行边。不会改变该图的平面性；
在一图中两结点间已有的边上，增加一个 2 - 度结点，从而使一条边分为两条边。不会改变该图的平面性；
在一图中两结点间，删去另一个与此二结点相邻的 2 - 度结点，从而使两条边
合为一条边。不会改变该图的平面性。

所谓对一个图使用 K - 技术不会改变图的平面性是指：
原来是平面图，使用 K - 技术后仍为平面图；
原来是非平面图，使用 K - 技术后仍为非平面图。

# 定理 2.(Kuratowski - 平面图最后定理 (1930))

设 G=(V,E) 是无向图。那么，图 G 是平面图 $\iff$

图 G 中无一子图与 $K_5$ 或 $K_{3,3}$ 同构；
图 G 中无一经由 K - 技术所得的子图与 $K_5$ 或 $K_{3,3}$ 同构

# 定理 3. 平面图是 H - 图的一个必要性判定定理

(格林贝格 (Gringberg)(1968) - 柯车列夫 (Kozyrev) 定理)
设 G=(V,E) 是无向图。那么，
平面图 G 有 Hamilton - 圈 $\displaystyle \implies \sum^n_{i=2}(i=2)(I_i=Q_i)=0$
其中：n－是图 G 的结点数；
Ii －是 H - 圈内由 i 条边围成的区域个数；
Qi －是 H - 圈外由 i 条边围成的区域个数。

# 对偶图 (dual graph)

设 G=(V,E) 是平面图，R 是图 G 的区域集，并且 | V|=n， |E|=m，|R|=r 。则平面图的对偶图 $G^d=(V^d,E^d)$ 是一 (多重) 无向图，其中：

$V^d=\{v_i^d:v_i^d是在区域r_i中的结点\land t_i\in R\}\\ E^d=\{e_k^d:e_k^d=(v_i^d,v_j^d)\land v_i^d在r_i中\land v_j^d在r_i中\land e_k^d与e_k相交\land e_k \in E \land e_k是r_i和r_j的公共边界 \}\\ 并且|V_d|=r， |E_d|=m，|R_d|=n 。$

平面图 G 的对偶图 Gd 从拓扑学的角度来看，就是将图 G 的每个区域都收缩为结点，将图 G 的每个结点都扩张为区域；

因此，平面图 G 的面着色问题就相当于其对偶图 Gd 的结点着色问题；所以，四色定理的证明就归结为含有 5 - 度结点的平面图的结点着色问题；
平面图 G 和它的对偶图 Gd 互为对偶，即 $(G^d)^d=G$ ；
平面图 G 的对偶图 Gd 也满足 Euler 公式，即

$|V^d|-|E^d|+|R^d|=r-m+n=n-m+r= |V|-|E|+|R|=2$

# 定理 3

设 G=(V,E) 是无向图。那么，
图 G 是可平面图 $\iff$ 图 G 有对偶图 $G^d$