最小化颜色以绘制图，使得没有路径具有相同的颜色

---

图着色是图论中图标记的一个子集。颜色的使用源于地图上国家的着色，其中每个区域都着色。图着色有几个现实世界的应用，以及理论问题。除了传统形式的问题外，还可以对图、着色方式甚至颜色本身施加其他约束。它甚至以著名的数字谜题数独的形式获得了广泛的关注。图着色仍然是一个活跃的研究领域。

什么是顶点着色？

顶点着色是指为任何图的每个顶点或节点分配颜色或标签，使得没有两个颜色相同的节点通过边连接。最流行的顶点着色方法试图减少单个图中使用的颜色数量。这种类型的着色称为最小顶点着色。

k-着色是指使用k种或更少颜色对图进行顶点着色。k-可着色图采用色数k，色数为k的图称为“k-色图”。唯一一种单色可着色（因此是单色）的图是空图，而双色可着色图包括二分图。四色定理指出所有平面图都是4-可着色的。

边着色

当为图的边分配不同的颜色时，确保没有节点旁边有两个以上相同颜色的边，则称为边适当着色。图的色指数或边色数是指用于边着色的最小颜色数量。

色数

色数定义为用于对任何图的顶点或节点进行着色的最小颜色数。此数字的值通常大于一。另一方面，当图只有一个顶点时，色数为一。

如何最小化颜色以着色图，其中没有路径具有相同的颜色？

以下是一个基于拓扑排序理论的解决方案：

在“有向无环图 (DAG)”中，拓扑排序定义为节点的“线性排序”，这样对于任何有向边（例如，p，q），p顶点在排列中出现在q之前。

如果图不是DAG，则拓扑排序不可行

在拓扑排序中，

• “使用一个临时堆栈”。

• “不要立即显示顶点；而是先在其每个相邻顶点上递归运行拓扑排序，然后再将其压入堆栈”。

• “最后，打印堆栈的内容”。

我们可以看到，所需的最小颜色数等于图的最长路径的长度。

所有入度等于零的节点都可以具有相同的颜色。从它们的邻居中消除一个入度，并循环遍历所有入度 = 0 的节点。

“如果遵循此规则，则只有在所有路径中位于其上方的每个节点都被分配了颜色之后，才会为特定节点分配颜色。因此，这将提供路径的最长可能长度”。

要将这个想法付诸实践，请遵循以下步骤：

• 根据提供的边，构建有向图的邻接表。

• 保留一个入度向量，其中包含每个节点的入度。

• 声明一个变量（例如，depth）来保存节点的深度。

• “在拓扑排序的每次迭代期间，选择一种新颜色并将其分配给入度为 0 的节点，并且当添加新颜色时，深度增加一”。

• 作为必要的答案，返回深度的最终值。

示例

#include <bits/stdc++.h>
using namespace std;
  
// Function to find minimum number of colours required
int min_colour(int N, int M, vector<int> mat[]){

   // Create an adjacency list
   vector<vector<int> > adj(N + 1);
  
   // Create indeg to store indegree of every minion
   vector<int> indeg(N + 1);
  
   for (int i = 0; i < M; i++) {
  
      // Store mat[i][1] in adj[(mat[i][0])] as mat[i][1] directs to mat[1][0]
      adj[(mat[i][0])].push_back(mat[i][1]);
      indeg[(mat[i][1])]++;
   }

   // Initialize a variable depth to store min different colors required
   int depth = 0;
   queue<int> q;
  
   for (int i = 1; i <= N; i++) {
      if (indeg[i] == 0) {
         q.push(i);
      }
   }
  
   if (q.empty())
      return 0;

   // Loop to use Topological sorting
   while (!q.empty()) {
      int size = q.size();
      for (int k = 0; k < size; k++) {
         int e = q.front();
         q.pop();
  
         for (auto it : adj[e]) {
            indeg[it]--;
            if (indeg[it] == 0) {
               q.push(it);
            }
         }
      }
      depth++;
   }
  
   // Return the minimum number of colours
   return depth;
}

// Driver code
int main(){
   int N = 5, M = 6;
   vector<int> mat[] = { { 1, 3 }, { 2, 3 }, { 3, 4 }, { 1, 4 }, { 2, 5 }, { 3, 5 } };

   // Function Call
   cout << min_colour(N, M, mat);
   return 0;
}

输出

根据上述代码，输出为：

3

辅助空间和时间复杂度均为：O(N + M)

图着色的替代技术

让我们看看一些解决顶点着色问题的方案。

• 最简单但效率最低的方法是蛮力搜索。蛮力搜索算法包括尝试所有可能的图着色，并选择颜色最少的那个。虽然这种方法保证找到最佳解决方案，但它的计算成本很高。此外，此方法仅适用于小型图。

• 第二种策略是局部搜索。局部搜索方法通过小的局部调整迭代地改进现有答案。在顶点着色问题的情况下，局部搜索方法可以交换两个相邻顶点的颜色。它还可以尝试只重新着色一个顶点。

• 贪婪方法可用于解决顶点着色问题。这些算法简单有效。但是，它们并不总是产生最佳选择。

• 顶点着色问题也可以表示为整数线性规划。这种方法可以找到问题的精确解。但是，对于大型图，它可能会变得非常昂贵。

顶点着色的应用

• 它在运筹学和计算机科学等各个领域都有多种用途。调度、路由、寄存器分配和无线频率分配是一些最流行的顶点着色问题的应用。

• 在调度问题中，我们必须将资源分配给可用的任务，同时避免冲突。为了解决这个问题，我们可以将每个任务表示为图中的一个顶点，并将每个资源表示为一种颜色。此图还允许我们计算色数。因此，色数表示执行所有任务而不发生冲突所需的最低资源数量。

• 网络路由问题。数据包必须通过节点网络进行路由，而不会发生冲突。此外，我们可以使用顶点着色来描述这个问题，其中每个节点表示一个顶点，每条路径表示图中的颜色。

• 编译器必须使用计算机处理器中的寄存器为程序中的变量分配寄存器。我们可以使用顶点着色和色数原理来分配最少的寄存器来运行程序。

• 在无线网络通信中，顶点着色问题可用于将无线信道分配给设备以减少干扰。

结论

在图论中，顶点着色是图标记的一个子集，它涉及将标签传递给顶点或节点标签以减少单个图中使用的颜色数量。调度、路由、寄存器分配和无线频率分配都是运筹学和计算机科学中顶点着色的应用。