图度作为无向图绘制的解

Question

问题是：

给定一个表示为邻接矩阵和整数k的无向图，编写一个函数来确定该图中的每个顶点是否可以着色，使得两个相邻的顶点都不能使用最多k个颜色共享相同的颜色。来源：https://www.dailycodingproblem.com/

所提出的解决方案使用回溯算法(https://www.dailycodingproblem.com/blog/graph-coloring)，但我想知道仅仅计算顶点度是否足够(来源：https://youtu.be/LUDNz2bIjWI?t=169)。

    boolean canBeColored(int[][] adjacencyMatrix, int colors) {

    for (int row = 0; row < adjacencyMatrix.length; row++) {
        int degree = 0;
        for (int column = 0; column < adjacencyMatrix[row].length; column++) {
            if (adjacencyMatrix[row][column] == 1) {
                degree++;
            }
        }

        if (degree > colors) {
            return false;
        }
    }

    return true;
}

Answer 1

事实并非如此。考虑一个三角形图，它有树节点和三个边。所有顶点都有二级，但需要三种颜色才能对其着色。对于该输入，您的功能将失败。

事实上，这个问题是NP-完全的，这意味着它不知道是否可以构造一个有效的算法来解决它。因此，如果你能做到这一点，你将赢得声誉和财富，也是一个非常大的奖金。