图着色

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

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

顶点着色

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

色数

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

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

示例

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

区域着色

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

示例

看一下下面的图。区域“aeb”和“befc”是相邻的，因为这两个区域之间存在公共边“be”。

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

示例

K_n的色数是

a) n

b) n–1

c) ⌊ n / 2 ⌋

d) ⌈ n / 2 ⌉

考虑这个 K₄ 的例子。

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

图着色的应用

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

• 聚类
• 数据挖掘
• 图像捕捉
• 图像分割
• 网络
• 资源分配
• 进程调度

Mahesh Parahar

更新于：2019年8月23日

670 次浏览

开启你的职业生涯

通过完成课程获得认证

开始