graph - 快速着色图的边缘

Question

假设我贪婪地将颜色分配给图形的边缘，G = (V,E)如下所示，

1. 选择一条未着色的边 (u,v)
2. 识别所有与 u 接触的边缘的颜色并选择最低的未使用颜色。对 v 做同样的事情。
3. 分配 (u,v) 两种颜色中较大的一种。

执行步骤 2 的一种简单方法是检查所有颜色1,2,...，直到遇到任何边缘接触都未使用的颜色u。有更快的方法吗？

Answer 1

看看这个。根据您的确切需求，您可以使用可以提高性能的算法变体，无论您正在寻找一种或所有解决方案。

Answer 2

您还可以遍历连接到 的所有边u，消除使用的颜色，然后选择第一个未使用的颜色。