图论-平面图整理

复习平面图相关的一些基本点

基本概念

若图$G=(V, E)$存在一种图形表示，使得将它华仔平面上后没有两个结点重合，每条边不自身相交且美哟欧两条边在它们公共关联结点以外相交，则称$G$是具有平面性的图，简称平面图。

设$G$是平面图。若$G$的图形中由边围成的一个封闭区域，不能再分割称两个或两个以上的子区域，则称这个封闭区域为$G$的面。包围这个区域的边称为面的边界。面的边界数称为面的度。（割边计算度算两条边）

设$G=(V, E)$是一个平面图。构造图$G^*=(V^*, E^*)$如下:

$G$的面$F_1, F_2, … , F_f$与$V^*$中的点$u_1^*, u_2^*, … , u_f^*$一一对应；若面$F_i$和$F_j$邻接，则$u_i^*, u_j^*$邻接；弱$G$中有一条边$e$只是面$F_i$的边界，则$u_i^*$有有一环。称图$G^*$是$G$的对偶图。

设$G^*$是平面图$G$的对偶图，若$G^* \cong G$，称$G$为自对偶图。

对无环图$G$的每个顶点涂上一种颜色，使得相邻的顶点图不同的颜色，称为对图$G$的一种着色；若能用$k$种颜色给$G$的顶点着色，就称对$G$进行了$k$着色，也成$G$是$k$可着色的。若$G$是$k$可着色的，但不是$(k-1)$可着色的，就称$G$是$k$色图，并称这样的$k$为$G$的色数，即为$\chi(G)=k$。不混淆时，色数$\chi(G)$也可以简记为$\chi$。

为地域连通且相邻国家有一段公共边界的平面地图$G$的每一个国家图上一种颜色，使相邻的国家涂上不同的颜色，称为对$G$的一种面着色。若能用$k$种颜色给$G$的面着色，就称对$G$进行了$k$着色，或称$G$是$k$面可着色的。若$G$是$k$面可着色的，但不是$(k-1)$面可着色的，就称$k$为$G$的面色数，记为$\chi^*(G)=k$。

基本定理

若$G$是平面图，则$G$的任何子图都是平面图。若图$G$是非平面图，则$G$的任何母图也都是非平面图。 $K_n(n \geqslant 5)$和$K_{3,n}(n \geqslant 3)$都是非平面图。不是割边，必是两个面的公共界面；是割边必定是一个面的界面。平面图的所有面度之和等于边数的二倍。（类比握手定理）欧拉公式：设$G$是一个面数为$f$的连通平面图，则$n-m+f=2$。 对于具有$k(k \geqslant 2)$个连通分支的平面图$G$，有$n-m+f=k+1$设$G$是一个阶数大于2的$(n, m)$的连通简单平面图，则$m \geqslant 3n-6$ 任何简单连通平面图中，至少存在一个其度不超过$5$的结点。设$G$是一个围长$g$大于$2$的$(n, m)$连通平面图，则：$m \leqslant \frac{gn-2g}{g-2}$。$K_5, K_{3, 3}$是非平面图。Kuratowski定理：一个图是平面图，当且仅当它不包含与$K_5, K_{3, 3}$的细分图同构子图。设$G^*$是连通平面图$G$的对偶图，$n^*, m^*, f^*$分别为$G^*$和$G$的顶点数，边数和面数，则： $n^*=f$$m^*=m$$f^*=n$设$G^*$的顶点$u_i^*$位于$G$的面$R_i$中，则$d(u_i^*)=deg(R_i)$。$\chi(G)=1$，当且仅当$G$是零图。$\chi(K_n)=n$。设$G$至少含有一条边，则$\chi(G)=2$，当且仅当$G$是二部图。对于任意的图$G$（不含环），均有$\chi(G) \leqslant \Delta (G)+1$。地图$G$是$k$面可着色的，当且仅当它的对偶图$G^*$是$k$可着色的。任何连通平面图都是$5$可着色的。