Algoritmo Austero para Colorear

ALGORITMO AUSTERO PARA COLOREAR
Damos un procedimiento para colorear los vértices de un grafo siguiendo un orden impuesto a los vértices, usando la menor cantidad de colores posibles.
Supongamosque es el conjunto de colores; procedemos a describir el algoritmo que denominamos algoritmo austero y consta de los siguientes pasos:
1. Paso inicial.- Ordenamos los vértices del grafo. Esimportante notar que la eficiencia del algoritmo depende del orden que elijamos. Hacemos una lista de los vértices del grafo

2. Primer paso.- Le asignamos el primer color al vértice .
3. Segundo paso.-Procedemos a asignar un color al vértice así: si es adyacente al vértice le asignamos el siguiente color , en otro caso le asignamos
4. k-ésimo paso.- Para colorear el vértice buscamos todos losvértices del conjunto que son adyacentes a y determinamos los colores que han sido usados en sus coloraciones; luego usamos el primero disponible en el orden de que no haya sido usado en la coloraciónde los vértices adyacentes a
Ejemplo:
Consideremos el siguiente grafo con los vértices ordenados y C = {a, b, c,. . .}

Usamos el algoritmo austero para asignar los colores:
Al vértice v1 leasignamos el colora a; puesto que el vértice v2 es adyacente a v1 le asignamos el color b; el vértice v3 es adyacente a v2 pero no es adyacente a v1, de este modo le asignamos el color a; v4 es adyacentea v2 y v3, luego le asignamos el color c; v5 le corresponde a; v6 le corresponde b y a v7 le corresponde b.
La coloración correspondiente siguiendo el algoritmo austero es

El número de coloresusado es tres el cual es su número cromático. No siempre este algoritmo nos da una coloración donde el número de colores es igual al número cromático. Damos un ejemplo.
Ejemplo:
Consideremos el grafodel cubo Q3



Esta última coloración es la mejor. Hay dos cosas importantes, las coloraciones dependen del orden en que se elijan los vértices. La otra que no es tan evidente es que podemos...