我必须制作一个程序来说明图形是否可着色 - 基本上我必须检查色度指数是 d 还是 d+1,其中 d 是所有顶点的最大度数(维辛定理)。我知道这个问题是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;
}