第六章 平面图

6.1 平面图

平面图的概念和性质

图的平面性问题是图论典型问题之一. 生活中许多应用问题都与该问题有关.

例如印刷电路板设计问题: 在电路板设计时, 需要考虑的问题之一是连接电路元件间的导线间不能交叉 (导线未绝缘). 否则, 会出现短路故障. 显然, 电路板可以模型为一个图,“要求电路元件间连接导线互不交叉”, 对应于“要求图中的边不能相互交叉”.

一些图论问题限定在平面图上可能会易于得到结果, 或者有好的结论. 如第七章将要学到的: 每个平面图是 $5$ 可着色的. 这也促使我们研究平面图.

针对上面的问题, 我们引入如下概念:

★平面图

如果能把图 $G$ 画在平面上, 使得除顶点外, 边与边之间没有交叉, 称 $G$ 可以嵌入平面, 或称 $G$ 是可平面图 (planar graph). 可平面图 $G$ 的边不交叉的一种画法, 称为 $G$ 的一种平面嵌入, $G$ 的平面嵌入表示的图称为平面图 (plane graph).

注: 可平面图和平面图可以等同看待.

图的平面性问题主要研究图的平面嵌入性问题以及在其它曲面上的嵌入问题, 是拓扑图论的主要内容. Kuratowski, Whitney 以及我国数学家吴文俊等在该方面都有重要结果.

面 $\Phi$

一个平面图 $G$ 把平面分成若干连通片, 这些连通片称为 $G$ 的一个面 (face) 或区域 (region), $G$ 的面组成的集合用 $\Phi$ 表示.

内部面, 外部面

面积有限的区域称为平面图 $G$ 的内部面 (inner face) 或有界面, 否则称为 $G$ 的外部面 (outer face) 或无界面.

在下图 $G$ 中, 共有 $4$ 个面. 其中 $f_4$ 是外部面, 其余是内部面. $\Phi =\{f_1,f_2,f_3,f_4\}$.

Jordan 曲线

Jordan 曲线 (Jordan curve) 是一条连续的, 自身不交的, 起点和终点重合的 (封闭的) 曲线.

平面图中圈中的各条边构成一条 Jordan 曲线.

Jordan 曲线定理

平面上任意简单闭合的曲线 $J$ 把平面划分为内部 (interior J) 和外部 (exterior J).

内部和外部均为开集. 上述定理表明连接内部点和外部点的任何连线都与 $J$ 相交.

Jordan 曲线定理是一个拓扑学的结论. 虽然定理直观上是明显的, 但它的严格证明十分困难.

面的边界, 面的次数 $\mathrm{deg}(f)$

在 $G$ 中, 顶点和边都与某个给定面关联的子图, 称为该面的边界 (boundary).

某面 $f$ 的边界中含有的边数 (割边计算 $2$ 次) 称为该面 $f$ 的次数 (degree), 记为 $\mathrm{deg}(f)$.

$$\mathrm{deg}(f_1)=1,\mathrm{deg}(f_2)=3,\mathrm{deg}(f_3)=6,\mathrm{deg}(f_4)=6$$

★平面图的次数公式

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

$$\sum _{f\in \Phi }\mathrm{deg}(f)=2m$$

证明: 对 $G$ 的任意一条边 $e$, 如果 $e$ 是某个面内的割边, 那么由面的次数定义, 该边对 $G$ 的总次数贡献 $2$ 次; 如果 $e$ 不是割边, 那么, 它必然是两个面的公共边, 因此, 由面的次数定义, 它也给总次数贡献 $2$ 次. 于是有:

$$\sum _{f\in \Phi }\mathrm{deg}(f)=2m$$

★平面图的欧拉公式

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

$$n-m+\varphi =2$$

证明: 对 $\varphi$ 用归纳法.

当 $\varphi =1$ 时, 每条边都是割边, 且 $G$ 连通, 则 $G$ 是树, 那么 $m=n-1$. 定理中的恒等式成立.

假设恒等式对于所有小于 $\varphi$ ($\varphi >1$) 个面的图都成立. 下面考虑 $\varphi$ 的情形. 取 $G=(n,m)$ 中的一条非割边 $e$. 则 $G-e$ 是包含 $\varphi -1$ 个面的平面图. 由归纳假设,

$$|V(G-e)|-|E(G-e)|+\varphi (G-e)=2$$

易知,

$$|V(G-e)|=n,|E(G-e)|=m-1,\varphi (G-e)=\varphi -1$$

因此, $n-m+\varphi =2$ 成立.

推论: 对于非连通图的欧拉公式

设 $G$ 是具有 $\varphi$ 个面 $k$ 个连通分支的平面图, 则:

$$n-m+\varphi =k+1$$

证明: 对第 $i$ ($1\le i\le k$) 个分支来说, 设顶点数为 $n_i$, 边数为 $m_i$, 面数为 ${\varphi }_i$, 由欧拉公式:

$$n_i-m_i+{\varphi }_i=2$$

所以,

$$\begin{gathered} \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{gathered}$$

而:

$$\sum _{i=1}^k{n}_i=n,\sum _{i=1}^k{m}_i=m,\sum _{i=1}^k{\varphi }_i=\varphi +k-1$$

所以得:

$$n-m+\varphi =k+1$$

★定理: 连通平面图的最大边数

设 $G$ 是具有 $n$ 个点 $m$ 条边 $\varphi$ 个面的连通平面图, 如果对 $G$ 的每个面 $f$, 有: $\mathrm{deg}(f)\ge l\ge 3$, 则:

$$m\le \frac{l}{l-2}(n-2)$$

证明: 一方面, 由次数公式得:

$$\begin{array}{rl}& 2m=\sum _{f\in \Phi }\mathrm{deg}(f)\ge l\varphi \\ \Rightarrow & \varphi \le \frac{2m}{l}\end{array}$$

另一方面, 由欧拉公式得:

$$\varphi =2-n+m$$

所以有:

$$\varphi =2-n+m\le \frac{2m}{l}$$

整理得:

$$m\le \frac{l}{l-2}(n-2)$$

注:

• 定理也可以叙述为: 设 $G=(n,m)$ 是连通图, 如果: $m>\frac{l}{l-2}(n-2)$, 则 $G$ 是非可平面图.
• 定理的条件是 $G$ 是平面图的必要条件, 不是充分条件.
• 定理中, 若每个面 $f$ 都有, $\mathrm{deg}(f)\ge 3$ 或 $4$ 时, 可以分别得到下面两个推论.

★推论1

设 $G$ 是具有 $n$ ($n\ge 3$) 个点 $m$ 条边 $\varphi$ 个面的简单平面图, 则:

$$m\le 3n-6$$

证明: $n$ ($n\ge 3$) 个点的图每个面的次数至少是 $3$, 即 $l=3$. 由欧拉公式得 $m\le 3n-6$.

推论2

设 $G$ 是具有 $n$ ($n\ge 3$) 个点 $m$ 条边 $\varphi$ 个面的简单平面二部图, 则:

$$m\le 2n-4$$

证明: 二部图不存在奇圈, 所以每个面的次数至少是 $4$, 即 $l=4$. 由欧拉公式得 $m\le 2n-4$.

注: 对非连通图推论1, 2仍然正确.

证明 $K_5$ 不可平面

证法一: $K_5$ 是简单图, $m=10,n=5$. 则有 $3n-6=9$. 得 $m>3n-6$, 所以 $K_5$ 非可平面.

证法二: 应用 Jordan 曲线理论.

存在 Jordan 曲线 (蓝色曲线) 把平面划分为内部和外部, 连接内部点和外部点的任何连线都与 Jordan 曲线相交, 故红色线会导致 $K_5$ 不可平面.

证明 $K_{3,3}$ 不可平面

证法一: 注意到, $K_{3,3}$ 是二部图, 不存在奇圈, 所以, 每个面的次数至少是 $4$, 即 $l=4$.

所以, $\frac{l}{l-2}(n-2)=\frac{4}{2}(6-2)=8$.

而 $m=9$, 这样有: $m>\frac{l}{l-2}(n-2)$.

所以, 由定理, $K_{3,3}$ 非可平面.

证法二: 应用 Jordan 曲线理论.

证明 Petersen 图不可平面

Petersen 图最小圈长为 $5$, 每个面的次数至少是 $5$, 即 $l=5$.

所以, $\frac{l}{l-2}(n-2)=\frac{5}{3}(10-2)=\frac{40}{3}$.

而 $m=15$, 这样有: $m>\frac{l}{l-2}(n-2)$.

所以, 由定理, Petersen 图不可平面.

证明 $Q_4$ 不可平面

4 维超立方图 $Q_4$ 最小圈长为 $4$, 每个面的次数至少是 $4$, 即 $l=4$.

所以, $\frac{l}{l-2}(n-2)=\frac{4}{2}(16-2)=16$.

而 $m=32$, 这样有: $m>\frac{l}{l-2}(n-2)$.

所以, 由定理, $Q_4$ 不可平面.

定理

设 $G$ 是具有 $n$ 个点 $m$ 条边的连通平面图,若 $G$ 的每个面均由长度是 $l$ 的圈围成,则:

$$m(l-2)=l(n-2)$$

证明: 由次数公式, 欧拉公式容易得证.

★定理: 平面图的最小度不超过 5

设 $G$ 是具有 $n$ 个点 $m$ 条边的简单平面图, 则:

$$\delta \le 5$$

证明: 若不然, 设 $\delta \ge 6$.

由握手定理:

$$\begin{array}{rl}& 6n\le \sum _{v\in V(G)}d(v)=2m\\ \Rightarrow & m>3n-6\end{array}$$

这与 $G$ 是简单平面图矛盾.

注: 该结论是证明“5色定理”(第七章)的出发点.

定理

一个简单连通平面图是 $2$ 连通的, 当且仅当它的每个面的边界是圈.

证明:

“必要性”: 设 $G$ 是 $2$ 连通的简单平面图, $G$ 没有自环. 那么 $G$ 没有割边, 也没有割点. 所以, 每个面的边界一定是一条闭迹 (why not walk?).

设 $C$ 是 $G$ 的任意面的一个边界, 我们证明, 它一定为圈.

若不然, 设 $C$ 是 $G$ 的某面的边界, 但它不是圈.

因 $C$ 是一条闭迹且不是圈, 所以 $C$ 中存在子圈. 设该子圈是 $W_1$. 因 $C$ 是某面的边界, 所以 $W_1$ 与 $C$ 的关系可以表示为下图的形式:

容易知道: $v$ 为 $G$ 的割点, 矛盾.

“充分性”: 设平面图 $G$ 的每个面的边界均为圈. 若 $G$ 不是 $2$ 连通的, 则 $G$ 存在割点 $v$. $G$ 的无界面边界不是圈, 矛盾.

推论

若一个平面图是 $2$ 连通的, 则它的每条边恰在两个面的边界上.

图的嵌入性问题简介

球面嵌入和平面嵌入

定理: $G$ 可球面嵌入当且仅当 $G$ 可平面嵌入.

证明: 我们用建立球极投影 (stereographic projection) 的方法给出证明.

将球面 $S$ 放在一个平面 $P$ 上, 设切点为 $O$, 过 $O$ 作垂直于 $P$ 的直线, 该直线与 $S$ 相交于 $z$.
作映射 $f:S–\{z\}\to P$. 定义 $f(x)=y$, 使得 $x,y,z$ 三点共线. 该映射称为球极平面射影.
通过 $f$, 可以把嵌入球面的图映射为嵌入平面的图. 反之亦然.

注: 这就是世界地图为什么可以在纸上(平面)印刷的原因.

图的曲面嵌入问题

图的曲面嵌入性问题是拓扑图论的研究热点之一.

注: 可参见M.A. Armstrong著, 孙以丰译《基础拓扑学》.

常见的简单曲面有平环, Mӧbius 带, 环面, Klein 瓶和射影平面. 它们都可以用矩形面块经过粘合而得到.

常见的曲面	图示	矩形表示
Mӧbius 带 (1858 年德国数学家 Mӧbius 发现)
环面
Klein 瓶 (1882 年德国数学家 Felix Klein 发现)

环面嵌入

环面的形状像一个汽车轮胎的表面.

将 $K_4,K_5,K_{3,3}$ 嵌入到环面上:

图的曲面嵌入矩形表示

凸多面体与平面图

多面体, 凸多面体

一个多面体 (polyhedron) 是由若干个多边形沿着边粘起来的一个封闭的表面所围的立体. 多面体称为凸的 (convex), 如果在体上任取两点, 其连线 (直线段) 包含在体上.

定理 (Steinitz’s Theorem, 1922)

每个凸多面体能够形成一个 $3$-连通的平面图, 反之亦然.

凸多面体的平面图

把一个凸多面体画在平面上, 得到一个对应的平面图, 该平面图称为该凸多面体的平面图.

正多面体

正四面体, 正六面体, 正八面体, 正十二面体, 正二十面体:

古希腊哲学家柏拉图 (429-347 B.C) 的朋友泰阿泰德发现了正多面体并告诉了柏拉图, 柏拉图将这其写在《蒂迈欧篇》中, 所以正多面体也被称为柏拉图立体 (Platonic solid).

定理: 存在且只存在 5 种正多面体

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

证明: 任取一个正 $\varphi$ 面体, 其顶点数、棱数分别是 $n$ 和 $m$. 对应的平面图是一个每个面次 (度) 数为 $l$, 顶点度数为 $r$ 的简单平面正则图 $G$.

由次数公式得:

$$2m=\varphi l\text{\hspace{1em}(1)}$$

由握手定理得:

$$2m=nr\text{\hspace{1em}(2)}$$

以上两等式中: $l\ge 3,r\ge 3$.

由 (1) 与 (2) 得:

$$m=\frac{nr}{2},\varphi =\frac{2m}{l}=\frac{nr}{l}\text{\hspace{1em}(3)}$$

将 (3) 代入欧拉公式得:

$$n=\frac{4l}{2l-lr+2r}\text{\hspace{1em}(4)}$$

在 (4) 中,

$$2l-lr+2r>0\Rightarrow 2(l+r)>lr$$

于是得不等式组:

$$\{\begin{array}{l}2(l+r)>lr\\ l\ge 3\\ r\ge 3\end{array}\text{\hspace{1em}(5)}$$

不等式组 (5) 的正整数解恰有 5 组:

定理得证.

正多面体的平面表示

富勒烯图

富勒烯图 (Fullerene) 是所有面是五边形或者六边形的连通平面 $3$ 正则图.

富勒烯图产生于化学中只包含碳原子的分子. 最典型结构是足球烯 $C_{60}$, 它是碳的第三种同素异形体 (第一种Fullerene, 1985年由Rice University 的 Richard Smalley等人合成; Kroto, Curl和Smalley因此获得1996 Nobel Prize).

注: $C_{60}$ 可以由正二十面体砍角后得到.

定理

富勒烯图恰好有 $12$ 个 $5$ 边形面.

证明: 令 $G$ 是一个富勒烯图. 假设 $f_5$ 和 $f_6$ 分别表示 $G$ 的五边形面和六边形面的个数.

由欧拉公式得: $n-m+\varphi =2$

$G$ 是 $3$ 正则图, 由握手引理得: $3n=2m$

由面的次数公式得: $5f_5+6f_6=2m$

另一方面, $\varphi =f_5+f_6$.

联立上面四个式子, 即可解得 $f_5=12$.

一些特殊的富勒烯图

仅包含 3 角形和 6 边形的 fullerene, 被称为 (3,6)-fullerene.

仅包含 4 边形和 6 边形的 fullerene, 被称为 (4,6)-fullerene 或 Boron-nitrogen fullerene.

6.2 一些特殊平面图及平面图的对偶图

极大平面图及其性质

对于一个简单平面图来说, 在不邻接顶点对间加边, 当边数增加到一定数量时, 就会变成非平面图. 这样, 就启发我们研究平面图的极图问题.

★极大平面图

设 $G$ 是简单可平面图, 如果
(1) $G$ 是 $K_i$ ($1\le i\le 4$) 或
(2) 在 $G$ 的任意非邻接顶点间添加一条边后, 得到的图均不可平面图,
则称 $G$ 是极大可平面图 (maximal planar graph).

极大可平面图的平面嵌入称为极大平面图 (maximal plane graph).

注: 只有在简单图前提下定义极大平面图才有意义.

引理

设 $G$ 是极大平面图, 则 $G$ 必然连通;
若 $G$ 的阶数大于等于 $3$, 则 $G$ 无割边.

证明:

(1) 先证明 $G$ 连通.
若不然, $G$ 至少有两个连通分支. 设 $G_1$ 与 $G_2$ 是 $G$ 的任意两个连通分支.
把 $G_1$ 画在 $G_2$ 的外部面上, 并在 $G_1,G_2$ 上分别取一点 $u$ 与 $v$. 连接 $u$ 与 $v$ 得到一个新平面图 $G^{\ast }$. 但这与 $G$ 是极大平面图相矛盾.

(2) 当 $G$ 的阶数 $n\ge 3$ 时, 我们证明 $G$ 中没有割边.
若不然, 设 $G$ 中有割边 $e=uv$, 则 $G-uv$ 不连通, 恰有两个连通分支 $G_1$ 与 $G_2$.

设 $u$ 在 $G_1$ 中, 而 $v$ 在 $G_2$ 中. 由于 $n\ge 3$, 所以, 至少有一个分支包含两个以上的顶点. 设 $G_2$ 至少含有两个顶点. 又设 $G_1$ 中含有点 $u$ 的面是 $f$, 将 $G_2$ 画在 $f$ 内.

由于 $G$ 是简单图, 所以, 在 $G_2$ 的外部面上存在不等于点 $v$ 的点 $t$. 现在, 在 $G$ 中连接点 $u$ 与 $t$ 得新平面图 $G^{\ast }$, 它比 $G$ 多一条边. 这与 $G$ 的极大性相矛盾.

★定理: 极大平面图的性质

设 $G$ 是 $n$ 阶 ($n\ge 3$) 简单平面图, 则下面命题等价:

(1) $G$ 是极大平面图;
(2) $G$ 每个面的次数是 $3$, 亦称作三角剖分 (triangulation);
(3) $G$ 有 $3n-6$ 条边.

证明:

(1) ⇔ (2)
由 $G$ 是简单图知, $G$ 的每个面的次数至少是 $3$. 假设 $G$ 中某个面 $f$ 的次数大于等于 $4$. 如下图所示:

若 $v_1$ 与 $v_3$ 不邻接, 将边 $v_1{v}_3$ 画在 $f$ 内, 得到边数更多的平面图, 这与 $G$ 是极大平面图矛盾.

(2) ⇔ (3)
将 $2m={\sum }_{f\in \Phi }\mathrm{deg}(f)\ge 3\varphi$ 代入欧拉公式得到 $m\le 3n-6$.
而 $m=3n-6$ 则意味着 $2m=3\varphi$. 即每个面的次数都是 $3$.

推论

设 $G$ 是 $n$ 个点, $m$ 条边和 $\varphi$ 个面的极大平面图, 且 $n\ge 3$. 则: $\varphi =2n-4$.

证明: 因 $G$ 是极大平面图, 将 $m=3n-6$ 代入欧拉公式即得.

注

(1) 顶点数相同的极大平面图并不唯一. 例如:

(2) 正四, 八, 二十面体均为极大平面图.

极大外平面图及其性质

外平面图

若一个可平面图 $G$ 存在一种平面嵌入, 使其所有顶点均在某个面的边界上, 称该图为外可平面图 (outerplanar graph). 外可平面图的一种外平面嵌入, 称为外平面图 (outerplane graph).

注: 对外可平面图 $G$ 来说, 一定存在一种外平面嵌入, 使得 $G$ 的顶点均在外部面的边界上 (内部面和外部和可以相互转化). 这由如下球极投影法可以说明.

为什么要研究外可平面图呢? 对于平面图上的一些问题, 外平面图可能容易得到. 例如:

命题: $2$-连通的外平面图的外面边界是 Hamiltonian 圈.

★极大外平面图

设 $G$ 是一个简单外可平面图, 若在 $G$ 中任意不邻接顶点间添上一条边后, $G$ 成为非外可平面图, 则称 $G$ 是极大外可平面图 (maximal outerplanar graph). 极大外可平面图的外平面嵌入, 称为极大外平面图 (maximal outerplane graph).

引理

设 $G$ 是一个连通简单外可平面图, 则在 $G$ 中有一个度数至多是 $2$ 的顶点.

Hint: 应用归纳法 (考虑 $G$ 有割点或者 $G$ 是 $2$-连通的情形).

定理

设 $G$ 是一个有 $n$ ($n\ge 3$) 个点, 且所有点均在外部面上的极大外平面图, 则 $G$ 有 $n-2$ 个内部面.

证明: 对 $G$ 的阶数作归纳.

当 $n=3$ 时, $G$ 是三角形, 显然只有一个内部面;

设当 $n=k$ 时, 结论成立. 当 $n=k+1$ 时, 首先, 注意到 $G$ 必有一个 $2$ 度顶点 $v$ 在 $G$ 的外部面上. (可由上面引理得到)

考虑 $G-v$. $G-v$ 有 $k$ 个点, 由归纳假设, $G-v$ 有 $k-2$ 个内部面. 这样 $G$ 有 $k-1$ 个内部面. 于是定理得证.

定理

设 $G$ 是一个有 $n$ ($n\ge 3$) 个点, 且所有点均在外部面上的外平面图, 则 $G$ 是极大外平面图, 当且仅当其外部面的边界是圈, 内部面是三角形.

注: 这是极大外平面图的典型特征.

证明:

(1) 必要性:
$G$ 是极大外平面图.
证明极大外平面图 $G$ 是 $2$-连通的(作为练习).
由6.1中定理知, $G$ 的每个面都是圈.
再证明 $G$ 的任一内部面 $C$ 是三角形. 若不然, 则 $C$ 中一定存在不邻接顶点, 连接这两点得到一个新平面图, 这与 $G$ 的极大性矛盾. 又由于 $G$ 是简单图, 所以 $C$ 的长度只能为 $3$.

(2) 充分性:
(反证) $G$ 外部面的边界是圈, 内部面是三角形, 若 $G$ 不是极大外平面图, 则存在不相邻点 $u$ 与 $v$, 使得 $G+uv$ 是外平面图. 若边 $uv$ 经过 $W$ 的内部面, 则它要与 $G$ 的其它边相交; 若 $uv$ 在 $W$ 的外部面, 则所有点不能在 $G$ 的外部面.

平面图的对偶图

★对偶图 $G^{\ast }$

给定平面图 $G$, $G$ 的对偶图 (dual) $G^{\ast }$ 如下构造:

(1) 在 $G$ 的每个面 $f_i$ 内取一个点 $v_i^{\ast }$ 作为 $G^{\ast }$ 的一个顶点;

(2) 对 $G$ 的每一条边 $e$, 若 $e$ 是面 $f_i$ 与 $f_j$ 的公共边, 则连接 $v_i^{\ast }$ 与 $v_j^{\ast }$, 且连线穿过边 $e$; 若 $e$ 是面 $f_i$ 中的割边, 则以 $v_i$ 为顶点作自环, 且让它与 $e$ 相交.

正立方体的对偶图：

注:

• 对偶出现的很早 (Fifteenth book of Euclid, AD 500-600, 记录了正多面体图之间的相互对偶).

• “对偶”是数学研究问题的一种方法; 通过将问题转化促使问题解决; 如, 线性规划中求解对偶问题.

• 通过将平面转化为对偶图研究. 如, 将平面地图的4色问题转换为对应对偶图的顶点4色问题(见第七章)研究.

$G$ 与 $G^{\ast }$ 的对应关系

若 $G$ 为连通图, 则:

1. $G^{\ast }$ 的顶点数等于 $G$ 的面数;
2. $G^{\ast }$ 的边数等于 $G$ 的边数;
3. $G^{\ast }$ 的面数等于 $G$ 的顶点数;
4. $d(v^{\ast })=\mathrm{deg}(f)$.

若 $G$ 不连通, 上面的关系中 3 不满足.

★定理

平面图 $G$ 的对偶图必然连通.

证明: 在 $G^{\ast }$ 中任意取两点 $v_i^{\ast }$ 与 $v_j^{\ast }$. 我们证明该两点连通即可！

用一条曲线 $l$ 把 $v_i$ 和 $v_j$ (注: $v_i$ 和 $v_j$ 分别为 $v_i^{\ast }$ 与 $v_j^{\ast }$ 对应在 $G$ 中的面) 连接起来, 且 $l$ 不与 $G$ 的任意顶点相交.

显然, 曲线 $l$ 从 $v_i$ 到 $v_j$ 经过的面边序列, 对应从 $v_i^{\ast }$ 到 $v_j^{\ast }$ 的点边序列, 该点边序列就是该两点在 $G^{\ast }$ 中的通路.

注: 由该定理知: $(G^{\ast }{)}^{\ast }$ 不一定同构于 $G$.

定理

$G$ 是平面图, 则 $(G^{\ast }{)}^{\ast }\cong G$ 当且仅当 $G$ 是连通的.

证明:

“必要性”
由于 $G$ 是平面图, 由定理, $G\ast$ 是连通的. 而由 $G\ast$ 是平面图, 再由定理, $(G\ast )\ast$ 是连通的.
所以, 由 $(G^{\ast }{)}^{\ast }\cong G$ 得: $G$是连通的.

“充分性”
由对偶图的定义知, 平面图 $G$ 与其对偶图 $G^{\ast }$ 嵌入在同一平面上, 当 $G$ 连通时. 容易知道: $G^{\ast }$ 的无界面 $f^{\ast }$ 中仅包含 $G$ 的唯一顶点 $v$, 而除 $v$ 外, $G$ 中其它顶点 $u$ 均与 $G^{\ast }$ 的有限面形成一一对应 ($G^{\ast }$ 有限面的邻接关系与 $G$ 中对应顶点的邻接关系一致), 于是, $G$ 中顶点和 $(G^{\ast }{)}^{\ast }$ 顶点在这种自然对应方式下一一对应, 且对应顶点间邻接关系保持不变, 故 $(G^{\ast }{)}^{\ast }\cong G$.

定理

同构的平面图可以有不同构的对偶图.

例如下面的两个图: $G_1\cong G_2$.

但 G_1^∗ \not \cong ̸ G_2^∗.

这是因为: $G_2$ 中有次数是 $1$ 的面, 而 $G_1$ 没有次数是 $1$ 的面. 所以, 它们的对偶图不能同构.

定理*

设 $G$ 是连通平面图, $S$ 是 $G$ 的一个边子集. 则 $S$ 的导出子图是 $G$ 的圈当且仅当 $S^{\ast }$ 是 $G^{\ast }$ 的一个极小边割.

设 $G$ 是连通平面图, $S$ 是 $G$ 的一个边子集. 则 $S$ 是 $G$ 的一个极小边割当且仅当 $S^{\ast }$ 的导出子图是 $G^{\ast }$ 的一个圈.

6.3 平面图的判定及涉及平面性的不变量

平面图的判定

在本章第一次课中, 我们已经明确: 对于 $3$ 阶以上的具有 $m$ 条边的简单图 $G$, 如果 $G$ 满足如下条件之一:

• (1) $m>3n-6$;
• (2) 包含 $K_5$ 作为子图;
• (3) 包含 $K_{3,3}$ 作为子图.

那么, $G$ 不是平面图.

但上面的条件仅为 $G$ 不可平面的充分条件. 是否存在可平面图的充分必要条件? 波兰数学家 Kazimierz Kuratowski 最早 (20世纪30年代) 给出图的平面性判定充要条件. 后来, 美国数学家Whitney, 加拿大数学家Tutte, 我国数学家吴文俊等都给出了不同的充要条件. 我们主要介绍波兰数学家 Kuratowski 的结果.

剖分, 内收缩

在图 $G$ 的边上插入一个 $2$ 度顶点, 使一条边分成两条边, 称将图的剖分 (subdivision); 去掉一个图的 $2$ 度顶点, 使关联它们的两条边合并成一条边, 称将图 $G$ 在 $2$ 度顶点内收缩 (contraction) 或简化 (simplify).

注: 内收缩事实上是一种特殊的收缩运算 ($2$ 度点的收缩).

同胚

两个图 $G_1$ 与 $G_2$ 是同胚的 (homeomorphic), 如果 $G_1\cong G_2$, 或者通过反复剖分和内收缩后能够变成一对同构的图.

例如 $G_1,G_2,G_3$ 是同胚图.

注:

(1) 图的平面性在同胚意义下不变;

(2) 判定两个图是否同胚是 NP-完全的;

(3) 图的同胚是等价关系.

Kuratowski 定理

(Kuratowski, 1930) 图 $G$ 是可平面的, 当且仅当它不含 $K_5$ 和 $K_{3,3}$ 同胚的子图.

Kuratowski 定理可以等价叙述为: 图 $G$ 不可平面当且仅当它含有 $K_5$ 或 $K_{3,3}$ 的同胚子图.

注: 上述结论是 1965 年 Harary 和 Tutte 对 Kuratowski 定理的表述, 与 1930 年 Kuratowski 论文中的表述不同 (未说明充分性).

Kuratowski 原始论文中的 $K_{3,3}$ 和 $K_5$:

例

求证: 下面两图均不可平面.

证明:

内收缩 $G_1$ 的 $2$ 度点后得 $K_5$. 即 $G_1$ 不可平面.

取 $G_2$ 的如下子图:

对上面子图, 按 $2$ 度顶点收缩得与之同胚子图 $K_{3,3}$:

所以, $G_2$ 不可平面.

例

确定下图是否可平面.

分析: 根据图的结构, 突破方向是: 该图不可平面.

当然可以考虑是否满足 $m>3n-6$. 遗憾的是该图不满足这个不等式！

所以, 要在该图中寻找一个与 $K_5$ 或 $K_{3,3}$ 同胚的子图!

由于该图的最大度为 $4$ 的顶点才 $4$ 个, 所以, 不存在与 $K_5$ 同胚的子图. 因此, 只有寻找与 $K_{3,3}$ 同胚的子图!

解: 取 $G$ 中红色边的一个导出子图:

也就是得到 $G$ 的如下形式的一个子图:

上图显然和 $K_{3,3}$ 同胚. 由 Kuratowski 定理知, $G$ 不可平面.

基础简单图

给定图 $G$, 去掉 $G$ 中的自环, 用单边代替平行边而得到的图称为 $G$ 的基础简单图 (fundamental simple graph).

定理

(1) 图 $G$ 可平面, 当且仅当它的基础简单图可平面;

(2) 图 $G$ 可平面当且仅当 $G$ 的每个块都可平面.

证明:

(1) 由平面图的定义, 该命题显然成立.

(2) 必要性显然.下面证明充分性.

不失一般性, 假设 $G$ 连通. 我们对 $G$ 的块数 $b$ 作归纳.

当 $b=1$ 时, 由条件, 结论显然成立;

设当 $b<k$ 时, 若 $G$ 的每个块是可平面的, 则 $G$ 是可平面的. 下面考虑 $b=k$ 时的情形.

设点 $v$ 是 $G$ 的割点, 则按照 $v$, $G$ 可以分成两个边不重子图 $G_1$ 与 $G_2$, 即 $G=G_1\cup G_2$, 且 $G_1\cap G_2=v$.

由归纳假设, $G_1$ 与 $G_2$ 都是可平面图. 取 $G_1$ 与 $G_2$ 的平面嵌入满足点 $v$ 都在外部面边界上, 则把它们在点 $v$ 处对接后, 将得到 $G$ 的平面嵌入. 即证 $G$ 是可平面图.

子式 (minor)

关于图的可平面性的刻画, 德国数学家瓦格纳 (Wagner) 在 1937 年科隆大学博士毕业时得到了一个漂亮定理.

图 $G$ 的子式 (minor) 或次图是对 $G$ 进行一系列的删点, 删边或者边收缩运算得到的基础简单图.

例如 $H$ 是 $G$ 的 minor.

Wagner 定理

(Wagner,1937) 简单图 $G$ 是可平面图当且仅当 $K_5$ 和 $K_{3,3}$ 不是它的 minor.

注: 在结构图论中, minor 是一个非常重要的概念.

例

求证 Petersen 图不可平面.

证明: Petersen 图可通过一些边 (辐条边, spokes, 红色边) 收缩运算后得到 $K_5$ (或通过下图的变换为 $K_{3,3}$). 由瓦格纳定理得证.

例

(Selfridge,1960s) 设 $G$ 是一个简单图, 若顶点数 $n\ge 11$, 则 $G$ 与 $G$ 的补图中, 至少有一个是不可平面图.

证明: 设 $G$ 是一个 $n$ 阶可平面图, 则: $m(G)\le 3n-6$.

若 $G$ 与 $G$ 的补图均为平面图, 则 $m(\overline{G})+m(G)\le 6n-12$.

另一方面, $m(\overline{G})+m(G)=\frac{n(n-1)}{2}$.

当 $n\ge 11$ 时, 显然有 $\frac{n(n-1)}{2}>6n-12$.

矛盾. 因此 $G$ 与 $G$ 的补图中至少有一个是不可平面图.

例

设 $G_i$ 是一个有 $n_i$ 个点, $m_i$ 条边的图, $i=1,2$. 证明: 若 $G_1$ 与 $G_2$ 同胚, 则: $n_1+m_2=n_2+m_1$

证明: 设 $G_1$ 经过 $p_1$ 次剖分, $p_2$ 次 $2$ 度顶点收缩得到 $H_1$, $G_2$ 经过 $q_1$ 次剖分, $q_2$ 次 $2$ 度顶点收缩得到 $H_2$, 使得: $H_1\cong H_2$.

又设 $H_1$ 与 $H_2$ 的顶点数分别为 $n_1^{\ast }$ 和 $n_2^{\ast }$, 边数分别为 $m_1^{\ast }$ 与 $m_2^{\ast }$. 那么:

$$\begin{array}{ll}{n}_1^{\ast }=n_1+p_1-p_2,& m_1^{\ast }=m_1+p_1-p_2\\ n_2^{\ast }=n_2+q_1-q_2,& m_2^{\ast }=m_2+q_1-q_2\end{array}$$

所以:

$$\begin{gathered} n_1+m_2=n_1^{\ast }+m_2^{\ast }+p_1-p_2+q_1-q_2 \\ {n}_2+m_1=n_2^{\ast }+m_1^{\ast }+p_1-p_2+q_1-q_2 \end{gathered}$$

而由 $H_1\cong H_2$ 得: $m_1^{\ast }=m_2^{\ast },n_1^{\ast }=n_2^{\ast }$

所以: $n_1+m_2=n_2+m_1$.

涉及平面性的不变量

我们将要讨论: 如何刻画非可平面图的差别, 即不可平面性的强弱程度.

• 图的亏格 (genus)
• 图的厚度 (thickness) (Application in Printed Circuit Board)
• 图的交叉数 (crossing number)

图的亏格

将图嵌入到一些曲面, 通过曲面的拓扑不变量来衡量图的一些 (拓扑) 性质, 如不可平面性, 色数(第七章)等.

环柄

环柄 (handle), 直观地理解为咖啡杯的手把. (在边交叉处建立的“立交桥” (环柄). 让一条边经过 “桥下”, 而另一条边经过“桥上”, 从而把两条边在交叉处分开)

爱因斯坦: “重大问题的解决方案, 永远不可能在同一维度上产生, 而是在更高一个维度上产生”.

交叉帽

交叉帽 (cross cap), Mӧbius 带的另一种叫法 (通过扭曲将嵌入图上可能交叉的两条边分开).

$n$ 维流形

$n$ 维流形 ($n$-manifold) 指 Hausdorff 的并且能被有限的开集覆盖, 每个开集都同胚于一个 $n$ 维开球 $\{(x_1,\dots ,x_n|x_1^2+\dots +x_n^2<1)\}$.

曲面

曲面 (surface) 指连通的 $2$ 维流形 ($2$-manifold).

闭曲面分类定理

每一个紧致的 (它的所有开覆盖都有有限子覆盖) 连通闭曲面都同胚于一个球面去掉一些圆盘后粘上环柄或者交叉帽.

注: (1) 两个拓扑空间X和Y是同胚的(homeomorphic)如果存在f: X→Y满足f连续且是双射且f的逆也连续.

可定向, 不可定向

不包含交叉帽的闭曲面称为可定向的 (orientable); 包含交叉帽的曲面称为不可定向的 (non-orientable).

曲面的亏格 $g(\Sigma )$

闭曲面 $\Sigma$ 上包含 $k$ 个环柄 (或交叉帽, 事实上是 Mӧbius 带) 的数目, 称为可定向或不可定向亏格, 记为: $g(\Sigma )$.

注:

(1) 射影平面 (球面粘上一个交叉帽所得) 的亏格为 $1$;

(2) Klein 瓶的亏格为 2.

图的亏格 $g(G)$

图 $G$ 可以嵌入的最小亏格的可定向或不可定向闭曲面的亏格称为图 $G$ 的可定向或不可定向亏格, 记为: $g(G)$.

欧拉示性数 $c(\Sigma )$

闭曲面 $\Sigma$ 的欧拉示性数 (Euler chracteristic) $c(\Sigma )$ 定义为:

$$c(\Sigma )=\{\begin{array}{ll}2-2g,& 若\Sigma 是可定向曲面;\\ 2-g,& 若\Sigma 是不可定向曲面.\end{array}$$

注: $K_5$ 不可嵌入到平面上, 所以 $K_5$ 的亏格大于 $0$. 但 $K_5$ 可以嵌入到环面上, 所以 $K_5$ 的可定向亏格是 $1$. $K_5$ 也可以嵌入到射影平面上, 所以 $K_5$ 的不可定向亏格是 $1$.

定理: 一般连通图的欧拉公式

设 $\tilde{G}$ 是图 $G$ 的在闭曲面 $\Sigma$ 的胞腔嵌入 (cellular embedding), 则: $n-m+\varphi =c(\Sigma )$.

注: 因多面体对应一个连通图, 所以上面恒等式称为一般连通图的欧拉公式. (cellular embedding: 每个面都同胚于一个开圆盘).

例

验证 $K_5$ 的嵌入满足曲面胞腔嵌入的欧拉公式.

解: $K_5$ 嵌入环面有 $5$ 个面, $K_5$ 嵌入射影平面有 $6$ 个面. 环面和射影平面的亏格都是 $1$. 所以欧拉公式均成立.

例

$4$ 维超立方 $Q_4$ 能胞腔嵌入到环面吗?

解: 若 $Q_4$ 能嵌入环面, 则由欧拉公式得, $n-m+f=0$.

即 $f=16$. 这说明该嵌入有 $16$ 个面. 事实上, 确实存在 $Q_4$ 的环面嵌入. 如下图所示.

但 $Q_4$ 不能嵌入平面 (这一点容易证明).

图的厚度

厚度 $\theta (G)$

若图 $G$ 的 $k$ 个可平面子图的并等于 $G$, 则称 $k$ 的最小值为 $G$ 的厚度 (thickness), 记为 $\theta (G)$.

显然, 平面图的厚度是 $1$.

双可平面图

厚度为 $2$ 的图称为双可平面图 (biplanar graph).

图厚度的研究起源于下面问题: 哪些完全图的边可以分解为两个平面图的并?

例讨论了 $11$ 阶完全图的边不能分解为两个可平面图的并.

下图展示了 $6$ 阶完全图的边分解为两个平面图的并.

下图所示的一个 $8$ 阶图 (自补图) 及其补图均是平面的.

1962年, 著名图论专家Frank Harary猜想: 存在一个9阶图和它的补图都不可平面(对比例4中11阶图). 事实上该问题等价于: K9是否双可平面? (猜想正确, K9的厚度是3)

定理

(1) (Vasak; Aleksee和Gonchakov 1976)
$\theta (K_n)=\lfloor \frac{n+7}{6}\rfloor$, 除了 $\theta (K_9)=\theta (K_{10})=3$.

(2) (Beineke, Harary 和 Moon 1964)
$\theta (K_{m,n})=\lfloor \frac{mn}{2(m+n-2)}\rfloor$ , 除了 $m$ 和 $n$ 均为奇数, 或 $m\le n$, 存在一个偶数 $r$ 使得 $n=\lceil r(m-2)/(m-r)\rceil$.

(3) 对任意的简单图 $G=(n,m)$, 有: $\theta \ge m/(3n-6)$

注:
(1) 计算给定图的厚度是 NP-困难的 (判断厚度是否为 $2$ 是 NP-完全的).
(2) 印刷电路板的厚度与对应图的厚度有直接的关系.

图的交叉数

交叉数 $cr(G)$

将 $G$ 画在平面上时相交边对的最少数目称为 $G$ 的交叉数, 记为 $cr(G)$.

注: 一个图是平面图当且仅当其交叉数是 $0$.

WWII期间(1944), Pál Turán(Turán定理的发现者)被迫在一个砖厂工作(使用货车把砖从砖窑运到储存地). 窑和储存地之间有固定的路线, 货车经过路线交叉点时效率很低. 问题: 怎么样设计窑, 储存和路线使得交叉点最少? 问题可以建模为求二部图的交叉数.

例

Petersen 图的交叉数是 $2$.

例

$cr(K_6)=3$.

因 $6$ 个顶点的平面图最多包含 $12$ 条边, 因此 $cr(K_6)\ge 3$.

$K_6$ 的一种正好有 $3$ 个交叉点的画法.

注:
(1) 求给定图的交叉数是 NP-困难的 (限定在最大度不超过 $3$ 的图上是 NP-完全的, Garey and Johnson, 1983);
(2) 交叉数在 VLSI 设计, 数论和关联几何中也有应用.

超立方的交叉数

超立方 $Q_4$ 的交叉数是 $8$.

一般地, Eggleton 和 Guy在 1970 年得到了超立方交叉数的上界:

$$cr(Q_n)\le \frac{5}{32}{4}^n-\lfloor \frac{n^2+1}{2}\rfloor 2^{n-2}$$

Erdős 和 Guy 在 1973 年猜想上面等式成立.

最近, 大连理工大学的杨元生等发现当 $n>6$ 时, 等式不成立.

$$cr\left(Q_n\right)=\frac{139}{896}{4}^n-\lfloor \frac{n^2+1}{2}\rfloor 2^{n-2}+\frac{4}{7}\cdot 2^{3\lfloor \frac{n}{2}\rfloor -n}+{\lambda }_n\left(\frac{4^n}{24576}-\frac{4\lfloor \frac{n}{2}\rfloor }{6}\right)$$

其中, 当 $5\le n\le 6$ 时, ${\lambda }_n=0$, 当 $n\ge 13$ 时, ${\lambda }_n=1$.

6.4 平面性算法

涉及算法的相关概念

关于图的平面性问题, 我们已经建立了一些平面性判定方法:

• (1) 对于简单图 $G=(n,m)$, 如果 $m>3n-6$, 则 $G$ 非可平面;
• (2) 对于连通图 $G=(n,m)$, 如果每个面次数至少为 $l\ge 3$, 且 $m>(n-2)l/(l-2)$, 则 $G$ 非可平面;
• (3) Kuratowski 定理: $G$ 可平面当且仅当 $G$ 不含有与 $K_5$ 或 $K_{3,3}$ 同胚的子图;
• (4) Wagner 定理: $G$ 可平面当且仅当 $G$ 不含 $K_5$ 或 $K_{3,3}$ 的初等收缩子图 (minor).

上面的判定方法, 局限性较大. 本节将给出一个算法判定图 $G$ 是否平面, 进一步地, 如果 $G$ 是可平面图, 通过算法, 可以给出一种平面嵌入形式.

$H$-片断 $B_i$

设 $H$ 是 $G$ 的一个真子图, $E(G)-E(H)$ 被划分为如下的一些类:

• (1) 对于 $G-V(H)$ 的每一个分支 $F$ 以及 $F$ 连向于 $H$ 的边;
• (2) 每条剩余的边 $e$ (两个端点均在 $H$ 中) 定义了一个孤立类.

由这些 $H$ 的类在 $G$ 中的边导出子图称为 $G$ 的 $H$-片断 ($H$-fragment) (Historically called, 桥 bridge).

片断与 $H$ 的公共顶点称为附着顶点 (attached vertex).

注:

(1) 孤立类可能是存在的 (因 $H$ 不一定是导出子图).
(2) $H$-片断以及 $H$ 本身是对 $G$ 的边集的分解.

例如下图中, 红色边在 $G$ 中导出子图为 $H$. 则 $G$ 的所有 $H$-片断为 $B_1$ 到 $B_4$, 其中 $B_4$ 是孤立类.

冲突

令 $C$ 是图 $G$ 的一个圈. $G$ 的两个 $C$-片断 $A$ 和 $B$ 是冲突的 (conflict), 如果

• (1) $A$ 和 $B$ 在 $C$ 上有三个公共的附着点; 或
• (2) 在 $C$ 上存在四个顺序排列的顶点 $v_1,v_2,v_3,v_4$ 使得 $v_1,v_3$ 是 $A$ 的附着点并且 $v_2,v_4$ 是 $B$ 的附着点.

注: 冲突的两个片断没法平面嵌入到同一个面中.

冲突图

称圈 $C$ 的冲突图 (conflict graph) 是顶点由 $G$ 的 $C$-片断构成, 若 $C$ 的两个片断冲突, 则对应点在冲突图中相邻.

例如 $K_5$ 生成圈的冲突图.

练习: 画出 $K_{3,3}$ 生成圈的冲突图.

定理 (Tutte 1958)

图 $G$ 是可平面的当且仅当对 $G$ 的每个圈 $C$, $C$ 的冲突图是二部图.

证明:

必要性. $G$ 平面, $G$ 的任意一个圈 $C$ 都把平面划分为两个区域. $C$-片断在内部或外部的嵌入形成冲突图的独立集.

充分性. 设 $C$ 是 $G$ 的任意一个圈. 不妨设 $W$ 和 $B$ 为 $C$ 的冲突图的二部划分. 将 $W$ 代表的片断嵌入 $C$ 的内部, 将 $B$ 代表的片断嵌入 $C$ 的外部.

我们仅考虑 $W$ ($B$ 的证明类似). 因 $W$ 中的任意片断都不冲突, 故将其记为 $W_1,W_2,\dots ,W_k$. 所以可以将他们在 $W$ 中画出.

$F(B_i,H)$

为了方便, 定义下面的集合.

$$F(B_i,H)=\{f|f是H的面,且H的片断B_i的附着点均在f的边界上\}$$

例如：红色边的导出子图是 $H$. 对 $H$ 的所有片断 $B_i$ 确定 $F(B_i,H)$.

$$\begin{array}{rl}& F(B_1,H)=f_2,f_3\\ & F(B_2,H)=f_3\\ & F(B_3,H)=f_3\end{array}$$

平面性算法

1964年, Demoucron, Mlgrance 和 Pertuiset 提出了下面的平面性算法, 简称 DMP 算法. 我们本节讨论 DMP 算法. DMP 是多项式时间的.

事实上, Hopcroft-Tarjan [1974] 和 Booth-Luecker [1976] 得到首个线性时间 (较为复杂的) 平面性算法.

因图 $G$ 是平面的当且仅当 $G$ 的每个块都是平面的. 而求图的块的算法是好算法 (深度优先策略). 所以我们假设图 $G$ 是 $2$-连通的.

平面性算法 Planarity Testing Algorithm (DMP)

取 $G$ 的任意一个圈 $H_0$, 求出 $H_0$ 的一个平面嵌入.

假设 $H_i$ 已确定, 下面确定 $H_{i+1}$.

(1) 确定 $G$ 的所有 $H_i$-片断;

(2) 若 $E(G)-E(H_i)=\Phi$, 则停止 (返回 $G$ 可平面); 否则, 对每个片断 $B$, 求出 $F(B,H_i)$;

(3) 若存在片断 $B$, 使得: $F(B,H_i)=\Phi$, 则停止 (返回 $G$ 不可平面); 否则, 在 $H_i$ 的所有片断中确定一个使得 $|F(B,H_i)|$ 最小的 $B$, 并取 $f\in F(B,H_i)$.

(4) 在片断 $B$ 中取一条连接 $H_i$ 中两个附着顶点的路 $P_i$, $P_i\subseteq B_i$;
置 $H_i+1=H_i\cup P_i$,把 $P_i$ 画在 $H_i$ 的面 $f$ 内, 得到 $H_{i+1}$.
若 $H_i+1=G$, 返回 $G$ 可平面. 否则使得 $i=i+1$ 并返回第 (1) 步.

例

用平面性算法考察下图 $G$ 的平面性.

解:

(1) 取 $G$ 的一个圈 $H_1$, 并作平面嵌入:

(2)

$$\begin{array}{ll}{B}_1=G[\{v_1{v}_3\}]& F(B_1,\widetilde{H_1})=\{f_1,f_2\}\\ B_2=G[\{v_1{v}_4\}]& F(B_2,\widetilde{H_1})=\{f_1,f_2\}\\ B_3=G[\{v_2{v}_7\}]& F(B_3,\widetilde{H_1})=\{f_1,f_2\}\\ B_4=G[\{v_2{v}_6\}]& F(B_4,\widetilde{H_1})=\{f_1,f_2\}\\ B_5=G[\{v_3{v}_7\}]& F(B_5,\widetilde{H_1})=\{f_1,f_2\}\\ B_6=G[\{v_4{v}_5\}]& F(B_6,\widetilde{H_1})=\{f_1,f_2\}\\ B_7=G[\{v_5{v}_8\}]& F(B_7,\widetilde{H_1})=\{f_1,f_2\}\\ B_8=G[\{v_6{v}_8\}]& F(B_8,\widetilde{H_1})=\{f_1,f_2\}\end{array}$$

(3) 取 $B_1$ 和 $f_1$.

(4) 取 $P_1=v_1{v}_3$.

(2)

$$\begin{array}{ll}{B}_1=G[\{v_1{v}_4\}]& F(B_1,\widetilde{H_2})=\{f_1,f_3\}\\ B_2=G[\{v_2{v}_7\}]& F(B_2,\widetilde{H_2})=\{f_3\}\\ B_3=G[\{v_2{v}_6\}]& F(B_3,\widetilde{H_2})=\{f_3\}\\ B_4=G[\{v_3{v}_7\}]& F(B_4,\widetilde{H_2})=\{f_1,f_3\}\\ B_5=G[\{v_4{v}_5\}]& F(B_5,\widetilde{H_2})=\{f_1,f_3\}\\ B_6=G[\{v_5{v}_8\}]& F(B_6,\widetilde{H_2})=\{f_1,f_3\}\\ B_7=G[\{v_6{v}_8\}]& F(B_7,\widetilde{H_2})=\{f_1,f_3\}\end{array}$$

(3) 取 $B_2$ 和 $f_3$.

(4) 取 $P_2=v_2{v}_7$.

(2)

$$\begin{array}{ll}{B}_1=G[\{v_1{v}_4\}]& F(B_1,\widetilde{H_3})=\{f_1\}\\ B_2=G[\{v_2{v}_6\}]& F(B_2,\widetilde{H_3})=\{f_3\}\\ B_3=G[\{v_3{v}_7\}]& F(B_3,\widetilde{H_3})=\{f_1,f_4\}\\ B_4=G[\{v_4{v}_5\}]& F(B_4,\widetilde{H_3})=\{f_1\}\\ B_5=G[\{v_5{v}_8\}]& F(B_5,\widetilde{H_3})=\{f_1\}\\ B_6=G[\{v_6{v}_8\}]& F(B_6,\widetilde{H_3})=\{f_1\}\end{array}$$

(3) 取 $B_1$ 和 $f_1$.

(4) 取 $P_3=v_1{v}_4$.

(2)

$$\begin{array}{ll}{B}_1=G[\{v_2{v}_6\}]& F(B_1,\widetilde{H_4})=\{f_3\}\\ B_2=G[\{v_3{v}_7\}]& F(B_2,\widetilde{H_4})=\{f_5\}\\ B_3=G[\{v_4{v}_5\}]& F(B_3,\widetilde{H_4})=\{f_1\}\\ B_4=G[\{v_5{v}_8\}]& F(B_4,\widetilde{H_4})=\{f_1\}\\ B_5=G[\{v_6{v}_8\}]& F(B_5,\widetilde{H_4})=\{f_1\}\end{array}$$

(3) 取 $B_1$ 和 $f_5$.

(4) 取 $P_4=v_2{v}_6$.

继续下去, 得到:

算法分析

算法分析(主要运算) :

(i) 找出块 $G$ 中的一个圈 $H_i$; $O(V^2)$
(ii) 确定 $G$ 中 $H_i$ 的片断以及它们对于 $H_i$ 的附着点; $O(V^2)$
(iii) 对于 $H_i$ 的每个面 $f$ 确定其周界; $O(V)$
(iv) 对于 $H_i$ 的每个片断 $B$, 确定 $F(B,H_i)$; $O(V)$
(v) 在 $H_i$ 的某个片断 $B$ 中求一条起点与终点均为附着点的一条路 $P_i$. $O(V)$

可证上述每一个算法均存在好算法, 因此平面性算法是好算法.