在线学习
重点科目
初中数学
高中数学
高等数学
线性代数
概率统计
高中物理
数学公式
主要科目
复变函数
离散数学
数学分析
实变函数
群论
数论
未整理科目
近世代数
数值分析
常微分方程
偏微分方程
大学物理
射影几何
微分几何
泛函分析
拓扑学
数学物理
趣味数学
科数网
题库
教材
高考区
考研区
VIP
科数网
题库
在线学习
高中数学
高等数学
线性代数
概率统计
高中物理
复变函数
离散数学
你好
游客，
登录
注册
在线学习
离散数学
第五章 图论
对偶图
最后
更新:
2025-01-22 09:33
查看:
59
次
反馈
刷题
对偶图
定义 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
)
纠错
高考
考研
关于
赞助
公式
科数网是专业专业的数学网站。