我必须制作一个程序来说明图形是否可着色 - 基本上我必须检查色度指数是 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;
}