algorithm - 图形着色需要什么？

Question

图着色的实际应用是什么。换句话说，为什么我们需要使用这样的算法来优化颜色数量（问题的一些重要特征）。

Answer 1

您似乎对什么是图形着色有一些误解，也可能对什么是图形有一些误解。
实际颜色与此无关，图形着色用于解决资源有限或其他限制的问题。颜色只是您尝试优化的任何资源的抽象，而图表是您的问题的抽象。

网络上有很多关于图论的资源，所以简而言之 - 图是一组元素（称为顶点）的抽象表示，其中一些元素共享一个连接（称为边）。这当然是最基本的概念，还有很多其他的属性可以加在上面，比如有向边、权重等等，不过这个概念现在应该够用了。

图经常被用来模拟各种现实世界的问题（有时也是虚构的问题，因为数学家和计算机科学家毕竟还是要继续发表论文），我们现在有许多算法可以有效地处理它们（在复杂性），找到各种可能有趣的属性以解决上述问题。或者，我们有时可以证明一个问题不能用任何有效的算法来解决。图形着色是其中之一（或更准确地说，问题：can a graph be colored in up to k colors，或问题what is the minimal number of colors needed to color the graph)，除非我们正在处理某些图的子类型，例如平面图（邻国地图是一个很好的例子，因为它被用于一些有趣的图着色证明）。这里的着色意味着将“颜色”或数字附加到每个顶点，使得没有两个具有连接边的顶点具有保存值。

可以应用图形着色的现实生活问题的示例：您设计一个编译器，在给定程序中观察 N 个变量，并希望将尽可能多的变量分配到寄存器中（其余的将不得不溢出到内存，速度较慢，最好避免）。但是，您的 CPU 总共只有 16 个逻辑寄存器。但是，从好的方面来说 - 您知道哪些变量在相同的上下文和时间中使用，哪些不是。显然，那些不在一起的可以使用相同的寄存器。那么，您可以将所有变量分配到现有的寄存器集中吗？

为了解决这个问题，您可以构建一个以变量为顶点的图形，其中一条边连接在同一时间范围内使用的每两个变量。用最少数量的“颜色”为该图着色会告诉您总共需要多少个寄存器，因为每种颜色都可以分配给一个寄存器，并且由于着色前提 - 没有 2 个同时存在的变量可以使用相同的“颜色"（注册），因为它们将通过边缘连接并且不能以相同的方式着色。

Answer 2

数独求解器是图形着色派上用场的经典示例。

请注意，这里的颜色数量受游戏规则的限制。图着色算法中的“颜色”通常是比喻性的，而不是文字的。数独更常使用数字 1-9 而不是颜色，但这并不能阻止图形着色的相关性。

Answer 3

有很多实际应用依赖于图形着色。例如，蜂窝天线的频率分配是一个著名的问题。在这个问题中，只能使用少量频率（颜色），并将它们分配给天线，以便客户端始终连接到其中一个天线。当多个天线的覆盖区域重叠时会出现问题，在这种情况下，我们希望至少有一个具有唯一频率（颜色）的天线。在这个问题中不能使用简单的适当（非单调）着色。

在上述情况下，我们处理超图的着色。我们根据着色问题定义超图。并且有不同的着色变体，例如无冲突着色，唯一最大着色。在静态情况下进行了许多研究，其中超图不随时间变化。并且在线设置的情况下正在进行许多有趣的研究，其中超边缘可能会随时间变化（例如某些天线停止工作，或者新天线固定在某个位置）。

您还可以参考1篇调查论文，了解更多关于有趣的着色问题及其应用的信息。