Mengzelev's Blog

图论学习笔记-平面图与着色

Word count: 1,299 / Reading time: 5 min
2018/12/13 Share

平面图

平面图(planar graph):如果$G$能够被画在一个平面上而使得任何两条边都不会交叉

平图(plane graph):如果$G$是平面图且$G$的任何两条边都不交叉

平面图的例子:cycle, path, star, tree

区域(regions):一个平图把平面分成一些连通片
外区域(exterior region):每个平图中总有的一个无界的区域
边界(boundary):在一个平图中,顶点和边斗鱼某个给定区域$R$关联的子图称为是$R$的边界

割边总是恰好在一个区域的边界上
非割边一定位于两个区域的边界上

如果$G$是一个至少含有三条边的连通平图,则$G$的而每个区域的边界至少含有三条边

定理9.1(Euler恒等式):如果$G$是一个阶为$n$,边数为$m$且含有$r$个区域的连通平图,则$n-m+r=2$

定理9.2:如果$G$是一个阶为$n\ge 3$且边数为$m$的平面图,则$m\le 3n-6$。(平面图的必要条件,非平面图的充分条件)
逆否命题:设$G$阶为$n$,若$m>3n-6$,则$G$是非平面图。
注:满足$m\le 3n-6$的不一定是平面图

推论9.3:每个平面图含有一个度小于或等于5的顶点。

推论9.4:完全图$K_5$是非平面的。

极大平面的(maximal planar):若$G$是平面的,且在$G$的任意两个不邻接的顶点之间添加一条边即可产生一个非平面图。
另一种表述:$G$是平面的,但$G$不是任何一个平面图的生成子图
极大平面图满足$m=3n-6$

定理9.5:图$K_{3,3}$是非平面的

细分(subdivision): 如果有一个或多个度为2的顶点被插入到$G$的一条或多条边中,则称图$G’$是图$G$的一个细分

定理9.7(Kuratowski定理):一个图$G$是平面图当且仅当$G$不含$K_5$,$K_{3,3}$,或者$K_5$或$K_{3,3}$的一个细分作为子图。

如果一个图$G$含有(1)至多4个度大于或等于4的顶点(2)至多5个度大于或等于3的顶点,则$G$必定是平面的。

顶点染色

对偶(dual):每张地图都有一个与之关联的图$G$,称为该地图的对偶,其中$G$的顶点即为地图的区域,$G$的两个顶点是邻接的当且仅当它们所对应的区域是相邻的
每张地图的对偶图都是平面图,每个连通的平面图都是某个地图的对偶。

真染色(proper coloring):给$G$的顶点分配一些颜色(来自于某个颜色集合),是的每个顶点都能分配到一种颜色,且邻接的顶点被染成不同的颜色,简称为染色(coloring)

色数(chromatic number)$\chi(G)$:在$G$的所有染色中,所用的最少颜色数

$k$可染色的(k-colorable):如果能用一个含有$k$种颜色的集合给$G$的顶点染色,则称$G$是$k$可染色的(k-colorable),应用$k$种颜色的染色称为是$k$染色(k-coloring)

若$\chi(G)=k$,则$G$也称为是$k$色的(k-chromatic),并且$G$的每个$k$染色都是$G$的最小染色(minimum coloring)

定理10.1(四色定理):每个平面图的色数至多是4

色类(color classes):若$G$是一个$k$色图,则可以把$V(G)$划分成$k$个独立集$V_1,V_2,…,V_k$,此时这些顶点集称为色类。

定理10.2:图$G$的色数是2当且仅当$G$是一个非空的二部图。

(复习:定理1.12:图$G$是二部的当且仅当其不含奇圈)
若$G$含有奇圈,则$\chi(G)\ge 3$

$n$阶图$G$的色数为$n$当且仅当$G=K_n$

证明$\chi(G)=k$,必须证明:

  • 至少需要$k$种颜色来为$G$染色(不能用$k-1$种颜色为$G$染色)
  • 存在$G$的一个$k$染色

若$H$为$G$的一个子图,则$\chi(H)\le\chi(G)$

团(clique):$G$的一个完全子图
团数(clique number)\omega(G):图$G$中最大团的阶数
$\alpha(G)=k$当且仅当$\omega(G)=k$

定理10.5:对每个$n$阶图$G$:$$\chi(G)\ge\omega(G), \chi(G)\ge\frac{n}{\alpha(G)}$$
(给出了图$G$的色数的下限)

图$G$的染色可以看成是$V(G)\to\mathbb{N}$的一个函数$c:V(G)\to\mathbb{N}$,使得当$uv\in E(G)$时,$c(u)\neq c(v)$

定理10.7:对于每个图$G$,$\chi(G)\le 1+\Delta(G)$。($\Delta(G)$为$G$的最大度)

定理10.8(Brooks定理):对每个非奇圈也非完全的连通图$G$,$\chi(G)\le\Delta(G)$

定理10.9:对于每个图$G$,$\chi(G)\le 1+\max{\delta(H)}$,其中$\max$取遍$G$的所有诱导子图$H$。

影子图(shadow graph)$S(G)$:通过在$G$中,对其每个顶点$v$,增加一个新的顶点$v’$,称之为$v$的影子顶点(shadow vertex)

定理10.10:对于每个整数$k\ge 3$,都存在一个色数为$k$的无三角的图。

CATALOG
  1. 1. 平面图
  2. 2. 顶点染色