平面图的判定

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：May.18 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

平面图的判定

    在 一文中，我们已经看到过判断非平面图的充分条件：对于 $3$ 阶以上的具有 $m$ 条边的简单图 $G$。如果 $G$ 满足以下条件之一:

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

    则 $G$ 不是平面图。

    在本节中我们将探究可平面图的充分必要条件。

相关概念

    在图 $G$ 的边上插入一个 $2$ 度顶点，使一条边分成两条边，称为图的 剖分 (Subdivision)。去掉一个图的 $2$ 度顶点，使关联它们的两条边合并成一条边，称将图 $G$ 在 $2$ 度顶点内收缩 (Contraction) 或 简化 (Simplify)。

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

    给定图 $G$，去掉 $G$ 中的自环，用单边代替平行边而得到的图称为 $G$ 的 基础简单图 (Fundamental Simple Graph)。

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

性质定理

    下面不加证明地给出一个关于平面图的判定定理:

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

    上面的定理告诉我们，对于一个图 $G$，如果我们可以基于它的子图剖分或者简化出含 $K_5$ 或者 $K_{3,3}$，那么这个图一定不可平面。

    基于这层定义，存在定理：

1. 图 $G$ 可平面，当且仅当它的基础简单图可平面;
2. 图 $G$ 可平面当且仅当 $G$ 的每个块都可平面

    证明:

    对于 (1) ，基于平面图的定义，结论显然。

    对于 (2)，必要性显然，下面证明充分性。

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

    当 $b=1$ 时，由条件可得，$G$ 包含的唯一的块可平面，也即是它本身可平面。

    当 $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$ 是可平面图。

    下面不加证明地给出一个基于子式的结论：

简单图 $G$ 是可平面图当且仅当 $K_{5}$ 和 $K_{3,3}$ 不是它的 minor。

    如下图所示，Peterson 图不是可平面的，因为它包含了 $K_{3,3}$ 作为它的 minor。