Honestamente, no puedo creer que esto no se haya preguntado, pero aquí está

Antecedentes

Dado un simple gráfico plano no dirigido (el gráfico se puede dibujar en el plano sin intersecciones), es un teorema comprobado que el gráfico es de 4 colores, un término que exploraremos en un momento. Sin embargo, es mucho más fácil hacer un gráfico de 5 colores, que es en lo que enfocaremos nuestro desafío hoy.

Una coloración k válida de un gráfico es una asignación de "colores" a los nodos del gráfico con las siguientes propiedades

1. Si dos nodos están conectados por un borde, los nodos se colorean con colores diferentes.
2. En todo el gráfico, hay un máximo de 5 colores.

Dado esto, le presentaré un algoritmo bastante básico para 5 colores de cualquier gráfico plano simple no dirigido. Este algoritmo requiere las siguientes definiciones

Accesibilidad : si el nodo 1 es accesible desde el nodo 2, eso significa que hay una secuencia de nodos, cada uno conectado al siguiente por un borde, de modo que el primer nodo es el nodo 2 y el último es el nodo 1. Tenga en cuenta que desde gráficos no dirigidos son simétricos, si el nodo 1 es accesible desde el nodo 2, el nodo 2 es accesible desde el nodo 1.

Subgrafo : Un subgrafo de un gráfico de un conjunto dado de nodos N es un gráfico donde los nodos del subgrafo están todos en N, y un borde del gráfico original está en el subgrafo si y solo si ambos nodos están conectados por el borde están en N.

Deje que Color (N) sea una función para colorear gráficos planos con N nodos con 5 colores. Definimos la función a continuación.

1. Encuentre el nodo con el menor número de nodos conectados a él. Este nodo tendrá como máximo 5 nodos conectados a él.
2. Elimina este nodo del gráfico.
3. Llame a Color (N-1) en este nuevo gráfico para colorearlo.
4. Agregue el nodo eliminado nuevamente al gráfico.
5. Si es posible, coloree el nodo agregado en un color que ninguno de sus nodos conectados tenga.
6. Si no es posible, los 5 nodos vecinos al nodo agregado tienen 5 colores diferentes, por lo que debemos intentar el siguiente proceso.
7. Numere los nodos que rodean el nodo agregado n1 ... n5
8. Considere el subgrafo de todos los nodos en el gráfico original coloreado del mismo color que n1 o n3.
9. Si en este subgrafo, n3 no es accesible desde n1, en el conjunto de nodos accesibles desde n1 (incluido n1), reemplace todas las ocurrencias del color de n1 con n3 y viceversa. Ahora colorea el color original del nodo n1 agregado.
10. Si se pudo acceder a n3 desde n1 en este nuevo gráfico, realice el proceso desde el paso 9 en los nodos n2 y n4, en lugar de n1 y n3.

Desafío

Dada una entrada de una lista de bordes (que representa un gráfico), colorea el gráfico, asignando un valor a cada nodo.

Entrada : una lista de aristas en el gráfico (es decir, [('a','b'),('b','c')...])

Tenga en cuenta que la lista de bordes de entrada será tal que si (a, b) está en la lista, (b, a) NO está en la lista.

Salida : un objeto que contiene pares de valores, donde el primer elemento de cada par es un nodo, y el segundo su color, es decir, [('a',1),('b',2)...]o{'a':1,'b':2,...}

Puede usar cualquier cosa para representar colores, desde números, caracteres, a cualquier otra cosa.

La entrada y salida es bastante flexible, siempre y cuando sea bastante claro cuáles son las entradas y salidas.

Reglas

• Este es un desafío de código de golf
• No tiene que usar el algoritmo que he descrito anteriormente. Simplemente está ahí para referencia.
• Para cualquier gráfico, a menudo hay muchos métodos válidos para colorearlos. Mientras el color que produzca su algoritmo sea válido, eso es aceptable.
• Recuerde que el gráfico debe ser de 5 colores.

Casos de prueba

Use el siguiente código para probar la validez de sus resultados de coloración. Como hay muchos colores de gráficos válidos por gráfico, este algoritmo simplemente verifica la validez del color. Vea la cadena de documentación para ver cómo usar el código.

Algunos casos de prueba aleatorios (y bastante tontos) :

Caso de prueba 2: Krackhardt Kite Graph [(0, 1), (0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]

Una salida válida: {0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}

Nota : Estos casos de prueba son demasiado pequeños para probar el comportamiento más matizado del algoritmo de coloración, por lo que construir sus propios gráficos es probablemente una buena prueba de la validez de su trabajo.

Nota 2 : Agregaré otra pieza de código que graficará su solución para colorear pronto.

Nota 3 : ¡No preví los algoritmos de coloración aleatoria que se han presentado, que es lo genial de PPCG! Sin embargo, si alguien pudiera desarrollar un algoritmo más determinista, también sería genial.

Python 2 , 96 bytes

i=0
g=input()
while 1:i+=1;c={k:i/4**k%4for k in sum(g,())};all(c[s]^c[t]for s,t in g)>0<exit(c)

Pruébalo en línea!

$g$$i$$c$$c$$c$

La entrada es plana, por lo que siempre es posible encontrar un color 4.

(Por lo tanto: esto encuentra el color lexicográficamente más temprano en cierto sentido, y lo hace de manera muy ineficiente).

$k$$\Big\lfloor \frac{i}{4^k} \Big\rfloor \bmod 4$$k$$i$

JavaScript (ES7), 80 76 74 bytes

Guardado 2 bytes gracias a @Neil

El mismo enfoque que Lynn . Resuelve en 4 colores, numerados del 0 al 3 .

a=>{for(x=0;a.some(a=>a.map(n=>z=c[n]=x>>n*2&3)[0]==z,c={});x++);return c}

Pruébalo en línea!

Brachylog , 38 bytes

cd{∧4>ℕ}ᶻ.g;?z{tT&h⊇ĊzZhpT∧Zt≠}ᵐ∧.tᵐ≜∧

Pruébalo en línea!

Explicación

Example input: [["a","b"],["c","b"]]

cd                                       Concatenate and remove duplicates: ["a","b","c"]
  {∧4>ℕ}ᶻ.                               The output is this list zipped zith integers that
                                           are in [0..4]: [["a",I],["b",J],["c",K]]
         .g;?z                           Zip the output with the input:
                                           [[[["a",I],["b",J],["c",K]],["a","b"]],[["a",I],["b",J],["c",K]],["c","b"]]
              {               }ᵐ∧        Map for each element
               tT                        Call T the couple of nodes denoting an edge
                 &h⊇Ċ                    Take a subset of 2 elements in the head
                     zZ                  Zip and call it Z
                      ZhpT               The nodes in Z are T up to a permutation
                          ∧Zt≠           The integers in Z are all different color
                                 .tᵐ≜∧   Label the integers (i.e. colors) in the output so that
                                           it matches the set constraints

Python 2 , 211 bytes

def f(g):
 g={k:[(a,b)[a==k]for a,b in g if k in(a,b)]for k in sum(g,())};c={k:0 for k in g}
 for a,b in sorted(g.iteritems(),key=lambda a:len(a[1])):c={k:(c[k],c[k]+1)[c[a]==c[k]and k in b]for k in c}
 return c

Pruébalo en línea!

Determinista! Probablemente fallaría en casos de prueba más complicados, pero estoy demasiado agotado para encontrar un gráfico para el que falla. Más casos de prueba y críticas. ¡Bienvenidos!

Limpio , 139 bytes

import StdEnv,Data.List
$l#(a,b)=unzip l
#e=nub(a++b)
=hd[zip2 e c\\c<- ?e|all(\(a,b)=c!!a<>c!!b)l]
?[h:t]=[[n:m]\\n<-[0..4],m<- ?t]
?e=[e]

Pruébalo en línea!

Genera todos los colores y devuelve el primero válido.

Jalea , 23 bytes

®iⱮⱮ³¤ịE€S
FQ©L4ṗÇÐḟḢ®ż

Pruébalo en línea!

Fuerza bruta. Asume que los nodos están etiquetados por enteros.