图论 - 色度指数

Question

我必须制作一个程序,它将说明图形是否可着色 - 基本上我必须检查色度指数是d还是d + 1,其中d是所有顶点的最大度数(vizing定理).我知道这个问题是NP完全的,基本上它必须是强制性的.我有一个想法,但不知道它是否正确 -

1)找到具有deg(v)= d的顶点并用v与d区分颜色的所有边缘着色.

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

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

干杯