图论 - 着色

图着色不过是一种简单的方法，用于在某些约束条件下标记图的组成部分，例如顶点、边和区域。在一个图中，没有两个相邻的顶点、相邻的边或相邻的区域用最少的颜色着色。这个数字称为色数，该图称为正确着色的图。

在图着色中，对图设置的约束条件包括颜色、着色顺序、着色方式等。颜色赋予顶点或特定区域。因此，具有相同颜色的顶点或区域构成独立集。

顶点着色

顶点着色是将颜色分配给图 'G' 的顶点，使得没有两个相邻的顶点具有相同的颜色。简而言之，一条边的两个顶点不应该具有相同的颜色。

图 'G' 的顶点着色所需的最小颜色数称为 G 的色数，记为 X(G)。

当且仅当 'G' 是一个空图时，χ(G) = 1。如果 'G' 不是空图，则χ(G) ≥ 2。

示例

注意 - 如果存在一个最多使用 n 种颜色的顶点着色，即 X(G) ≤ n，则称图 'G' 是 n 可覆盖的。

区域着色是将颜色分配给平面图的区域，使得没有两个相邻的区域具有相同的颜色。如果两个区域具有公共边，则称它们为相邻的。

示例

看看下面的图。区域 'aeb' 和 'befc' 是相邻的，因为这两个区域之间有一条公共边 'be'。

类似地，其他区域也根据邻接关系着色。该图的着色方式如下：

示例

Kn 的色数是

考虑 K₄ 的这个例子。

在完全图中，每个顶点都与其余 (n – 1) 个顶点相邻。因此，每个顶点都需要一种新的颜色。因此，K_n 的色数 = n。

图着色是图论中最重要概念之一。它被用于计算机科学的许多实时应用中，例如：

打印页面