图论-色度指数

Question

我必须编写一个程序来判断图是否d可着色--基本上我必须检查色度指数是d还是d+1，其中d是所有顶点的最大度数(vizing定理)。我知道这个问题是NP完全的，基本上它必须是强制的。我有一个想法，但不知道它是否正确-

1)找到deg(v) =d的顶点，并用d种不同的颜色给所有与v关联的边着色。

2)对于与v相邻的顶点关联的所有边，从d种颜色集中应用一些颜色

3)重复2)用于“发现”的边

如果所有的边都用d种颜色着色，则色度指数是d，我对图G有一种着色。

如果某些边不能用d种颜色中的颜色着色，就用d+1-st种颜色给他着色，用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;
}

Answer 1

为每条边生成约束，为具有最多边的顶点的所有边分配不同的颜色，然后从最受约束的边处理每条边。

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)

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

Answer 2

将图形转换为使用顶点着色算法非常简单:对于原始图形中的每条边(x，y)，在转换后的图形中创建顶点xy；对于原始图形中的每个顶点x，在转换后的图形中的所有顶点之间创建名称中包含x的边。

干杯