algorithm - 图论 - 色度指数

Question

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

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

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

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

如果所有边都用 d 种颜色着色，则色度指数为 d，并且 i 有图 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)

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