Algoritmos para coloreo

A Natalia le parecen interesantes los problemas de coloreo, y la verdad es que lo son, tal vez para salir un poco de la rutina de los que ya tenemos: Euler, Hamilton, mínimo árbol generador y camino más corto.

Tal vez agregar el tema de coloreos sea demasiado, o al revés, es posible que traiga variedad a los problemas que vemos.

Tenemos que tener en cuenta que de incluir el tema deberíamos dar un algoritmo (“receta”) para resolver el problema.

Como ya mencioné, como en el caso del ciclo de Hamilton, no se conocen algoritmos eficientes para resolver el problema del coloreo para grafos en general, y hay que recurrir a herramientas más allá de lo que queremos.

No habría problemas en proponer un algoritmo en Python que funcione razonablemente bien para un grafo con pocos vértices, y podemos ponerlo como “caja cerrada para apretar botones”, y también, como en el caso del viajante, podemos proponer una heurística del estilo “codicioso” o ”voraz” (“greedy” en inglés).

El algoritmo voraz más usado para este problema consiste en dar un orden a los vértices, dar un color al primero y continuar dando el primer color no usado por los vecinos a cada vértice que procesamos. Para más claridad, incluyo el ejemplo que aparece en un artículo de la FCEIA.