图形着色 | 系列 1（简介和应用）
原文： https://www.geeksforgeeks.org/graph-coloring-applications/
图形着色问题是将颜色分配给受某些约束的图形的某些元素。
顶点着色是最常见的图形着色问题。 问题是，在给定 m 种颜色的情况下，找到了一种为图形的顶点着色的方法，使得没有两个相邻的顶点使用相同的颜色着色。 其他图形着色问题，例如 边着色 （没有顶点入射到相同颜色的两个边）和 面部着色 （地理图 着色）可以转换为顶点着色。
色数：将图形 G 着色所需的最小颜色数称为其色数。 例如，以下颜色至少可以涂 2 种颜色。
查找给定图的色数的问题是 NP Complete 。
图形着色的应用：
图形着色问题具有广泛的应用。
1）制定时间表或时间表： 假设我们要为一所大学制定考试时间表。 我们列出了不同的科目，每个科目都招收了学生。 许多科目将有普通学生（同批，一些积压学生等）。 我们该如何安排考试时间，以使同一位普通学生不会同时安排两次考试？ 安排所有考试需要多少个最短时间？ 此问题可以表示为一个图形，其中每个顶点都是一个主题，并且两个顶点之间的边意味着有一个普通的学生。 因此，这是一个图形着色问题，其中最小时隙数等于图形的色数。
2） 移动无线电频率指配 *：* 将频率分配给塔，在同一位置分配给所有塔的频率必须不同。 如何在此约束下分配频率？ 最少需要多少个频率？ 这个问题也是图形着色问题的一个实例，其中每个塔代表一个顶点，两个塔之间的边代表它们在彼此的范围内。
3）数独： 数独也是图着色问题的一种变体，其中每个单元代表一个顶点。 如果两个顶点在同一行，同一列或同一块中，则它们之间存在一条边。
4） 寄存器分配 *：* 在编译器优化中 寄存器分配是将大量目标程序变量分配给少量 CPU 寄存器的过程。 此问题也是图形着色问题。
5）二分图： 我们可以通过使用两种颜色为图形着色来检查图是否为二分图。 如果给定的图形是 2 色的，则它是两部分的，否则不是。 有关更多详细信息，请参见和。
6）地图颜色： 国家或州的地理地图，其中不能为两个相邻城市分配相同的颜色。 四种颜色足以为任何贴图着色（请参见四种颜色定理）
可以有更多应用程序：例如，下面的参考视频讲座以 1:18 进行案例研究。
Akamai 运行着由数千个服务器组成的网络，这些服务器用于在 Internet 上分发内容。 他们每周几乎都会安装一个新软件或更新现有软件。 无法将更新同时部署在每台服务器上，因为可能必须关闭服务器才能进行安装。 同样，一次更新不应一次完成，因为这将花费大量时间。 有些服务器不能一起拆卸，因为它们具有某些关键功能。 这是图形着色问题的典型调度应用。 事实证明，有 8 种颜色足以着色 75000 个节点的图形。 这样他们就可以通过 8 次安装更新。
我们将很快讨论解决图形着色问题的不同方法。
https://youtu.be/_sdVx_dWnlk
参考：
讲义 6 | MIT 6.042J 计算机科学数学，2010 秋季| 视频讲座
如果发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
版权属于：月萌API www.moonapi.com，转载请注明出处
