图论中的色数

在本节中，我们可以学习色数，但为此，我们必须首先了解什么是图着色。只有这样，我们才能轻松理解色数。

图着色

图着色是一种过程，其中需要为图的所有顶点分配某些颜色。颜色的分配方式应确保图中没有两个相邻顶点具有相同的颜色。图着色还有一个名字，即顶点着色。在图着色过程中，图不包含任何一条边，其端点具有相同的颜色。如果我们利用所有这些属性对图进行着色，我们就可以得到一个正确着色的图。如果我们使用至少 3 种颜色为图的所有顶点着色，那么这种图就是正确着色的。有一个例子可以用来理解图着色的概念，如下所述：

在上图中，总共有 5 个顶点，它们使用了 3 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色。因此，我们使用至少 3 种颜色为该图的所有顶点着色。因此，上图是一个正确着色的图。

色数 = 3

色数

可以通过找到正确地给任何图着色所需的最小颜色数量来获得任何图的色数。在分配颜色时，不应将相同的颜色分配给两个相邻的顶点。

色数示例

在色数的情况下，可以有各种各样的例子。以下是一些示例：

示例 1

这个例子包含一个图，我们需要找到它的色数。

解答：正如我们所知，如果颜色的分配方式使得两个相邻顶点不具有相同的颜色，则图具有色数。在上图中，总共有 5 个顶点，它们使用了 4 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色。因此，在该图中，满足色数的所有属性。因此，

色数 = 4

示例 2

这个例子包含一个图，我们需要找到它的色数。

解答：正如我们所知，如果颜色的分配方式使得两个相邻顶点不具有相同的颜色，则图具有色数。在上图中，总共有 4 个顶点，它们使用了 2 种颜色进行着色，但两个相邻顶点具有相同的颜色。因此，在该图中，不满足色数的所有属性。

示例 3

这个例子包含一个图，我们需要找到它的色数。

解答：正如我们所知，如果颜色的分配方式使得两个相邻顶点不具有相同的颜色，则图具有色数。在上图中，总共有 6 个顶点，它们使用了 2 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色。因此，在该图中，满足色数的所有属性。因此，

色数 = 2

各种图的色数

在图论领域，我们有各种各样的图，它们都有一些色数。在这里，我们将讨论其中的一些，例如：

环图

如果图具有相同的起始和最后一个顶点，但没有重复的边，则可以称该图为环图。正如我们所知，在环图中，每个顶点有两条入射边，因此每个顶点的度都是 2。在一个图中，需要至少 3 长度的图来创建一个环。因此，如果是一个环图，那么它们的长度应大于 2。

环图的色数

• 如果我们有一个包含偶数个顶点的环图，那么在这种类型的图中，其色数为 2。
• 如果我们有一个包含奇数个顶点的环图，那么在这种类型的图中，其色数为 3。

环图色数示例

在环图的色数的情况下，可以有各种各样的例子。以下是一些示例：

示例 1

这个例子包含一个环图，我们需要找到它的色数。

解答：正如我们所知，如果一个图具有相同的起始和最后一个顶点，但没有重复的边，则它是一个环。在上图中，总共有 5 个顶点，它们使用了 3 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色。在环图的情况下，如果顶点数为奇数，则色数应为 3，该图也包含 3 作为色数，并且顶点数为奇数。因此，在该图中，满足环的色数的所有属性。因此，

色数 = 3

示例 2

这个例子包含一个环图，我们需要找到它的色数。

解答：正如我们所知，如果一个图具有相同的起始和最后一个顶点，但没有重复的边，则它是一个环。在上图中，总共有 6 个顶点，它们使用了 2 种颜色进行着色，但两个相邻顶点具有相同的颜色。因此，在该图中，不满足环的色数的所有属性。

示例 3

这个例子包含一个环图，我们需要找到它的色数。

解答：正如我们所知，如果一个图具有相同的起始和最后一个顶点，但没有重复的边，则它是一个环。在上图中，总共有 4 个顶点，它们使用了 2 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色。在环图的情况下，如果顶点数为偶数，则色数应为 2，该图也包含 2 作为色数，并且顶点数为偶数。因此，在该图中，满足环的色数的所有属性。因此，

色数 = 2

平面图

平面图可以描述为一个可以在平面上绘制的图，在绘制时，边不应相互交叉。

平面图的色数

如果我们有一个平面图，那么其色数的计算结果总是小于或等于 4。

平面图色数示例

在平面图的色数的情况下，可以有各种各样的例子。以下是一些示例：

示例 1

这个例子包含一个平面图，我们需要找到它的色数。

解答：正如我们所知，如果一个图可以在平面上绘制，并且在绘制时边不相互交叉，那么它就是一个平面图。在上图中，总共有 4 个顶点，它们使用了 2 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色，并且边不相互交叉。在平面图的情况下，色数应小于或等于 4，该图的色数为 2。因此，在该图中，满足平面图色数的所有属性。因此，

色数 = 2

示例 2

这个例子包含一个平面图，我们需要找到它的色数。

解答：正如我们所知，如果一个图可以在平面上绘制，并且在绘制时边不相互交叉，那么它就是一个平面图。在上图中，总共有 6 个顶点，它们使用了 6 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色，并且边不相互交叉。但是在平面图的情况下，色数应小于或等于 4，该图的色数为 6。因此，在该图中，不满足平面图色数的所有属性。

完全图

完全图可以描述为一个图，其中使用唯一的边来连接两个不同的顶点。如果是一个完全图，那么每个顶点都必须连接到其他顶点。顶点必须分配不同的颜色。也就是说，如果一个完全图中有 4 个顶点，那么就需要 4 种颜色来为该图的所有顶点着色。我们不能使用相同的颜色来为完全图中的任何两个顶点着色。

完全图的色数

如果我们有一个完全图，那么我们可以通过获取顶点的总数来获得其色数。换句话说，完全图的色数和顶点的数量是相同的。

完全图色数示例

在完全图的色数的情况下，可以有各种各样的例子。以下是一些示例：

示例 1

这个例子包含一个二分图，我们需要找到它的色数。

解答：正如我们所知，如果一个图通过唯一的边连接两个不同的顶点，则该图是完全图。在上图中，总共有 4 个顶点，它们使用了 4 种颜色进行着色。在完全图的情况下，色数应等于顶点数，该图包含 4 个顶点。因此，在该图中，满足完全图色数的所有属性。因此，

色数 = 4

示例 2

这个例子包含一个完全图，我们需要计算这个图的色数。

解答：正如我们所知，如果一个图通过唯一的边连接两个不同的顶点，则该图是完全图。在上图中，总共有 6 个顶点，它们使用了 4 种颜色进行着色。在完全图的情况下，色数应等于顶点数，但该图包含 6 个顶点和 4 种颜色。因此，在该图中，不满足完全图色数的所有属性。

示例 3

这个例子包含一个二分图，我们需要找到它的色数。

解答：正如我们所知，如果一个图通过唯一的边连接两个不同的顶点，则该图是完全图。在上图中，总共有 4 个顶点，它们使用了 3 种颜色进行着色。在完全图的情况下，色数应等于顶点数，但该图包含 4 个顶点和 3 种颜色。因此，在该图中，不满足完全图色数的所有属性。

二分图

如果图中存在两个顶集，则该类型的图称为二分图。如果我们想在顶点之间建立连接，那么它只能在两个不同的顶点集之间建立。换句话说，我们可以说 X 集中的顶点不能连接到同一组顶点。它只能连接到 Y 集中的顶点。

二分图的色数

如果我们有一个二分图，那么其色数的计算结果总是 2。

二分图色数示例

在二分图的色数的情况下，可以有各种各样的例子。以下是一些示例：

示例 1

这个例子包含一个二分图，我们需要找到它的色数。

解答：正如我们所知，如果一个图有两个顶点集相互连接，那么它就是一个二分图。这里，我们有两个不同的顶点集，同一集中的顶点不相互连接。它们连接到不同的顶点集。两个集合都使用了 2 种颜色进行着色。第一个集合的所有顶点都用绿色着色，第二个集合的所有顶点都用红色着色。在二分图的情况下，色数应为 2，该图的色数也为 2。因此，在该图中，满足二分图色数的所有属性。因此，

色数 = 2

示例 2

这个例子包含一个二分图，我们需要找到它的色数。

解答：正如我们所知，如果一个图有两个顶点集相互连接，那么它就是一个二分图。这里，我们有两个不同的顶点集，同一集中的顶点不相互连接。它们连接到不同的顶点集。第一个集合的所有顶点都用蓝色着色，第二个集合的所有顶点都用橙色着色。因此，两个集合都使用了 2 种颜色进行着色。在二分图的情况下，色数应为 2，该图的色数也为 2。因此，在该图中，二分图色数的所有属性都得到满足。因此，

色数 = 2

示例 3

这个例子包含一个二分图，我们需要找到它的色数。

解答：正如我们所知，如果一个图有两个顶点集相互连接，那么它就是一个二分图。这里，我们有两个不同的顶点集，同一集中的顶点不相互连接。它们连接到不同的顶点集。第一个集合和第二个集合的所有顶点都用红色着色。因此，两个集合都使用相同的颜色进行着色。在二分图的情况下，色数应为 2，但该图的色数为 1。因此，在该图中，二分图色数的所有属性都不满足。

Tree

如果一个图是连通的并且不包含任何回路，则该图称为树。如果我们有一棵树，那么它也一定是一个二分图。正如我们在二分图中学习到的色数是 2，因此，树的色数也将是 2。树可以包含任意数量的顶点，这些数量对其色数没有影响。

树的色数

如果我们有一棵树，那么其色数的计算结果总是 2。

树色数示例

在树的色数的情况下，可以有各种各样的例子。以下是一些示例：

示例 1

这个例子包含一棵树，我们需要找到它的色数。

解答：正如我们所知，如果一个图是连通的并且不包含任何回路，则该图是一棵树。在上图中，总共有 4 个顶点，它们使用了 2 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色。在树的情况下，色数应为 2，该图的色数也为 2。因此，在该图中，树的色数的所有属性都得到满足。因此，

色数 = 2

示例 2

这个例子包含一棵树，我们需要找到它的色数。

解答：正如我们所知，如果一个图是连通的并且不包含任何回路，则该图是一棵树。在上图中，总共有 7 个顶点，它们使用了 2 种颜色进行着色，但两个相邻顶点具有相同的颜色。在树的第二层和第三层，有相同的颜色，即红色。因此，在该图中，树的色数的所有属性都不满足。因此，该树没有色数。

示例 3

这个例子包含一棵树，我们需要找到它的色数。

解答：正如我们所知，如果一个图是连通的并且不包含任何回路，则该图是一棵树。在上图中，总共有 15 个顶点，它们使用了 2 种颜色进行着色，并且颜色的分配方式是使两个相邻顶点不具有相同的颜色。在树的情况下，色数应为 2，该图的色数也为 2。因此，在该图中，树的色数的所有属性都得到满足。因此，

色数 = 2