Мне нужен алгоритм для получения хроматического числа графа

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

Супер медленный, но он должен работать:

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; 
} 

Answer 2

Нахождение хроматического числа графа является NP-Complete (см Graph Coloring). Это NP-Complete даже для того, чтобы определить, является ли данный граф 3-цветным (а также найти раскраску).

Вики-страница, связанная в предыдущем абзаце, содержит некоторые описания алгоритмов, которые вы, вероятно, можете использовать.

btw, так как это NP-Complete, и вы действительно не заботитесь о производительности, почему бы вам не попробовать использовать грубую силу?

Удовлетворите хроматическое число k, попробуйте все возможности раскраски вершин (max k^n возможностей), если оно не окрашивается, новое предположение для хроматического числа = min {n, 2k}. Если это k-colorable, новое предположение для хроматического числа = max {k/2,1}. Повторите, следуя шаблону, используемому бинарным поиском, и найдите оптимальный k.

Удачи вам!

И ответить на ваши изменения.

Ни один из вариантов увеличения цвета не будет работать. Кроме того, ваш алгоритм O (n^2). Этого достаточно, чтобы сказать, что очень вероятно, что ваш алгоритм ошибочен, даже не ища контрпримеры. Эта проблема NP-Complete!