最后更新: 2024-04-06 21:41 查看: 126 次反馈刷题

平面图

## 平面图
所谓图的平面性问题, 就是一个图是否存在除结点处之外无边相交的平面图解。研究图的平面性问题很有实用价值, 例如考虑印刷电路的布线时就会遇到这样的问题。
定义 19 若无向图 $G$ 能画在平面上, 除结点处之外无边相交, 则称 $G$ 为可平面图或平面图。画出的无边相交的图称为 $G$ 的一个平面嵌入或平图。无平面嵌入的图称为非平面图。

显然, 若 $G$ 为平面图, 则其子图也是平面图; 若 $G$ 为非平面图, 则其母图也是非平面图; 若 $G$ 为平面图, 则其每个分支也为平面图, 因此, 只需研究连通平面图。

定义 20 平图 $G$ 的边所围成的区域, 若其内部不含 $G$ 的结点和边, 则称该区域为 $G$的面。每个平图恰有一个面为无界区域, 称为无限面或外部面, 其余的面称为有限面或内部面。包围一个面的边构成的回路称为该面的边界, 回路的长称为边界的长。

定义 21 若平面图 $G$ 中任意两个不相邻的结点之间加一条边, 所得图为非平面图, 则称 $G$ 为极大平面图。若非平面图 $G$ 中任意删除一条边, 所得图为可平面图, 则称 $G$ 为极小非平面图。
定理 21 (欧拉公式) 设 $G=(n, m)$ 是有 $r$ 个面的连通平面图, 则 $n-m+r=2$ 。
推论 设 $G=(n, m)$ 是有 $r$ 个面和 $k$ 个分支的平面图, 则 $n-m+r=k+1$ 。
定理 22 不少于 3 个结点的极大平面图 $G=(n, m)$ 有 $r$ 个面, 它的所有面的边界是 $K_3$,且有 $m=3 n-6, r=2 n-4$ 。
定理 23 不少于 4 个结点的极大平面图 $G$, 有 $\delta(G) \geq 3$ 。
定理 24 设连通平面图 $G=(n, m)$, 若 $G$ 的每个面的边界长度均为 $l(l \geq 3)$, 则 $m=\frac{l}{l-2}(n-2)$; 若 $G$ 的每个面的边界长度至少为 $l(l \geq 3)$, 则 $m \leq \frac{l}{l-2}(n-2)$ 。
定理 25 设 $G=(n, m)$ 为连通平面图, 若 $G$ 的每个面的边界长度至少为 3 , 则 $m \leq 3 n-6$; 若 $G$ 的每个面的边界长度至少为 4, 则 $m \leq 2 n-4$; 若 $G$ 的每个面的边界长度至少为 5 , 则 $m \leq \frac{5}{3} n-\frac{10}{3}$; 若 $G$ 的每个面的边界长度至少为 6 , 则 $m \leq \frac{3}{2} n-3$ 。
推论 $\mathrm{K}_5$ 和 $K_{3,3}$ 为非平面图。
定理 26 设 $G$ 为连通的简单平面图, 则 $G$ 中至少有一个结点 $v, \operatorname{deg}(v) \leq 5$ 。
上述定理都是判别平面图的必要条件, 而非充分条件, 但这些定理的逆否命题是判别非平面图的充分条件, 可用来判别一个图为非平面图。凡是平面图一定满足相应的不等式,但满足某一个不等式的末必都是平面图, 而不满足相应不等式的肯定不是平面图。如 $K_5$ 和 $K_{3,3}$ 。 凡是不超过 4 个结点的图必为平面图, 5 个结点和 6 个结点的非平面图就是 $K_5$ 和 $K_{3,3}$,它们是非平面图的两个最小模型, 非常重要, 是定理 27、28 的基础。定理 27、28 给出了平面图的一个十分简洁的特征, 但要用这个充要条件来具体判别一个图是否是平面图, 仍属不易。

若在图的一条边上插入一个新的 2 度结点, 使一条边变成两条边, 或对于两条关联于一个 2 度结点的边, 去掉这个结点, 使两条边合成一条边, 图的平面性都保持不变。
定义 22 若 $G_1$ 和 $G_2$ 同构, 反复插入或除去 2 度结点后仍同构, 则称 $G_1$ 和 $G_2$ 同胚。
定理 27 一个图是平面图当且仅当它不含与 $K_5$ 和 $K_{3,3}$ 同胚的子图。
定理 28 一个图是平面图当且仅当它不含经过边的收缩能成为 $K_5$ 和 $K_{3,3}$ 的子图。
平面图 $G$ 的对偶图 $G^*$ 构造如下: 在 $G$ 的每个面中取一点为 $G^*$ 的结点, 对 $G$ 中的每条边 $e$, 都取 $G^*$ 的一条边 $e^*$, 使 $e^*$ 只穿过 $e$ 一次 (不穿过 $G$ 的其他边) 并连接以 $e$ 为公共边的两个面中 $G^*$ 的结点 (两个面可能是一个面), 若 $e$ 为 $G$ 的断边, 则 $e$ 对应的边 $e^*$ 为 $G^*$ 的环; 若 $e$ 为 $G$ 的环, 则 $e$ 对应的边 $e^*$ 为 $G^*$ 的断边。显然, $G^*$ 是连通平面图。
若平面图 $G$ 的对偶图 $G^*$ 与 $G$ 同构, 则称 $G$ 为自对偶图。
定理 29 若 $G^*$ 为连通平面图 $G$ 的对偶图, 则 $n^*=r, m^*=m, r^*=n$ 。其中 $n, m, r$分别为 $G$ 的结点数、边数和面数, $n^* 、 m^* 、 r^*$ 分别为 $G^*$ 的结点数、边数和面数。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：欧拉图与哈密尔顿图

下一篇：覆盖集、独立集和匹配

本文对您是否有用？有用 (0) 无用 (0)