科数网
学习首页
高中数学
高中物理
微积分
线性代数
概率论
赞助
在线教程
图论
平面图
最后更新:
2024-04-06 21:41
查看:
45
次
下载
编辑本文
科数网
平面图
## 平面图 所谓图的平面性问题, 就是一个图是否存在除结点处之外无边相交的平面图解。研究图的平面性问题很有实用价值, 例如考虑印刷电路的布线时就会遇到这样的问题。 定义 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
)
科数网知识库旨在打造一个可以顺序阅读的在线电子学习教程,点击顶部的
编辑本文
来完善本文,如果本文对您有用,也欢迎
赞助我们
0
篇笔记
写笔记
更多笔记
提交笔记