图论 - 着色

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

在进行图着色时，对图设置的约束包括颜色、着色顺序、分配颜色的方式等。着色是为顶点或特定区域提供的。因此，具有相同颜色的顶点或区域形成独立集。

顶点着色

顶点着色是将颜色分配给图"G"的顶点，使得没有两个相邻的顶点具有相同的颜色。简单来说，一条边上的任何两个顶点都不应该具有相同的颜色。

图"G"顶点着色所需的最小颜色数称为 G 的色数，用 X(G) 表示。

当且仅当"G"为零图时，χ(G) = 1。如果"G"不是零图，则 χ(G) ≥ 2。

示例

注意 − 如果顶点着色最多使用 n 种颜色，即 X(G) ≤ n，则图"G"被称为 n 可覆盖。

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

示例

查看下图。区域"aeb"和"befc"相邻，因为这两个区域之间有一条共同的边"be"。

同样，其他区域也根据相邻性着色。此图的着色如下 −

示例

Kn 的色数为

考虑这个 K4 的例子。

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

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