着色图

图形着色不过是在某些约束下标记图形组件（例如顶点，边线和区域）的一种简单方法。在图形中，没有用最小数量的颜色对两个相邻的顶点，相邻的边或相邻的区域进行着色。此数字称为色数，而该图称为正确着色的图。

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

顶点着色

顶点着色是将颜色分配给图形“ G”的顶点，以使两个相邻的顶点都不具有相同的颜色。简而言之，边的两个顶点都不应具有相同的颜色。

色数

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

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

示例

注-如果顶点着色最多使用n种颜色，即X(G)≤n，则认为图'G'是n可覆盖的。

区域着色

区域着色是将颜色分配给平面图的区域，这样就不会有两个相邻的区域具有相同的颜色。如果两个区域具有相同的边缘，则称它们是相邻的。

示例

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

类似地，其他区域也基于邻接而着色。该图的颜色如下-

示例

K _n的色数为

a）n

b）n–1

c）中⌊ ñ / 2 ⌋   

d）⌈ ñ / 2 ⌉   

考虑带有K _4的示例。

在完整图中，每个顶点都与其余（n – 1）个顶点相邻。因此，每个顶点都需要一种新的颜色。因此，K _n = n的色数。

图形着色的应用

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

• 聚类

• 数据挖掘

• 影像撷取

• 图像分割

• 联网

• 资源分配

• 流程调度