图论4-Planarity

Planarity

一个平面图(planar)被定义为：在平面上绘制没有交叉的图；

若图$G$不能在平面上绘制或表示，称为非平面图；

若两个图可以在同一个图的边插入一个2度的新顶点来获得，则这两个图是同胚的(homeomorphic);

称图$H$紧缩于(contractible to)$K_{3,3}$或$K_5$， 如果我们将$H$的边收缩能够得到$K_{3，3}$或$K_5$;

Theorem(Kazimierz Kuratowski)

$K_{3,3},K_5$是非平面的；进一步地，如果一个图是平面图，当且仅当其没有子图和$K_{3,3}$或$K_5$同胚；

Corollary

一个图是平面的当且仅当它不包含可紧缩到$K_5$或$K_{3,3}$的子图;

proof:考虑命题反面

Crossing

图$G$的交叉数${\rm cr}(G)$定义为将$G$绘制在平面上是发生的最小交叉数；

显然${\rm cr}(K_5)={\rm cr}(K_{3,3})=1$;

图的厚度$t(G)$定义为将$G$分解成若干个平面图的并的最小数量；

Theorem

对于简单图$G$,顶点数$n\ge 3$,边数$m$; 则厚度存在下界
$$
t(G)\ge \lceil \frac {m}{3n-6} \rceil
$$
proof:只需证$m\le (3n-6)t(G)$;

Bound

定义一个平面图的区域$R$的边界度(bound degree)为$b(R)$ 为遍历区域的边界记录的图的边数；

假设平面图将平面划分为$f$个区域，称$f$为平面图的面数；

Theorem

假设平面图$G$的面最小边界度为$l\ge 2$,则
$$
lf\le C=\sum_{R} b_R\le 2m
$$
对于不少于3个顶点的简单平面图，则
$$
m\le \frac{l}{l-2}(n-2)
$$
对于一般的平面图，自然有
$$
m\le 3n-6
$$
对于二部平面图，有
$$
m\le 2n-4
$$

Theorem(Euler)

若图$G$是一个具有$n$个顶点，$m$条边和$f$个面的连通平面图，则满足一下公式：
$$
n-m+f=2
$$
proof:若图有圈，删除一条圈中的边导致$m$和$f$均减少1，且不丢失连通性；重复上述操作划归为树的情况，即$m=n-1,f=1$
note:由此可证明$K_{3,3},K_5$不是连通图；

Corollary

$K_{m,n}$是平面图当且仅当$\min {m,n}\le 2$;$K_n$是平面图当且仅当$n\le 4$;

Corollary

对于平面图$G$，有
$$
n-m+f=\omega(G)+1
$$

Polyhedra

一个多面体(polyhedron)定义为一个实体，它被有限个面包围，每一个面都是多边形；
一个多面体是凸的，若连接两个顶点的险段都完全包含在多面体内；
多面体可以用一个平面图表示；

一个多面体是正则的(regular)，若存在整数$n\ge 3, m\ge 3$,每个顶点均有$r$个面在此相遇，而且每个面的边界上均有$l$条边；

Theorem

假定正多面体的顶点度为$r$，每个面度为$l$，则$(l,r)$仅有如下取值：
$$(3,3),(3,4),(4,3),(3,5),(5,3)$$
proof:注意到
$$
n-m+f=2 \
2m=lf=nr
$$

导出
$$
(l-2)(r-2)<4
$$

Fullerene

一个烯(fullerene)的特征如下：

• 由五边形和六边形构成；
• 每个顶点处有3个面相遇；

可以确定，总共12个五边形；

proof:注意到
$$
n-m+f=2\
f=f_5+f_6\
2m=3n=5f_5+6f_6
$$

Genus

定义一个表面的亏格数(genus)$g$，如果其拓扑同构于有$g$个柄(handle)或者交叉帽(cross-caps)一个球体(sphere);

这里给出结论，$K_5$和$K_{3,3}$是亏格数为1的图(toroidal graphs)；

Theorem

图$G$的亏格数$g$不超过其交叉数${\rm cr}(G)$;

Theorem

对于可定向的连通图$G$，亏格数为$g$,顶点数为$n$,边数为$m$，面数为$f$,满足
$$
n-m+f=2-2g
$$

Theorem

对于不少于4个顶点的可定向的连通图$G$，边数为$m$,顶点数为$n$，其亏格数满足
$$
g(G)\ge \lceil \frac{m-3n}{6}\rceil +1
$$