特殊平面图与平面图的对偶图

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

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

目录

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

正在加载目录...

一些特殊平面图

极大平面图及其性质

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

    设 $G$ 是简单可平面图, 如果:

1. $G$ 是 $K_i$ $(1 \le i le 4)$;或者
2. 在 $G$ 的任意非邻接顶点间添加一条边后，得到的图均是非可平面图

    则称 $G$ 是 极大可平面图 (Maximal Planar Graph)。

    极大可平面图的平面嵌入称为 极大平面图 (Maximal Plane Graph)。

    值得强调的是，只有在简单图的前提下定义极大平面图才有意义。

    下面给出一些关于极大平面图的性质定理。

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

    证明:

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

    然后证明当极大平面图 $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^{\star}$，它比 $G$ 多一条边，这与 $G$ 的极大性相矛盾。

    下面证明极大平面图的一个重要性质:

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

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

    证明:

    首先证明 $1 \iff 2$: 由 $G$ 是简单图可知，$G$ 的每个面的次数至少是 $3$ (i.e. 由于不存在自环，每个面的次数不及 $3$ 是围不出来一个面的)。假设 $G$ 中的某个面 $f$ 的次数大于等于 $4$，如下图所示:

    若 $v_1$ 和 $v_3$ 不邻接，则将边 $v_1v_3$ 画在 $f$ 内，得到边数更多的平面图，这与 $G$ 是极大平面图相矛盾。

    然后证明 $2 \iff 3$: 由次数公式可得 $2m=\sum_{f \in \Phi} \deg (f) \ge 3\Phi$，将这个结论代入平面图的欧拉公式 $n-m+\Phi =2$ 可以得到: $m \le 3n-6$。而反过来证明，$m=3n-6$ 意味着 $2m=3\Phi$，即每个面的次数都是 $3$。

    在我们上一篇文章中介绍的正多面体的平面图中，正四、八、二十面体均为极大平面图。

极大外平面图及其性质

    若一个可平面图 $G$ 存在一种平面嵌入，使其所有顶点均在某个面的边界上，称该图为 外可平面图 (Outerplanar Graph)。外可平面图的一种外平面嵌入，称为 外平面图 (Outerplane Graph)。

    设 $G$ 是一个简单外可平面图，若在 $G$ 中任意不邻接顶点间添上一条边后，$G$ 成为非外可平面图，则称 $G$ 是 极大外可平面图(Maximal Outerplanar Graph)。极大外可平面图的外平面嵌入，称为 极大外平面图 (Maximal Outerplane Graph)。

    下面给出一些关于极大外平面图的性质。

    首先不加证明地给出一个引理:

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

    下面来看定理:

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

    证明:

    对 $G$ 的阶数进行归纳。当 $n=3$ 时，$G$ 是三角形，显然只有一个内部面;

    设当 $n=k$ 时，结论成立。

    当 $n=k+1$ 时，首先由 3 可以知道 $G$ 必有一个 $2$ 度顶点 $v$ 在 $G$ 的外部面上。考虑 $G-v$，$G-v$ 有 $k$ 个点，由归纳假设可知，$G-v$ 有 $k-2$ 个内部面。由于在边界上删除一个 $2$ 度顶点会减少图上的一个面，因此可以知道 $G$ 上有 $k-1$ 个内部面，于是定理得证。

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

    证明:

    首先证明必要性:

    证明 $G$ 的 (外部面的) 边界是圈。容易知道 $G$ 的外部面边界一定为闭迹 (i.e. 边不重的首尾相同的途径)，也即不存在上图所示的情况，否则 $G$ 不能为极大外平面图。设 $W=v_1v_2...v_nv_1$ 是 $G$ 的外部面边界。若 $W$不是圈, 则存在 $i$ 与 $j$，使 $v_i = v_j = v$。此时，$G$ 可以示意如下:

    $v_{i−1}$ 与 $v_{i+1}$ 不能邻接，否则 $W$ 不能构成 $G$ 的外部面边界。这样，我们连接 $v_{i−1}$ 与 $v_{i+1}$:

    这样一来我们得到一个新外平面图，这与 $G$ 的极大性矛盾。

    然后证明 $G$ 的内部面是三角形。

    首先证明 $G$ 的内部面的边界必须是圈。因为，$G$ 的外部面的边界是生成圈，所以 $G$ 是 $2$ 连通的。由上一篇文章中的 Theorm 13 可知，一个简单连通平面图是 $2$ 连通的当且仅当它的每个面的边界是圈，故 $G$ 的每个面的边界必是圈。

    其次, 设 $C$ 是 $G$ 中任意一个内部面的边界。如果 $C$ 的长度大于等于 $4$，则 $C$ 中一定存在不邻接顶点，连接这两点得到一个 新平面图，这与 $G$ 的极大性矛盾。又由于 $G$ 是简单图，所以 $C$ 的长度只能为 $3$。

    然后证明充分性:

    设 $G$ 是一个外平面图，内部面是三角形，外部面是圈 $W$。

    如果 $G$ 不是极大外平面图，那么存在不相邻顶点 $u$ 与 $v$，使得 $G+uv$ 是外平面图。但是, $G+uv$ 不能是外平面图。因为若边$uv$ 经过 $W$ 的内部，则它要与 $G$ 的其它边相交; 若 $uv$ 经过 $W$ 的外部，导致所有点不能在 $G$ 的同一个面上。

    所以 $G$ 是极大外平面图。

平面图的对偶图

    给定平面图 $G$，$G$ 的 对偶图 (Dual) $G^{\star}$ 如下构造:

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

    举例如下:

    平面图的对偶图和原图的关系如下:

• $G^{\star}$ 的顶点数等于 $G$ 的面数;
• $G^{\star}$ 的边数等于 $G$ 的边数;
• $G^{\star}$ 的面数等于 $G$ 的顶点数;
• $d(v^{\star}) = \deg (v^{\star})$

    下面探讨关于平面图的对偶图的性质:

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

    证明:

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

    用一条曲线 $l$ 把 $v_i$ 和 $v_j$ (注: $v_i$ 和 $v_j$ 分别为 $v_i^{\star}$ 与 $v_j^{\star}$ 对应在 $G$ 中的面) 连接起来，且 $l$ 不与 $G$ 的任意顶点相交。显然, 曲线 $l$ 从 $v_i$ 到 $v_j$ 经过的面边序列，对应从 $v_i^{\star}$ 到 $v_j^{\star}$ 的点边序列，该点边序列就是该两点在 $G^{\star}$ 中的通路。

    由上述定理可知，$(G^{\star})^{\star}$ 不一定同构于 $G$，因为「原图不连通」$\rightarrow$ 「对偶图连通」$\rightarrow$「对偶(对偶图)连通」。

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

    首先证明必要性。由于 $G$ 是平面图，由 6，$G^{\star}$ 是连通的。而由 $G^{\star}$ 是平面图，再由 6，$(G^{\star})^{\star}$ 是连通的。所以由 $(G^{\star})^{\star} \cong G$ 得，$G$ 是连通的。

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

    值得注意的是，同构的平面图可以有不同构的对偶图。