Unidad IV. Coloración de grafos
Teoría de grafos 2-2010
Ing. Josmary Fernández

Definiciones y Grafos
UNEFA Núclo Mérida

Coloración de grafos
Hay muchos problemas, como la asignación de tareas y los problemas de almacenamiento, donde es necesario partir el conjunto de vértices (resp. aristas) de un grafo asociado de tal forma que vértices (resp. aristas) adyacentes pertenezcan a diferentes conjuntos de la partición. Tales particiones se interpretan habitualmente en términos de colores, asignando a los elementos de cada parte un mismo color. Por esto se llaman coloraciones (resp. coloraciones de aristas).
Los problemas sobre coloración de grafos fueron, en la segunda mitad …ver más…

Se presenta un procedimiento secuencial para colorear los vértices de un grafo siguiendo un orden impuesto a los vértices, usando la menor cantidad de colores posibles. Este algoritmo es llamado austero (avaricioso, greedy en inglés).
Supongamos que C={c1,c2,...} es el conjunto de colores; procedemos a describir el algoritmo que denominamos algoritmo austero y consta de los siguientes pasos:
•Paso inicial. Ordenamos los vértices del grafo. Es importante notar que la eficiencia del algoritmo depende del orden que elijamos. Hacemos una lista de los vértices del grafo (v1, v2,..., vn).
Un buen orden debe minimizar los colores prohibidos: se deben colocar los vértices de mayor orden al principio. De todas maneras no hay un criterio establecido para construir dicho orden.
•Primer paso. Le asignamos el primer color c1 al vértice v1.
•Segundo paso. Procedemos a asignar un color al vértice v2 así: si es adyacente al vértice v1 le asignamos el siguiente color c2, en otro caso le asignamos c1.
•k­ésimo paso. Para colorear el vértice vk buscamos todos los vértices del conjunto {v1,v2,...,

Unidad IV. Coloración de grafos
Teoría de grafos 2-2010
Ing. Josmary Fernández

Definiciones y Grafos
UNEFA Núclo Mérida

vk−1} que son adyacentes a vk y determinamos los colores que han sido