图着色|集1（简介和应用）

图着色 问题是根据特定的约束为图形的特定元素指定颜色。

顶点着色 是最常见的图着色问题。问题是，给定m个颜色，找到一种给图的顶点着色的方法，这样就不会有两个相邻的顶点使用相同的颜色着色。其他的图着色问题，比如 边着色 （没有顶点与相同颜色的两条边关联）和 面部着色 （地理地图着色）可以转换为顶点着色。

色数： 图G着色所需的最小颜色数称为其色数。例如，以下颜色可以至少为2种颜色。

求给定图的色数的问题是 NP完全 .

图着色的应用：

图的着色问题有着大量的应用。

1） 制定时间表或时间表： 假设我们想为一所大学制定am考试时间表。我们列出了不同的科目和每个科目的注册学生。许多科目都会有普通学生（同一批、一些积压学生等）。 我们如何安排考试，这样就不会同时安排两个普通学生的考试？安排所有考试最少需要多少时间？ 这个问题可以表示为一个图，其中每个顶点都是一个主题，两个顶点之间的边意味着有一个共同的学生。这是一个图着色问题，其中最小时隙数等于图的色数。

2) 移动无线电频率分配 : 将频率分配给塔时，分配给同一位置的所有塔的频率必须不同。如何分配具有此约束的频率？所需的最低频率是多少？这个问题也是图着色问题的一个例子，其中每个塔代表一个顶点，两个塔之间的边代表它们在彼此的范围内。

3） 数独： 数独也是图着色问题的一种变体，其中每个单元代表一个顶点。如果两个顶点位于同一行、同一列或同一块中，则它们之间有一条边。

4) 寄存器分配 : 在编译器优化中，寄存器分配是将大量目标程序变量分配给少量CPU寄存器的过程。这个问题也是一个图着色问题。

5） 二部图： 我们可以通过使用两种颜色对图着色来检查图是否为二部图。如果给定的图是2-可着色的，那么它是二部图，否则不是。看见 这 更多细节。

6） 地图着色： 没有两个相邻城市不能被分配相同颜色的国家或州的地理地图。四种颜色足以为任何地图上色（请参见 四色定理 )

还有更多的应用程序： 例如，下面的参考视频讲座在1:18有一个案例研究。 Akamai 运行由数千台服务器组成的网络，这些服务器用于在Internet上分发内容。他们几乎每周都会安装新软件或更新现有软件。无法同时在每台服务器上部署更新，因为安装时可能必须关闭服务器。此外，不应该一次更新一个，因为这需要很多时间。有些服务器无法一起拆除，因为它们具有某些关键功能。这是图着色问题的一个典型调度应用。结果表明，8种颜色足以为75000个节点的图形着色。这样他们就可以在8个过程中安装更新。

我们将很快讨论解决图着色问题的不同方法。 https://youtu.be/_sdVx_dWnlk 参考资料： Lec 6 |麻省理工学院6.042J计算机科学数学，2010年秋季|视频讲座

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论