图论中的顶点着色

2025年7月12日 | 阅读 10 分钟

顶点着色是一种过程，我们需要为 G 的每个顶点分配颜色。我们应该为顶点分配颜色，而不使用相同的颜色给图的两个相邻顶点。正式地，顶点着色也可以被描述为一种赋值颜色过程。我们通常使用数字来表示图的颜色。此外，在进行顶点着色时，我们应该注意图的两个相邻顶点必须使用不同的颜色着色。简单来说，图中通过边连接的两个顶点不得具有相同的颜色。

图中两个顶点称为相邻，如果它们通过公共边连接。

现在我们展示一个例子，帮助我们理解两个顶点之间的邻接关系，如下所示

在这个图中，我们总共有 4 个顶点，c1、c2、c3 和 c4。这里，我们有三对相邻顶点。顶点 c1 和 c3 称为第一对相邻顶点。它们是相邻的，因为顶点 c1 和 c3 都包含一条公共边。同样，其他相邻顶点对是 (c1, c4) 和 (c2, c3)。在这个图中，没有两个相邻顶点使用相同的颜色填充，这满足了顶点着色的属性。

顶点着色可以在各种领域中使用，例如数学和计算机科学。此外，有可能使用顶点着色问题来模拟复杂的现实生活问题。确定图的色数是一项困难的任务，它也属于 NP 完全类。在图论领域，我们有一个有效的算法，可以用于解决所有图的这个问题。

色数

通过计算为图的所有顶点着色所需的最小颜色数，我们可以得到图的色数。当我们计算任何图的色数时，我们应该总是得到大于 1 的色数。只有一种情况，当我们得到的色数为 1，即图只包含 1 个顶点。

我们可以通过一个例子来理解色数，如下所示

在这个图中，我们需要 2 种颜色来为所有顶点着色，这样两个相邻顶点就不会有相同的颜色。因此，色数为 2。

顶点着色问题的几种方法

有几种方法可以用来解决顶点着色问题。

这些方法描述如下

蛮力搜索：第一种也是最基本的方法是蛮力搜索，但这种算法效率不高。在此算法中，我们将尝试所有可能的着色方式，然后选择颜色数最少的图。使用此算法后，我们总是会得到最优解，但此算法在计算上很昂贵。如果我们有小型图，我们应该使用此算法。对于大型图，此方法效率不高。

局部搜索：解决顶点着色问题的第二种方法是局部搜索。在此算法中，我们进行一些小的局部更改，并通过此过程迭代地改进现有解决方案。在此方法中，算法交换两个相邻顶点的颜色。此外，该算法还尝试另一种方法，即尝试重新着色单个顶点。如果我们结合局部搜索算法和其他一些技术，只有这样，该算法才能变得有效和高效。

整数线性规划：存在一个整数线性规划，可以通过它来构建顶点着色问题。使用此方法，可以获得顶点着色问题的精确解。但是，我们应该对小型图使用此方法，因为它对于大型图来说成本很高。

贪心法：我们可以解决顶点着色问题的最后一种方法是贪心法。对于这个问题，贪心法简单高效。但是，使用此算法后，我们不一定总是能得到最优解。

如何为顶点着色

为此，我们举一个例子，并尝试理解如何为图的所有顶点着色，而不使用相同的颜色给两个相邻顶点。图如下所示

开始时，以上图的所有顶点都是白色的 (color[v] = -1)。图中总共有 7 个顶点。现在，我们在主循环中开始使用 7 种可用颜色为每个顶点着色。假设所有颜色的代码为 {蓝色 = 1, 绿色 = 2, 黄色 = 3, 橙色 = 4, 粉色 = 5, 紫色 = 6, 灰色 = 7}

在所有顶点中，顶点 e 的度最高，即 3。所以，我们从顶点 e 开始。顶点 e 的所有邻居顶点是 {a, b, t}。所有顶点都是白色的，所以我们可以从 7 种颜色中选择一种来为顶点 e 着色。假设我们选择了蓝色，因为它在所有代码中是最小的，并像这样填充在顶点 e 中

之后，我们选择顶点 a。顶点 'a' 的所有邻居顶点是 {s, e, c}。由于我们已经使用了蓝色，所以我们总共有 6 种剩余颜色可以用来为顶点 a 着色。假设我们选择绿色 (代码 2)，因为它在剩余代码中是最小的。

现在，我们选择顶点 b。顶点 'b' 的所有邻居顶点是 {e, d, s}。由于我们已经用蓝色填充了顶点 e，并且顶点 e 与顶点 b 相邻。所以，我们不能选择蓝色来为这个顶点着色。顶点 a 与顶点 b 不相邻，因此我们可以使用顶点 a 的颜色（绿色）为顶点 b 着色。

为顶点 b 分配颜色后的图如下

现在，我们选择顶点 s。顶点 's' 的所有邻居顶点是 {a, b}。由于我们已经用绿色填充了顶点 a 和 b，并且它与顶点 s 相邻，所以我们不能选择绿色来为这个顶点着色。顶点 e 与顶点 b 不相邻，因此我们可以选择顶点 e 的颜色（蓝色）来为顶点 s 着色。

为顶点 s 分配颜色后的图如下

现在，我们选择顶点 c。顶点 'c' 的所有邻居顶点是 {a, t}。由于我们已经用绿色填充了顶点 'a'，并且它与顶点 c 相邻，所以我们不能选择绿色来为这个顶点着色。顶点 'e' 与顶点 'c' 不相邻，因此我们可以选择顶点 e 的颜色（蓝色）来为顶点 'c' 着色。为顶点 c 分配颜色后的图如下

现在，我们选择顶点 d。顶点 'd' 的所有邻居顶点是 {b, t}。由于我们已经用绿色填充了顶点 b，并且它与顶点 d 相邻，所以我们不能选择绿色来为这个顶点着色。顶点 'd' 与顶点 'e' 不相邻，因此我们可以选择顶点 e 的颜色（蓝色）来为顶点 'd' 着色。为顶点 d 分配颜色后的图如下

现在，我们选择顶点 t。顶点 't' 的所有邻居顶点是 {c, d, e}。由于我们已经用蓝色填充了顶点 c、d 和 e，并且它们与顶点 t 相邻，所以我们不能选择蓝色来为这个顶点着色。顶点 't' 与顶点 a 不相邻，因此我们可以选择顶点 a 的颜色（绿色）来为顶点 't' 着色。

为顶点 't' 分配颜色后的图如下

最后，图的所有顶点都分配了 2 种颜色，使得两个相邻顶点不具有相同的颜色。因此，在这个图中，色数为 2。

顶点着色的应用

在图论领域，顶点着色是一个重要的问题。在许多领域，顶点着色有许多应用，例如运筹学、计算机科学以及更多领域。在顶点着色的情况下，无线频率分配、路由、调度和寄存器分配是最常见的应用。

调度问题：可以使用顶点着色问题来解决此问题。在此问题中，我们需要为可用的任务分配所有资源，并且在进行此操作时不得发生任何冲突。要解决此问题，我们需要将每个任务表示为图的顶点，并将每个资源表示为图的颜色。此外，我们使用图并找到其色数。因此，通过色数，我们可以轻松完成所有任务，因为我们得到了完成任务所需的最小资源数。

编译器：我们可以在编译器中使用顶点着色问题。在这里，在计算机的处理过程中，变量被分配到寄存器。

网络路由问题：我们可以借助顶点着色问题来解决网络路由问题。在网络路由的情况下，数据包应该通过节点网络进行路由，但在进行此操作时不得发生任何冲突。要解决此问题，我们需要将每个节点表示为顶点，并将每条路径表示为颜色。

因此，通过色数，我们可以轻松路由所有数据包，因为我们得到了完成路由所需的最小可能路径数。

有一个例子可以用来轻松理解顶点着色的概念。在这个例子中，我们需要为手机网络提供频率。广播范围内有许多信号，它们都具有不同的频率。通过使用不同的频率，手机网络的信号不得相互干扰。因此，分配频率是一项艰巨的任务，我们可以通过构建连接网络模型来解决这项任务。在此模型中，顶点用于表示站点，边用于表示顶点之间的冲突。（在我们的例子中，冲突用于表示向网络提供不同频率的站点对）。我们通过站点和冲突构建的模型或图就是具有顶点着色的图。