我需要一个算法来得到一个图的色数

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）。即使确定一个给定的图是否是3-可着色的（以及找到一个着色），它也是NP完全的

上一段中链接到的wiki页面有一些算法描述，您可能可以使用这些描述

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

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

祝你好运

并回答您的编辑

增加颜色的选项都不起作用。另外，您的算法是O（n^2）。这本身就足以说明您的算法很可能是错误的，即使不寻找反例。这个问题是NP完全问题

Answer 2

超慢，但它应该可以工作：

int chromaticNumber(Graph g) {
  for (int ncolors = 1; true; ncolors++) {
    if (canColor(g, ncolors)) return ncolors;
  }
}

boolean canColor(Graph g, int ncolors) {
  return canColorRemaining(g, ncolors, 0));
}

// recursive routine - the first colors_so_far nodes have been colored,
// check if there is a coloring for the rest.
boolean canColorRemaining(Graph g, int ncolors, int colors_so_far) {
  if (colors_so_far == g.nodes()) return true;
  for (int c = 0; c < ncolors; c++) {
    boolean ok = true;
    for (int v : g.adjacent(colors_so_far)) {
      if (v < colors_so_far && g.getColor(v) == c) ok = false;
    }
    if (ok) {
      g.setColor(colors_so_far, c);
      if (canColorRemaining(g, ncolors, colors_so_far + 1)) return true;
    }
  }
  return false;
}