Sorprendentemente, ¡todavía no hemos tenido ningún desafío en la coloración de gráficos!

Dado un gráfico no dirigido, podemos darle a cada vértice un color tal que no haya dos vértices adyacentes que compartan el mismo color. El número más pequeño χ de colores distintos necesarios para lograr esto se llama el número cromático del gráfico.

Por ejemplo, a continuación se muestra una coloración válida con el número mínimo de colores:

_{(Encontrado en Wikipedia)}

Entonces el número cromático de este gráfico es χ = 3 .

Escriba un programa o función que, dado un número de vértices N <16 (que están numerados del 1 al N ) y una lista de aristas, determina el número cromático de un gráfico.

Puede recibir la entrada y producir la salida en cualquier formato conveniente, siempre que la entrada no se procese previamente. Es decir, puede usar una cadena o una matriz, agregar delimitadores convenientes a la cadena o usar una matriz anidada, pero haga lo que haga, la estructura aplanada debe contener los mismos números que los ejemplos a continuación (en el mismo orden).

No puede utilizar funciones relacionadas con la teoría de grafos incorporadas (como las de Mathematica ChromaticNumber).

Puede suponer que el gráfico no tiene un bucle (un borde que conecta un vértice consigo mismo) ya que eso haría que el gráfico no se pueda colorear.

Este es el código de golf, gana la respuesta más corta (en bytes).

Ejemplos

Su programa debe resolver al menos todo esto en un tiempo razonable. (Debe resolver todas las entradas correctamente, pero puede tomar más tiempo para entradas más grandes).

Para acortar la publicación, en los siguientes ejemplos, presento los bordes en una sola lista separada por comas. En su lugar, puede usar saltos de línea o esperar la entrada en algún formato de matriz conveniente, si lo prefiere.

Triángulo (χ = 3)

3
1 2, 2 3, 1 3

"Anillo" de 6 vértices (χ = 2)

6
1 2, 2 3, 3 4, 4 5, 5 6, 6 1

"Anillo" de 5 vértices (χ = 3)

5
1 2, 2 3, 3 4, 4 5, 5 1

Imagen de ejemplo arriba (χ = 3)

6
1 2, 2 3, 3 4, 4 5, 5 6, 6 1, 1 3, 2 4, 3 5, 4 6, 5 1, 6 2

Generalización de lo anterior para 7 vértices (χ = 4)

7
1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 1, 1 3, 2 4, 3 5, 4 6, 5 7, 6 1, 7 2

Gráfico de Petersen (χ = 3)

10
1 2, 2 3, 3 4, 4 5, 5 1, 1 6, 2 7, 3 8, 4 9, 5 10, 6 8, 7 9, 8 10, 9 6, 10 7

Gráfico completo de 5 vértices, más vértice desconectado (χ = 5)

6
1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5

Gráfico completo de 8 vértices (χ = 8)

8
1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, 2 3, 2 4, 2 5, 2 6, 2 7, 2 8, 3 4, 3 5, 3 6, 3 7, 3 8, 4 5, 4 6, 4 7, 4 8, 5 6, 5 7, 5 8, 6 7, 6 8, 7 8

Enrejado triangular con 15 vértices (χ = 3)

15
1 2, 1 3, 2 3, 2 4, 2 5, 3 5, 3 6, 4 5, 5 6, 4 7, 4 8, 5 8, 5 9, 6 9, 6 10, 7 8, 8 9, 9 10, 7 11, 7 12, 8 12, 8 13, 9 13, 9 14, 10 14, 10 15, 11 12, 12 13, 13 14, 14 15

Python 2.7 - 122 109 111 109 108 103

f=lambda n,e,m=1:any(all(t*m//m**a%m!=t*m//m**b%m for(a,b)in e)for t in range(m**n))and m or f(n,e,m+1)

Uso:

print f(5, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

Fuerza bruta al aumentar el número cromático (m) y verificar todos los colores posibles. Un color puede describirse como un número en la base m. Entonces los posibles colores son 0, 1, ..., m ^ n-1.

editar: El gráfico completo de 8 vértices lleva bastante tiempo. Pero mi computadora portátil lo resuelve en unos 10 minutos. Los otros casos de prueba toman solo unos segundos.

editar 2: lea que el preprocesamiento está permitido, así que dejo que el índice de los vértices comience con 0: acorta t * m // m ** x% ma t // m ** a% m (-2). Disuelva lambda y ponga m en parámetros de función (-11)

Edición 3: no se permite el procesamiento previo -> volver a t * m (+4), simplificado // a / (-2).

editar 4: eliminar corchetes en cualquier (-2), gracias xnor.

editar 5: en lugar de tomar el módulo m dos veces, simplemente restarlos y luego usar el módulo (-1). Esto también es una gran mejora del rendimiento. Todos los casos de prueba juntos tardan unos 25 segundos en mi computadora portátil.

edit 6: llamada recursiva en lugar de while 1: ym + = 1 (-5). Gracias de nuevo, xnor.

Java - 241 218

int k,j,c;int f(int n,int[]e){for(k=1;k<=n;k++)for(long p=0;p<x(n);p++){for(j=0,c=0;j<e.length;c=p%x(e[j])/x(e[j]-1)==p%x(e[j+1])/x(e[j+1]-1)?1:c,j+=2);if(c<1)return k;}return 0;}int x(int a){return(int)Math.pow(k,a);}

La forma más obvia de hacer esto dadas las restricciones es la fuerza bruta. Simplemente recorra cada número cromático ky asigne cada color a cada vértice. Si no hay vecinos del mismo color, tienes tu número. Si no, muévete.

Esto lleva más tiempo para el caso de prueba χ = 8(los gráficos completos son una mierda aquí), pero aún es inferior a 15 segundos (bueno, unos 100 segundos con la última edición).

La entrada es el número de vértices ny una matriz de vértices de borde e[]dados en el mismo orden que los valores separados por comas de los OP.

Con saltos de línea:

int k,j,c;
int f(int n,int[]e){
    for(k=1;k<=n;k++)
        for(long p=0;p<x(n);p++){
            for(j=0,c=0;
                j<e.length;
                c=p%x(e[j])/x(e[j]-1)==p%x(e[j+1])/x(e[j+1]-1)?1:c,
                j+=2);
            if(c<1)return k;
        }
    return 0;
}
int x(int a){return(int)Math.pow(k,a);}

Ah, y esto supone que la entrada es una especie de gráfico coloreable. Si un borde se repite de v1 a v1, o no hay vértices, no se puede colorear y generará 0. Todavía funcionará para gráficos sin bordes χ=1, etc.

Python 3 - 162

Utiliza el mismo enfoque de fuerza bruta, pero utiliza la biblioteca de herramientas iterto para una generación de combinación con suerte más rápida. Resuelve el gráfico completo de 8 en <1 min en mi máquina bastante común.

import itertools as I
def c(n,v):
 for i in range(1,n+1):
  for p in I.product(range(i),repeat=n):
   if(0==len([x for x in v if(p[x[0]]==p[x[1]])])):return i

Ejemplo de uso para el caso completo de 8 gráficos:

print(c(8,[x for x in I.combinations(range(8), 2)]))

Haskell, 163 bytes

p x=f(length x)(transpose x)1
f a[b,c]d|or$map(\x->and$g x(h b)(h c))(sequence$replicate a[1..d])=d|0<1=f a b c(d+1)
g a=zipWith(\x y->a!!x/=a!!y)
h=map(flip(-)1)

El uso sería así:

p [[1, 2],[2, 3],[3, 1]]

Enfoque básico de fuerza bruta. Verifique todas las combinaciones de colores posibles si son válidas. No hay mucho más que decir aquí, excepto que me complace escuchar algún consejo para acortar esto aún más;)