java - 我需要一个算法来获取图形的色数

Question

给定图的邻接矩阵，我需要获得 chromatic number (绘制图形的每个节点以使相邻节点获得不同颜色所需的最少颜色数)。

最好是java算法，我不关心性能。

谢谢。

编辑:最近引入了一个修复程序，所以答案更准确。现在它将用他以前的位置重新检查他的位置。

现在出现了一个新问题。提高他的“数字颜色”哪个更好？我所站的节点，或者我正在访问的节点(询问我是否与它相邻)？

public class Modelacion {

    public static void main(String args[]) throws IOException{

    //  given the matrix ... which i have hidden the initialization here

        int[][] matriz = new int[40][40];

        int color[] = new int[40];

        for (int i = 0 ; i<40;i++)
            color[i]=1;

        Cromatico c = new Cromatico(matriz, color);

    }
}

import java.io.IOException;


public class Cromatico {

Cromatico(int[][]matriz, int[] color, int fila) throws IOException{

        for (int i = 0; i<fila;i++){
            for (int j = 0 ; j<fila;j++){
                if (matriz[i][j] == 1 && color[i] == color [j]){
                    if (j<i)
                        color [i] ++;
                    else
                        color [j] ++;
                }
            }
        }

        int numeroCromatico = 1;
        for (int k = 0; k<fila;k++){
            System.out.print(".");
            numeroCromatico = Math.max(numeroCromatico, color[k]);  
        }

        System.out.println();
        System.out.println("el numero cromatico del grafo es: " + numeroCromatico);

    }
}

Answer 1

求图的色数是 NP 完全的(参见 Graph Coloring )。它甚至是 NP-Complete 来确定给定的图形是否是 3 色可着色的(并且还可以找到着色)。

上一段中链接到的 wiki 页面有一些您可能会用到的算法描述。

顺便说一句，既然它是 NP-Complete 并且您并不真正关心性能，为什么不尝试使用蛮力呢？

猜一个色数k，尝试顶点着色的所有可能性(最大k^n种可能性)，如果不可着色，则新猜色数= min{n,2k}。如果它是 k-colorable，则新猜测色数 = max{k/2,1}。重复，按照二进制搜索使用的模式找到最佳 k。

祝你好运!

并回答您的修改。

递增颜色的两种选择都不起作用。另外，您的算法是 O(n^2)。这本身就足以说明你的算法很可能是错误的，即使不寻找反例也是如此。这个问题是 NP 完全的!