Question

Coloring

替一张图的各个元件都涂上颜色，并规定相邻元件不可同色。一张图的上色情形，称作一种“著色”。

根据元件的不同，著色可分为许多种类型，例如点著色（vertex coloring）、边著色（edge coloring）、面著色（face coloring）。

【注：英文“Coloring”为名词，中文“著色”为动词，英翻中致使文法不通，请多见谅。】

Vertex Coloring

Vertex Coloring

“点著色”。替一张图上的每个点涂上颜色，并且规定以边相连的相邻两点不可同色。

Minimum Vertex Coloring 与 Chromatic Number

一张图的“最小点著色”是颜色最少的点著色方式，可能有许多种；一张图的“著色数”是最小点著色的颜色数目。

求最小点著色是 NP-complete 问题。有一些特殊的图，可以推理得到著色数的上限：

G 没有点和边：χ(G) = 0
G 没有边：χ(G) ≤ 1
G 为二分图（Bipartite Graph）：χ(G) ≤ 2
G 为平面图（Planar Graph）：χ(G) ≤ 4（四色定理）
G 为完全图（Complete Graph）：χ(G) = V
G 的每个点的连接边数相同（k-regular）：χ(G) ≤ k + 1
G 的每个点的连接边数不同（non-regular），也就是一般的图：χ(G) ≤ Δ(G)

χ(G)：一张图 G 的著色数。
Δ(G)：一张图 G 的最大 degree。

原图的 Minimum Vertex Coloring，等于补图的 Minimum Clique Cover。

UVa 10661 10004 10052

Greedy Vertex Coloring 与 Grundy Number

https://en.wikipedia.org/wiki/Grundy_number

因为最小点著色是 NP-complete 问题，于是有人转为讨论用贪心法进行点著色。当然啦，不保证著色数最小。

演算法：无向图点著色（Welsh-Powell Algorithm）

一个简单的 Greedy 演算法，找出其中一种点著色，但是不保证著色数最小。

首先把图上每个点，依照 degree 由大到小排序，然后一一涂色。每一个点都先尝试涂第一种颜色，若牴触了已涂色的点，就换下一种颜色，直到颜色不牴触为止。

每个点的度数范围都只有 0 到 V-1（不考虑多重的边、不考虑自己连向自己的边），故排序时可以採用 Counting Sort，时间複杂度是 O(V)。

每个点都著色的时间複杂度等同一次 Graph Traversal 的时间，如果图的资料结构为 adjacency matrix 就是 O(V^2)，如果图的资料结构为 adjacency lists 就是 O(V+E)。

Edge Coloring

Edge Coloring

“边著色”。替一张图上的每条边涂上颜色，并且规定共用端点的边不可同色。

Minimum Edge Coloring 与 Edge Chromatic Number

概念与 Vertex Coloring 相仿。

G 为任意图：χ'(G) ≥ Δ(G)
G 的每个点的连接边数相同（k-regular）：χ'(G) = k or k + 1

χ'(G)：边著色数
Δ(G)：一张图 G 的最大 degree。

UVa 10615

Total Coloring

点边都著色。

http://en.wikipedia.org/wiki/Total_coloring

Synchronizing Coloring

http://en.wikipedia.org/wiki/Road_coloring_theorem

Weighted Coloring

http://www-sop.inria.fr/members/Nicolas.Nisse/slides/weightedTrees.pdf

ICPC 7465