图的色数 | 图论中的图着色

图着色

图着色可以描述为一种为图的顶点分配颜色的过程。在此过程中，不应使用相同的颜色来填充两个相邻的顶点。我们也可以称图着色为顶点着色。在图着色中，我们必须注意，图不得包含任何一条边，其端点被着以相同的颜色。这种类型的图称为正确着色的图。

图着色示例

在此图中，我们展示了正确着色的图，其描述如下

上述图包含一些点，其描述如下

• 不能使用相同的颜色为两个相邻的顶点着色。
• 因此，我们可以称之为正确着色的图。

图着色的应用

图着色有各种应用。其中一些重要应用描述如下

• 赋值
• 地图着色
• 任务调度
• 数独
• 准备时间表
• 冲突解决

色数

色数可以描述为正确着色任何图所需的最小颜色数。换句话说，色数可以描述为给任何图着色所需的最小颜色数，使得图的任意两个相邻顶点都不会被分配相同的颜色。

色数示例

为了理解色数，我们将考虑一个图，其描述如下

上述图包含一些点，其描述如下

• 不能使用相同的颜色为两个相邻的顶点着色。
• 此图所需的最小颜色数为 3，用于正确地为顶点着色。
• 因此，在此图中，色数 = 3
• 如果我们想正确地给这个图着色，在这种情况下，我们至少需要 3 种颜色。

图色数类型

图的色数有各种类型，描述如下

圈图

当一个图包含 'n' 条边和 'n' 个顶点（n ≥ 3），它们形成一个长度为 'n' 的环时，该图被称为环图。环图中所有顶点的度数只能是 2 或 3。

色数

1. 如果环图中的顶点数为偶数，则该环图的色数为 2。
2. 如果环图中的顶点数为奇数，则该环图的色数为 3。

环图示例

有各种环图的例子。其中一些描述如下

示例 1：在下图，我们需要确定色数。

解决方案：在上述环图中，三个顶点有三种不同的颜色，并且没有相邻的顶点用相同的颜色着色。在此图中，顶点数为奇数。所以

色数 = 3

示例 2：在下图，我们需要确定色数。

解决方案：在上述环图中，四个顶点有两种颜色，并且没有相邻的顶点用相同的颜色着色。在此图中，顶点数为偶数。所以

色数 = 2

示例 3：在下图，我们需要确定色数。

解决方案：在上述图中，五个顶点有四种不同的颜色，并且两个相邻的顶点被着以相同的颜色（蓝色）。所以这个图不是环图，也没有色数。

示例 4：在下图，我们需要确定色数。

解决方案：在上述图中，六个顶点有两种不同的颜色，并且没有相邻的顶点用相同的颜色着色。在此图中，顶点数为偶数。所以

色数 = 2

平面图

当一个图在平面上绘制时，它被称为平面图。平面图的边不得相互交叉。

色数

1. 在平面图中，色数必须小于或等于 4。
2. 除了示例 3，上面所有的环图也可以表示平面图。

平面图示例

有各种平面图的例子。其中一些描述如下

示例 1：在下图，我们需要确定色数。

解决方案：在上述图中，三个顶点有三种不同的颜色，并且该图的边不相互交叉。所以

色数 = 3

这里，色数小于 4，所以这个图是平面图。

示例 2：在下图，我们需要确定色数。

解决方案：在上述图中，四个顶点有两种不同的颜色，并且该图的边不相互交叉。所以

色数 = 2

这里，色数小于 4，所以这个图是平面图。

示例 3：在下图，我们需要确定色数。

解决方案：在上述图中，五个顶点有五种不同的颜色，并且该图的边不相互交叉。所以

色数 = 5

这里，色数大于 4，所以这个图不是平面图。

示例 4：在下图，我们需要确定色数。

解决方案：在上述图中，六个顶点有两种不同的颜色，并且该图的边不相互交叉。所以

色数 = 2

这里，色数小于 4，所以这个图是平面图。

完全图

当且仅当用一条边连接每两个不同的顶点时，一个图被称为完全图。在完全图中，每个顶点都与所有其他顶点相连。在此图中，每个顶点都将用不同的颜色着色。这意味着在完全图中，两个顶点不包含相同的颜色。

色数

在完全图中，色数将等于该图中的顶点数。

完全图示例

有各种完全图的例子。其中一些描述如下

示例 1：在下图，我们需要确定色数。

解决方案：在上述图中，有 4 个不同的顶点，用了 4 种不同的颜色，并且没有任何颜色相同。根据定义，色数是顶点数。所以，

色数 = 4

示例 2：在下图，我们需要确定色数。

解决方案：在上述图中，有 5 个不同的顶点，用了 5 种不同的颜色，并且没有任何颜色相同。根据定义，色数是顶点数。所以，

色数 = 5

示例 3：在下图，我们需要确定色数。

解决方案：在上述图中，有 4 个不同的顶点，用了 3 种不同的颜色，并且一种颜色在两个顶点上重复。所以这个图不是完全图，也没有色数。

二分图

当一个图包含两个顶点集 A 和 B 时，该图被称为二分图。A 的顶点只能连接到 B 的顶点。这意味着边不能连接同一集内的顶点。

色数

在任何二分图中，色数始终等于 2。

二分图示例

有各种二分图的例子。其中一些描述如下

示例 1：在下图，我们需要确定色数。

解决方案：在上述图中，有 2 个不同的顶点集。所以所有二分图的色数始终为 2。所以

色数 = 2

Tree

当一个连通图没有回路时，它被称为树。在一棵树中，色数将等于 2，无论树中有多少顶点。每个二分图也是一棵树。

色数

在任何树中，色数等于 2。

树示例

有各种树的例子。其中一些描述如下

示例 1：在下图中，我们需要确定色数。

解决方案：有四个顶点用了两种不同的颜色。任何棵具有任意数量顶点的树的色数都必须是 2。所以，

色数 = 2

示例 2：在下图中，我们需要确定色数。

解决方案：有五个顶点用了两种不同的颜色。任何棵具有任意数量顶点的树的色数都必须是 2。所以，

色数 = 2

色数的实际应用

假设 Marry 是 Xyz 公司的一名经理。公司招聘了一些新员工，她需要为这些新员工制定培训计划。她需要安排三次会议，并且她正试图尽可能少地使用时间段来进行会议。如果某个员工必须参加两次不同的会议，那么经理就需要为这些会议使用不同的时间表。假设我们想获得这个会议的可视化表示。

为了进行可视化表示，Marry 使用点来表示会议。如果某个员工需要参加两次会议，那么这两个会议将通过一条边连接。不同的时间段用颜色来表示。所以经理用这些颜色填充点，这样两个共享边的点就不会用相同的颜色表示。（这意味着需要参加两次会议的员工不能有相同的时间表）。这的可视化表示描述如下