最小化颜色以绘制图形，使任何路径都具有相同的颜色
图着色是图论中图标记的一个子集。颜色的使用源于为地图上的国家着色，其中每个面都被着色。图着色在现实世界中有许多应用，也涉及理论问题。除了传统的问题形式外，还可以对图形、赋予颜色的方式，甚至颜色本身施加其他约束。它甚至以著名的数字谜题数独的形式获得了广泛的关注。图着色仍然是一个活跃的研究领域。
什么是顶点着色?
为任何图的每个顶点或节点分配颜色或标签，使得没有两个相同颜色的节点通过边连接，这称为顶点着色。最流行的顶点着色方法是尝试减少单个图中使用的颜色数量。这种类型的着色称为最小顶点着色。
k-着色是使用 k 种或更少种颜色对图进行顶点着色。k-可着色图的色数为 k，色数为 k 的图称为"k-色图"。唯一可单色(因此也是单色)的图是空图，而双色图包括二分图。根据四色定理，所有平面图都是四色可着色的。
边着色
当为图的边分配不同的颜色时，会对其进行适当的着色，以确保没有节点相邻的边颜色超过一对。图的色度指数，或称边色数，是指用于边着色的最小颜色数。
色数
色数定义为用于对任何图的顶点或节点进行着色的最小颜色数。该数字通常大于 1。另一方面，当图只有一个顶点时，色数为 1。
如何最小化颜色来为没有相同颜色路径的图着色?
以下是基于拓扑排序理论的解决方案 -
在"有向无环图 (DAG)"中，拓扑排序被定义为节点的"线性排序"，因此，对于任何有向边(例如 p、q)，p 顶点在排列中都先于 q 顶点出现。
如果不是 DAG，则无法进行拓扑排序
说到拓扑排序，
"使用临时堆栈。"
"不要立即显示顶点;而是在将其推送到堆栈之前，对其附近的每个顶点进行递归拓扑排序。"
"最后，打印堆栈的内容。"
我们可以看到，所需的最低颜色数量等于图的最长路径的长度。
所有入度等于零的节点都可以具有相同的颜色。从其邻居中消除一个入度，并循环遍历所有入度 = 0 的节点。
"如果遵循此规则，则只有在所有路由中位于该节点上方的每个节点都分配了颜色后，才会为特定节点分配颜色。因此，这将提供最长的路径长度。"
要将想法付诸实践，请按照以下步骤操作 -
根据提供的边，构建有向图的邻接表。
保存一个入度向量，用于保存每个节点的入度。
声明一个变量(例如，深度)来保存节点的深度。
"在拓扑排序的每次迭代中，都会选择一种新颜色并将其分配给入度为 0 的 Minion，并且当新颜色被添加时，深度会增加一已添加。
作为必要答案，返回深度的最终值。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数用于查找所需最少颜色数量
int min_colour(int N, int M,vector<int> mat[]){
// 创建邻接表
vector<vector<int> > adj(N + 1);
// 创建 indeg 来存储每个 minion 的入度
vector<int> indeg(N + 1);
for (int i = 0; i < M; i++) {
// 将 mat[i][1] 存储在 adj[(mat[i][0])] 中，因为 mat[i][1] 指向 mat[1][0]
adj[(mat[i][0])].push_back(mat[i][1]);
indeg[(mat[i][1])]++;
}
// 初始化一个变量深度来存储所需的最少不同颜色
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;
//循环使用拓扑排序
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 depth;
}
// 驱动代码
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)
图着色的替代技术
让我们来看看顶点着色问题的一些解决方案。
最简单但效率最低的方法是暴力搜索。暴力搜索算法包括尝试所有可能的图着色，并选择颜色最少的着色。虽然这种方法有望找到最佳解决方案，但计算成本高昂。此外，该方法仅适用于小型图。
第二种策略是局部搜索。局部搜索方法通过适度的局部调整迭代地改进现有答案。在顶点着色问题中，局部搜索技术可以切换两个相邻顶点的颜色。它也可能尝试只重新着色一个顶点。
贪婪方法可用于解决顶点着色问题。这些算法简单有效。然而，它们并非总能产生最佳结果。
顶点着色问题也可以表示为整数线性规划。此方法可以找到问题的精确解。然而，对于大型图，它可能变得极其昂贵。
顶点着色的应用
它在各个领域都有多种用途，包括运筹学和计算机科学。调度、路由、寄存器分配和无线频率分配是顶点着色问题的一些最常见用途。
我们必须将资源分配给可访问的任务，同时避免调度问题中的冲突。为了克服这一挑战，我们可以将每个作业表示为图中的一个顶点，将每个资源表示为一种颜色。该图还允许我们计算色数。因此，色数表示无冲突执行所有作业所需的最低资源。
网络路由问题。在路由中，数据包必须通过节点网络进行无冲突的路由。此外，我们可以使用顶点着色来描述这个问题，每个节点表示一个顶点，每条路径表示图中的颜色。
程序中的变量必须使用编译器分配给计算机处理器中的寄存器。我们可以使用顶点着色和色数原理来提供最少的寄存器来运行程序。
在无线网络通信中，顶点着色问题可用于为设备分配无线信道以减少干扰。
结论
在图论中，顶点着色是图标记的一个子集，涉及将标签传递给顶点或节点标签，以减少单个图中使用的颜色数量。调度、路由、寄存器分配和无线频率分配都是顶点着色在运筹学和计算机科学中的应用。
