Graph Theory and Network Algorithm 5 染色理论

发表于 2020-11-22 更新于 2022-04-08 分类于 UCAS ， Courses 阅读次数：

图论与网络算法 (070105M04003H)，染色理论。

染色理论

概念

边正常k-染色（proper edge k-colouring）：映射$c:E(G)\rightarrow\{1,2,...,k\}:\forall i\in\{1,2,...,k\},c^{-1}(i)$是匹配或空集；
- 令$E_i=c^{-1}(i)=\{e\in E(G)|c(e)=i\},i=1,2,...,k$，则$G$的一个边正常k-染色可看成是边集的一种划分$c=(E_1,E_2,...,E_k)$，其中每个$E_i$是匹配或空集。
边k色可染的（edge k-colourable）：$G$存在边正常k-染色；
- 每个无环非空图的边必$\epsilon$色可染；
- 若$G$是边k色可染的，则$\forall l\ge k$，$G$必是边l色可染的。
边色数（edge chromatic number）：设无环边非空图$G$，正整数$\chi'(G)=\min\{k|G$是边k色可染的$\}$；
- $\chi'(K_{2n})=2n-1=\Delta(K_{2n})$；（因为$K_{2n}$的边可划分为$2n-1$个无公共边的匹配）
- $\chi'(G)\ge\Delta(G)$。
改进：设$c$与$c'$都是$G$的边k-染色（未必是正常染色）。若$c(v),c'(v)$满足$\sum\limits_{v\in V(G)}c'(v)>\sum\limits_{v\in V(G)}c(v)$，则称$c'$是对$c$的一个改进；
- 对于非空无环图$G$的一个边k-染色$c$，用$c(v)$表示顶点$v$处出现不同颜色的数目；
- 此求和越大表明染色越均匀。
最佳边k-染色：不能改进的边k-染色。（可能不是正常染色）
第一类图：满足$\chi'(G)=\Delta(G)$的简单图；第二类图：满足$\chi'(G)=\Delta(G)+1$的简单图；
- 当$\upsilon(G)$充分大，几乎所有的非空简单图都是第一类图。

顶点正常k-染色（proper vertex k-colouring）：映射$\pi:V(G)\rightarrow\{1,2,...,k\}:\forall i\in\{1,2,...,k\},\pi^{-1}(i)$是独立集或空集；
- 令$V_i=\pi^{-1}(i)=\{x\in V(G)|\pi(e)=i\},i=1,2,...,k$，则$G$的一个顶点正常k-染色可看成是顶点集的一种划分$\pi=(V_1,V_2,...,V_k)$，其中每个$V_i$是独立集或空集。
点k色可染的（vertex k-colourable）：$G$存在顶点正常k-染色；（简称k色可染的）
- 每个无环图必$\upsilon$色可染；
- 若$G$是k色可染的，则$\forall m\ge k$，$G$必是m色可染的。
点色数（ chromatic number）：设无环边图$G$，正整数$\chi(G)=\min\{k|G$是k色可染的$\}$；
- 零图（$V(G)=\varnothing$）的色数定义为$0$
- $\chi(G)=1\Longleftrightarrow G=\bar{K}_\upsilon,v\ge1$（即$G$是空图但非零图）；
- $\chi(G)=2\Longleftrightarrow G$是非空二部图；
- $\chi(G)=\upsilon(G)\Longleftrightarrow G\supseteq K_\upsilon$；
- $\chi(C_{2n+1})=3$；
- $\chi(G)\ge3\Longleftrightarrow G$含有奇圈。
临界k-色图（critical k-chromatic graph）：无环边图$G:\chi(G)=k\ge1,\forall H\subset G:\chi(H)<k$；
- 临界k-色图（$k=1,2,...$）统称为色临界图；
- 临界k-色图即k色极小色图，即其是k色的，但任意删去一顶点或边后色数就会减少。
- 临界1色图$\Longleftrightarrow K_1$；
- 临界2色图$\Longleftrightarrow K_2$；
- 临界3色图$\Longleftrightarrow$ 奇圈；
- 每个k-色图都有子图为临界k色图；
- 每个色临界图都是连通的简单图。

定理

无环边非空连通图$G$，且非奇圈$\Longrightarrow \exists G$的边2-染色，使得所用的两种色在每个度$\ge2$的顶点处都出现。

设$c=(E_1,E_2,...,E_k)$是非空无环图$G$的一个最佳边k-染色，且存在一个顶点$u$及两种颜色$i,j$，色$i$不在$u$处出现，而色$j$在$u$处出现了至少两次，则$G[E_i\cup E_j]$中含$u$的连通分支必是奇圈。

Theorem 6.1.1 (König, 1916) 二部图$G \Longrightarrow \chi'(G)=\Delta(G)$。

反证，若不等，则有$\chi'(G)>\Delta(G)$，设出一个最佳$\Delta$边-染色，则其一定不是正常染色，故则$\exists u \in V(G):c(u)<d(u)\le\Delta$，则一定有某色在$u$没有出现，某色在$u$出现了两次，故$G$有奇圈，与二部图矛盾；

也可由二部图边集可分解为$\Delta(G)$无公共边的匹配直接证明。

Theorem 6.1.4 (Vizing, 1964) 无环边非空简单图$G \Longrightarrow \Delta(G)\le\chi'(G)\le\Delta(G)+1$。

Theorem 6.2.1 色临界图的顶点割集不是团。

团：$Q\subset V(G):G[Q]$是完全图；

反证法，假设$G$有一个点割集$S$是团，考虑$G-S$的连通分支，将$G[S]$按原连接方式与各个连通分支相连，则所得的每个图都是$k-1$色的，总可调整这些图的染色方式使其合在一起为$k-1$色的，矛盾。

色临界图都是块（即不含割点）。

反证，若否，割点构成一个团，矛盾。

$\upsilon(G)\ge3$的色临界图都是2连通的。

若临界k色图$G$由$2$顶点割集$\{u,v\}$，则$u$与$v$不相邻。

Theorem 6.2.2 (Dirac, 1952) 设临界k色图$G(k\ge2)\Longrightarrow \kappa'(G)\ge k-1$。

临界k色图$G\Longrightarrow \delta(G)\ge k-1$。
任何k色图至少由$k$个顶点的度$\ge k-1$。

任何k色图$G$的临界k色图$H$至少有$k$的顶点，且$\delta(G)\ge\delta(H)\ge k-1$。

Theorem 6.2.3 无环边简单图$G\Longrightarrow \chi(G)\le\Delta(G)+1$。

设$\chi(G)=k,H$是$G$临界k色子图，则$\delta(G)\ge k-1$，故$\Delta(G)\ge\Delta(H)\ge\delta(H)\ge k-1=\chi(G)-1$。

等号是可以取到的，如奇圈和完全图，且只有这两类图可以取到。

Theorem 6.2.4 (Brooks, 1941) 无环边简单图$G$非奇圈和完全图$\Longrightarrow \chi(G)\le\Delta(G)$。

有一些图离上界相差很远，如星图$K_{1,n}$的色数为$2$而$\Delta(K_{1,n})=n$。

Theorem 6.2.5 设连通简单图$G$的度序列为$d_1\ge d_2\ge...\ge d_\upsilon\Longrightarrow \chi(G)\le1+\max\limits_{i}\min\{d_i,i-1\}$。

Theorem 6.2.6 无环边图$G\Longrightarrow \chi(G)\le1+\max\limits_{H\subseteq G}\delta(H)$。

空图易证，故可设$\chi(G)=k\ge2$，设临界k色子图$H$，$\chi(G)=\chi(H)=k\le1+\delta(H)\le1+\max\limits_{H\subseteq G}\delta(H)$。

Theorem 6.2.7 无环边图$G\Longrightarrow \chi(G)\le1+l(G)$。（$l(G)$为$G$中最长路的长度）

设临界k色子图$H$，则$\delta(H)\ge k-1$。取$H$中最长路，可证$H$有长为$\delta(H)+1$的圈，则有长为$\delta(H)$的路，故$l(G)\ge\delta(H)\ge k-1$，从而$\chi(G)=k\le1+l(G)$。

Theorem 6.2.8 无环边图$G\Longrightarrow \chi(G)\ge\frac{\upsilon^2}{\upsilon^2-2\epsilon}$。

按色数$k$设$V(G)$的划分：$\pi=(V_1,V_2,...,V_k)$，将邻接矩阵按划分写成分块的形式，分析其中零元素的个数应$\ge\sum\limits_{i=1}^k|V_i|^2$（对角的分块矩阵中元素全为0）$\ge(\sum\limits_{i=1}^k|V_i|)^2$（Cauchy不等式），而实际零元素个数为$\upsilon^2-2\epsilon$个，结合两式得证。

色数的下界是不好证的。

Theorem 6.2.9 无环边图$G\Longrightarrow$

$\chi(G)+\alpha(G)\le\upsilon+1$；
$\chi(G)\cdot\alpha(G)\ge\upsilon$。（$\alpha(G)$是$G$的点独立数）

设最大独立集$I$，给最大独立集中的顶点染一种颜色，其余$\upsilon-\alpha(G)$个顶点各染一种颜色；

设$\chi(G)=k$，按色数定义，$V(G)$可划分为$k$个非空独立集，每个独立集至多有$\alpha(G)$个元素。

Theorem 6.2.10 无环边图$G\Longrightarrow \chi(G)\ge w(G)$。（$w(G)$表示$G$的团数）

取最大团，因其每两个顶点都相邻，故都要染不同色。

Theorem 6.2.11 $\forall k\in \mathbb{Z}^+,\exists$不含$K_3$的k色图。

此定理出现之前人们普遍认为：大团$\Longrightarrow$大色数，这个定理了不得。

算法

排课表问题——二部图的边染色算法

思想：给$G$添加必要的顶点使得$|X|=|Y|$，再添加必要的边使得$G$称为$\Delta(G)$正则二部图，反复运用匈牙利算法求此图的完美匹配，共可求得$\Delta(G)$个，每个对应一种颜色。
复杂度：$O(\Delta\cdot\upsilon^3)$

用$\chi'(G)$和$\chi(G)$来对边和点染色都是NPC的；用$\Delta(G)+1$对边染色有P算法；

此问题即要求再尽可能少的时间上完课（同一色为一课时）；

可调整课表使得需要的教室数为$\lceil\frac{\upsilon}{\Delta}\rceil$个。

点染色算法

添边粘合法
- 思想：$\forall u,v\in V(G),uv\notin E(G)$，$\chi(G)$不超过对$u,v$进行添边或粘合操作后所的图的色数，由此可以不断进行添边粘合操作形成一颗二叉树，直至得到完全图。
规范染色法（极大独立集法）（近似算法）
- 思想：先求$G$的极大独立集$V_1$，染上一种颜色，再求$G-V_1$的极大独立集，染上另一种颜色，以此类推，直至染完所有顶点。
- 复杂度：$O(\upsilon^2)$
这是一种贪婪算法；

规范k-染色一般不唯一；

枚举所有规范染色确定$\chi(G)$是不实际的，只适用于阶数小的图。
顺序染色法（近似算法）
- 思想：给顶点排一个顺序，依次给顶点染上$\{c_1,c_2,...\}$中可以染的标号最小的颜色。
- 复杂度：$O(\upsilon^2)$
- 近似比：$\frac{n}{2}$（$n$为所需颜色数）
最大度优先算法（近似算法）
- 思想：将顶点按度降序排列，每使用一种颜色时，尽可能多的给不相邻顶点染色，优先选择度大的顶点。
- 复杂度：$O(\upsilon^2)$
最大度优先算法综合了规范染色发和顺序染色法；

一种修改：在启用每种颜色时，删去已染色的顶点并重新对顶点度降序排列。

练习

$G（X，Y),\delta(G)>0$，证明：$G$有一种$\delta(G)$边染色，使得所有的色都在$G$的每个顶点上出现。

反证，可找到某色不出现，某色出现两次，则有奇圈，矛盾。

证明：简单图$G,\upsilon(G)=2n+1,\epsilon(G)>n\Delta(G)\Longrightarrow \chi'(G)=\Delta(G)+1$。

反证，假设$G$有染色$\{E_1,E_2,...,E_{\Delta(G)}\}$，则由$\epsilon>n\cdot\Delta(G)$，知$\exists E_i:\epsilon(E_i)>n$，故$V(E_i)\ge2n+2$，矛盾。

使用上述结论证明：
1. 若$G$是一个由顶点数为偶数的k-正则简单图（$k>1$）剖分一边后所得之图（剖分一边是指在该边上加入一个新顶点）则$\chi'(G)=\Delta(G)+1$；
2. 若$G$是一个由顶点数为奇数的k-正则图去掉$\frac{k}{2}$条边后得到的图（$k>1$），则$\chi'(G)=\Delta(G)+1)$。

$\upsilon=2n+1,\epsilon=nk+1,\Delta=k$；

$\upsilon=2n+1,\epsilon>nk,\Delta\le k$。

证明：非空正则简单图$G,\upsilon(G)$为奇数，则$\chi'(G)=\Delta(G)+1$。

$\upsilon=2n+1,\epsilon=nk+\frac{k}{2},\Delta=k$。

设$V=(V_1,V_2,...,V_\chi)$是简单图$G$的一个顶点正常$\chi$-染色。
1. 证明：$\forall Vi,\exists v_i\in V_i:v_i$与$V_j$中至少一个顶点相邻；
2. 证明$G$中至少有$\chi$个度$\ge \chi-1$的顶点，由此证明$\chi\le\Delta(G)+1$。

反证；

$\Delta(G)\ge d_G(v_i)\ge\chi-1$。

也可取$G$的临界k色图，利用其性质：临界k色图的$\delta\ge k-1$证得。

设$I$是色临界图$G$的任一个点独立集，证明：$\chi(G-I)=\chi(G)-1$。

由色临界图定义知$\chi(G-I)\le\chi(G)-1$，而$G$一定是$\chi(G-I)+1$色可染的，即$\chi(G)\le\chi(G-I)+1$，得证。

设$\upsilon$阶简单图$G$，证明：$2\sqrt{\upsilon}\le\chi(G)+\chi(\bar{G})\le\upsilon+1;\ \upsilon\le\chi(G)\cdot\chi(\bar{G})\le(\frac{\upsilon+1}{2})^2$。

注意到$w(\bar{G})=\alpha(G)$，
则$\chi(G)\cdot\chi(\bar{G})\ge\chi(G)\cdot w(\bar{G})=\chi(G)\cdot \alpha(G)\ge \upsilon$。

总结

	边色数	点色数
符号	$\chi'(G)$	$\chi(G)$
含义	边集划分，元素为匹配或空集	顶点集划分，元素为点独立集或空集
$<\Delta$	/	$\chi(G)=1\Longleftrightarrow G=\bar{K}_\upsilon,v\ge1$； $\chi(G)=2\Longleftrightarrow G$是非空二部图； $\chi(G)=\upsilon(G)\Longleftrightarrow G\supseteq K_\upsilon$； $\chi(C_{2n+1})=3$； $\chi(G)\ge3\Longleftrightarrow G$含有奇圈。
$\Delta$	（第一类图）路，树，二部图，偶数阶完全图，轮图	...
$\Delta+1$	（第二类图）奇圈，奇数阶完全图...	奇圈/完全图

$\left.\begin{aligned}&\frac{\upsilon^2}{\upsilon^2-2\epsilon}\\ &\frac{\upsilon}{\alpha(G)}\\&w(G) \end{aligned}\right\}\le\chi(G)\le\left\{\begin{aligned}&\Delta(G)+1\\ &1+\max\limits_{i}\min\{d_i,i-1\}\\ &1+\max\limits_{H\subseteq G}\delta(H)\\ &1+l(G)\\ &\upsilon-\alpha(G)+1 \end{aligned}\right.$
证明边/点色数时，想对边集/顶点集的划分。

	边色数	点色数
符号	\(\chi'(G)\)	\(\chi(G)\)
含义	边集划分，元素为匹配或空集	顶点集划分，元素为点独立集或空集
\(<\Delta\)	/	\(\chi(G)=1\Longleftrightarrow G=\bar{K}_\upsilon,v\ge1\)； \(\chi(G)=2\Longleftrightarrow G\)是非空二部图； \(\chi(G)=\upsilon(G)\Longleftrightarrow G\supseteq K_\upsilon\)； \(\chi(C_{2n+1})=3\)； \(\chi(G)\ge3\Longleftrightarrow G\)含有奇圈。
\(\Delta\)	（第一类图）路，树，二部图，偶数阶完全图，轮图	...
\(\Delta+1\)	（第二类图）奇圈，奇数阶完全图...	奇圈/完全图