Graph algoritmo del colorante

Question

De wiki http://en.wikipedia.org/wiki/Graph_coloring

En su forma más simple, es una forma de colorear los vértices de un gráfico tal que no hay dos vértices adyacentes comparten el mismo color; esto se llama colorante de vértice . Del mismo modo, un colorante borde asigna un color a cada borde de modo que no hay dos bordes adyacentes comparten del mismo color, y una coloración cara de un gráfico planar asigna un color a cada cara o región, de modo que no hay dos caras que compartir un límite tiene el mismo color .

Dada 'n' colores y vértices 'm', la facilidad con que se puede colorear un algoritmo gráfico ser implementado en un lenguaje de programación?

Language no barrier.

Sólo un desafío para la mente.

(Suponga Gráfico y existen objetos de vértices)

Editar:
Después de leer la wiki, el problema es NP-completo Tiempo
a revisar libros de matemáticas :)
mi mal.
lo siento.

Sólo por curiosidad,
esto ha sido probado? como en programas de escritura para el mismo?
Escuché que esto se usa en redes ópticas?

¿No es esto similar a la coloración del cubo?
(mínimo número de colores a la cara del color de cubo para que no haya dos partes comparten el mismo color?)

Answer 1

Es un problema NP completo, leyó el Wikipedia entry para obtener más información sobre los distintos métodos de resolución.

Answer 2

Si le dan 2 colores, y el gráfico es 2-colorable (es decir, es bipartite graph), entonces puede hacerlo en tiempo polinomial bastante trivial.

Di un pseudocódigo como respuesta a esta pregunta: Graph colouring algorithm: typical scheduling problem.

Answer 3

Como se mencionó, el problema general es np-complete. Los gráficos bipartitos se pueden colorear utilizando solo 2 colores.

También es cierto que los grafos planos (gráficos que no contienen K3,3 or K5 como gráficos sub, según el teorema de Kuratowski) se pueden colorear con 4 colores.

Answer 4

En mi tesis de maestría, pruebo los algoritmos de coloreo. El algoritmo más simple es Edge Backtrace.

Esta es mi aplicación en Java:

public boolean edgeBackTrace (List<Edge<T>> edgesList, Map<Edge<T>, List<Edge<T>>> neighborEdges) { 
    for (Edge<T> e : edgesList) { 
    e.setColor(0); 
    } 
    int i = 0; 
    while (true){ 
    Edge<T> edge = edgesList.get(i); 
    edge.setColor(edge.getColor() + 1); 
    if (edge.getColor().equals(4)) { 
     edge.setColor(0); 
     if (i == 0) { 
     return true; 
     } else { 
     i--; 
     } 
    } else { 
     boolean diferentColor = false; 

     for (Edge<T> e : neighborEdges.get(edge)) { 
     if (e.getColor().equals(edge.getColor())) { 
      diferentColor = true; 
     } 
     } 

     if (diferentColor == false) { 
     i++; 
     if (i == edgesList.size()) { 
      return false; 
     } 
     } 
    } 
    } 
} 

El algoritmo devuelve un valor de true si el gráfico tiene coloración. Puede ver en bordesLista como el color, los bordes individuales.