平面图的对偶图

设 $G$ 是某个平面图的某个平面嵌入, 构建 $G$ 的对偶图 $G^{\ast }$ 如下: 在 $G$ 的面 $R_i$ 中放置 $G^{\ast }$ 的顶点 $v^{\ast }$; 设 $e$ 为 $G$ 的任意一条边, 若 $e$ 在 $G$ 的面 $R_i,R_j$ 的公共边界上, 作边 $e^{\ast }$ 关联位于 $R_i,R_j$ 中的顶点 $v_i^{\ast },v_j^{\ast }$, 即 $e^{\ast }=(v_i^{\ast },v_j^{\ast })$; 若 $e$ 是 $G$ 中的桥且在面 $R_i$ 的边界上, 则 $e^{\ast }=(v_i^{\ast },v_i^{\ast })$.

• $G\ast$ 是平面图, 且是平面嵌入.
• $G\ast$ 是连通图.
• 若边 $e$ 为 $G$ 中的环, 则 $G^{\ast }$ 与 $e$ 对应的边 $e^{\ast }$ 为桥
• 若 $e$ 为桥, 则 $G^{\ast }$ 中与 $e$ 对应的边 $e^{\ast }$ 为环.
• 在多数情况下 $G^{\ast }$ 为多重图 (含平行边的图).
• 同构的平面图的对偶图不一定是同构的.

定理 设 $G^{\ast }$ 是连通平面图 $G$ 的对偶图, $n,m,r$ 分别为顶点数, 边数, 面数, 则 $n^{\ast }=r,m\ast =m,r\ast =n$, 设 $G^{\ast }$ 的顶点 $v_i^{\ast }$ 位于 $G$ 的面 $R_i$ 中, 则 $d_{G^{\ast }}(v_i^{\ast })=\mathrm{deg}(R_i)$.

定理 设 $G^{\ast }$ 是具有 $k(k\ge 2)$ 个连通分支的平面图 $G$ 的对偶图, 则 $n^{\ast }=r,m^8=m,r^{\ast }=n-k+1$, 设 $G^{\ast }$ 的顶点 $v_i^{\ast }$ 在 $G$ 的面 $R_i$ 中, 则 $d_{G^{\ast }}(v_i^{\ast })=\mathrm{deg}(R_i)$.

自对偶图

设 $G^{\ast }$ 是平面图 $G$ 的对偶图, 若 $G^{\ast }\cong G$, 则成为子对偶图.

指向原始笔记的链接

轮图

在 $n-1(n\ge 4)$ 边形中放置一个顶点, 使得这个顶点与所有顶点均相邻, 所得到的 $n$ 阶简单图称为 $n$ 阶轮图. 记为 $W_n$.

• 轮图都是 自对偶图.

指向原始笔记的链接