平面图

$G$ 是平面图当且仅当 $G$ 除顶点外能无边相交画在平面上.

• $K_5,K_{3,3}$ 都不是平面图.
• 平面图的子图都是平面图, 非平面图的母图都是非平面图.
• 平行边和环不影响平面性.

平面图的面

$G$ 的面指由 $G$ 的平面嵌入的边将平面划分成的区域.

无限面

平面图面积无限的面, 表示为 $R_0$.

指向原始笔记的链接

有限面

平面图中面积有限的面, 表示为 $R_1,R_2,...,R_k$.

指向原始笔记的链接

平面图面的边界

包围 $R_i$ 的所有边组成的回路组.

指向原始笔记的链接

平面图面的次数

$R_i$ 边界的长度, 表示为 $\mathrm{deg}(R_i)$.

指向原始笔记的链接

定理 平面图各面次数之和等于边数的两倍, ${\sum }_{i=1}^R\mathrm{deg}(R_i)=2m$

指向原始笔记的链接

极大平面图

若在简单平面图 $G$ 中任意两个不相邻的顶点之间藤甲一条新边, 所得到的图为非平面图, 则称 $G$ 为极大平面图.

若 $G$ 中没有不相邻顶点, $G$ 显然是极大平面图.

定理 极大平面图是连通的, 且 $n\ge 3$ 阶极大平面图中不可能有割点和桥.

定理 $G$ 为 $n\ge 3$ 阶简单连通的平面图, $G$ 为极大平面图当且仅当 $G$ 的每个 面的次数 均为 3.

指向原始笔记的链接

欧拉公式

定理 设 $G$ 为 $n$ 阶 $m$ 条边 $r$ 个面的连通平面图, 则 $n-m+r=2$.

定理 设 $G$ 为具有 $k\ge 2$ 个 连通分支 的平面图, 则 $n-m+r=k+1$.

定理 $G$ 为连通的平面图, $deg(R_i)\ge l(l\ge 3)$, 则 $m\le \frac{l}{l-2}(n-2)$.

定理 在具有 $k(k\ge 2)$ 个连通分支的平面图中, $m\le \frac{l}{l-2}(n-k-1)$.

定理 设 $G$ 为 $n(n\ge 3)$ 阶 $m$ 条边的极大平面图, 则 $m=3n-6$.

推论 设 $G$ 为 $n(n\ge 3)$ 阶 $m$ 条边的简单平面图, 则 $m\le 3n-6$.

定理 设 $G$ 为简单平面图, 则 $\delta (G)\le 5$.

指向原始笔记的链接

图的同胚

若 $G_1,G_2$ 同构, 或经过反复插入或消去 2 度顶点后同构, 则称两图同胚.

指向原始笔记的链接

定理 $G$ 是平面图 $\iff$ $G$ 中不含与 $K_5$ 或 $K_{3,3}$ 同胚的子图.

定理 $G$ 是平面图 $\iff$ $G$ 中无可收缩成 $K_5$ 或 $K_{3,3}$ 的子图.

平面图的对偶图

设 $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$.

• 轮图都是 自对偶图.

指向原始笔记的链接

指向原始笔记的链接