Programa realizado en el ámbito académico. Es uno de mis mejores trabajos y de los que estoy más orgulloso.

Introducción

¿Qué es un grafo?

Un grafo es un conjunto de vértices intercomunicados por aristas (como en la imagen de portada). Son útiles para plantear y resolver cierto tipo de problemas, ej: el problema del viajante.

¿Que es un coloreo de grafo?

A cada vértice se le asigna un “color”, con la condición que no hayan 2 o más vértices que estén conectados por alguna arista y que tengan el mismo color.

Un coloreo trivial para un grafo sería asignarle un color distinto a cada vértice.

¿Qué es un coloreo propio de grafo?

Un coloreo propio de un grafo, es un coloreo de grafo, con la condición agregada que se estén utilizando la menor cantidad de colores posibles.

Llamaremos χ (Chi) a la mínima cantidad de colores necesarios para generar un coloreo propio del grafo.

Resulta que, salvo para casos particulares, no existe un algoritmo polinomial (rápido) para generar un coloreo propio de un Grafo, a causa de esto vamos a utilizar una heurística, es decir, una función que aproxime el valor de χ. Dicha función va a ser utilizar múltiples veces Greedy, el cual depende del ordenamiento inicial de los vértices.

Diseño

Este programa fue pensado desde un principio para manejar grafos grandes, del orden de millones de vértices y decenas de millones de aristas, y utilizar Greedy mil veces!. Por lo tanto para soportar tales magnitudes se tuvo que pensar en eficiencia de manera constante durante todo el proceso de desarrollo.

Si no se tiene mucho cuidado se podría desarrollar un programa que tarde días o incluso meses en terminar!

Profundidad

Por información más específica y forma de uso, ver el repositorio con código fuente.