第六章 平面图
6.1 概念
- 平面图：如果能把图\(G\)画在平面上，使得除顶点外，边与边之间没有交叉，称\(G\)可嵌入平面，或称\(G\)是可平面图。可平面图\(G\)的边不交叉的一种画法，称为\(G\)的一种平面嵌入，\(G\)的平面嵌入表示的图称为平面图
- 面：一个平面图\(G\)把平面分成若干连通片，这些连通片称为\(G\)的区域，或\(G\)的一个面。\(G\)的面组成的集合用\(\psi\)表示；无界的区域称为外部面或无限面。
- 次数：某面\(f\)的边界中含有的边数（割边计算2次）称为该面\(f\)的次数, 记为\(deg(f)\)
6.2 性质
- 次数公式：设\(G=(n, m)\)是平面图，则\(\sum deg(f)=2m\)
- 平面图Euler公式：设\(G=(n, m)\)是连通平面图，\(\phi\)是\(G\)的面数，则：\(n-m+\phi =2\)
- 推论1 设\(G\)是具有\(\phi\)个面\(k\)个连通分支的平面图，则\(n-m+\phi =k+1\)
- 推论2 设\(G\)是具有\(n\)个点\(m\)条边\(\phi\)个面的连通平面图，如果对\(G\)的每个面\(f\) ,有\(deg (f) ≥ l ≥3\)，则\(\displaystyle m\leq \frac{l}{l-2}(n-2)\)
- 推论2也可以表述为设\(G=(n, m)\)是连通图，如果\(\displaystyle m> \frac{l}{l-2}(n-2)\)，则\(G\)是非可平面图
- 推论3 设\(G\)是具有\(n\)个点\(m\)条边\(\phi\)个面的简单平面图，则\(m\leq 3n-6\)
- 推论4 设\(G\)是具有\(n\)个点\(m\)条边的连通平面图，若\(G\)的每个圈均由长度是\(l\)的圈围成，则\(m(l-2)=l(n-2)\)
- 推论5 \(G\)是具有\(n\)个点\(m\)条边的简单平面图，则\(\delta \leq 5\)
6.3 判定
- 对于简单图\(G=(n, m)\)，如果\(m>3n-6\)，则\(G\)是非可平面的
- 对于简单连通图\(G=(n, m)\)，如果每个面次数至少为\(l\geq 3\),且\(\displaystyle m>(n-2)\frac{l}{l-2}\)，则\(G\)是非可平面的
- 库拉托斯基定理：\(G\)是可平面的当且仅当\(G\)不含有与\(K_5\)和\(K_{3,3}\)同胚的子图
- 瓦格纳定理：\(G\)是可平面的当且仅当\(G\)不含有能够收缩成\(K_5\)和\(K_{3,3}\)的子图
- 图\(G\)是可平面的，当且仅当它的基础简单图是可平面的
- 给定图\(G\), 去掉\(G\)中的环，用单边代替平行边而得到的图称为\(G\)的基础简单图
- 图\(G\)是可平面图当且仅当\(G\)的每个块是可平面图
