algorithm - 图论-色度指数

我必须编写一个程序，说图是否为d可着色的-基本上我必须检查色度索引是d还是d + 1，其中d是所有顶点的最大程度(定理定理)。我知道这个问题是NP完全的，基本上必须进行暴力破解。我有一个主意，但不知道它是否正确-

1)查找deg(v)= d的顶点，并用d的不同颜色对入射到v的所有边进行着色。

2)对于所有与v相邻的顶点入射的边，应用d种颜色中的某些颜色

3)对“发现的”边缘重复2)

如果所有边缘都用d种颜色着色，则色度指数为d，而我具有图形G的一种着色。

如果某个边缘无法用d种颜色中的颜色进行着色，则用d + 1种颜色对他进行着色，而剩余的边缘中则用d + 1种颜色中的颜色进行着色-这是问题所在-如果我使用宣称色度指数为d + 1，是否有其他着色色度指数为d的机会？ (对于将要着色的每个边缘，我选择一种可以使用的颜色)。

另外，哪种图形表示形式最适合该问题？在输入文件中，图形以邻接矩阵形式编写。我知道可以通过递归来解决，但是我不知道如何解决。我陷入了一些过于复杂的主意:S(一些提示或伪代码将不胜感激)。

编辑:

刚想到，我认为应该没问题(纯暴力破解)。我还没有尝试实现这一点。如果您发现有问题，请发表评论。再说一遍-算法应该检查图是否可用d或d + 1种颜色着色，其中d是给定简单图中所有顶点的最大度，并找到一种着色...

colorEdge(edge, color, extra) {
    if (edge colored) return;  //if already colored, return
    if (can be colored in color) color it; //if color can be applied, apply it
    else {
        //else, 'd+1'-st color neded, so color it with that color, continue finding
        //coloring with d+1 colors
        extra = true;
        color it in color extra;
    }

    //recursivly try to color adjacent edges with available colors
    for each color c' from set of d colors {
        for each edge k adjacent to current {
            colorE(k, c', extra)
        }
    }
}

//main
bool extra = false;
for each color b from set of d colors {
    colorEdge(some starting edge, b, extra)
    if (!extra) break;
}

最佳答案

为每个边缘生成约束，为边缘最多的顶点的所有边缘分配不同的颜色，然后从约束最大的边缘开始处理每个边缘。

for each edge e1
for each edge e2
  if (e1 and e2 have a common vertex)
    e1.addConstaint(can't match e2's colour)
    e2.addConstaint(can't match e1's colour)

vertex v = vertex with most edges
if (v has more edges than colours we have available) STOP
assign each edge of v a different colour

Sort edges by number of constraints
Remove all edges connected to v (thus assigned a colour)

process(edge) :=
  while (haven't tried all colours within the constraints)
    edge.colour = next untried colour within the constraints
    process(next most constrained edge)

process(most constrained edge)

将最受约束的边缘定义为周围边缘已被分配颜色的边缘是一个好主意，但这可能会导致相当多的开销。