科数网
数学题库
数学试卷
数学组卷
在线学习
电子教材
科数
试题
试卷
学习
教材
VIP
你好
游客，
登录
注册
在线学习
离散数学
第五章 图论
对偶图
最后
更新:
2025-01-22 09:33
●
参与者
查看:
16
次
纠错
分享
参与项目
词条搜索
对偶图
定义 9.3 （几何对偶）设 $G$ 是平面图 $G$ 的平面嵌入，则 $G$ 的几何对偶 $G^*$ 构造如下。 （1）在 $G$ 的每一个面 $f$ 内恰放唯一的一个顶点 $f^*$ 。 （2）对 $G$ 的两个面 $f_i, f_j$ 的公共边 $x_k$ ，作边 $x_k{ }^*=\left\{f_i^*, f_j^*\right\}$ 与 $x_k$ 相交；得到的图记为 $G^*$ ，即 $G$ 的几何对偶（简称 $G$ 的对偶）。  如图 9.4 （a）和（b）中 $G$ 的边用实线表示，$G$的几何对偶 $G^*$ 的边用虚线表示，这一例子中 $G$ 就是 $G$ 。由定义 9.3 的过程可知，平面图 $G$ 的任何两个几何对偶必同构。又平面图 $G_1$ 与 $G_2$ 同构，但未必 $G_1{ }^*$ 与 $G_2{ }^*$ 同构，如图9．4（a）和（b）。 显然 $G^*$ 有多重边当且仅当 $\vec{G}$ 中存在两个面至 （a） （b）少有两条公共边。 图 9.4 由定义可知，若 $G$ 是连通平面图，则 $G^*$ 也是连通平面图，而且 $G$ 和 $G^*$ 的顶点数，面数和边数有下列简单的关系。 定理 9.4 设 $G$ 是有 $n$ 个顶点，$e$ 条边，$f$ 个面的连通平面图；又设 $G$ 的几何对偶 $G^*$ 有 $n^*$ 个顶点，$e^*$ 条边，$f^*$ 个面，则 $n^*=f, e^*=e, f^*=n$ 。 证明：前两个关系式可直接由 $G^*$ 的定义给出，第 3 个关系式由欧拉公式 $n-e+f=2$ 以及 $n^*-e^*+f^*=2$ 推出。 定理 $9.5 G$ 是连通平面图当且仅当 $G^{* *}$ 同构于 $G$ 。 证明留作习题。
上一篇：
平面图的特征
下一篇：
顶点着色
本文对您是否有用？
有用
(
0
)
无用
(
0
)
初中数学
高中数学
高中物理
高等数学
线性代数
概率论与数理统计
复变函数
离散数学
实变函数
数论
群论
纠错
题库
高考
考研
关于
下载
科数网是专业专业的数学网站。