Coloracion De Grafos.

UNIDAD #4_COLORACIÓN DE GRAFOS.

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 del siglo XIX, uno de los hitos iniciales de la Teoría de Grafos. En aquel tiempo se planteó uno de los problemas clásicos, "El Problema de los cuatro colores", que no se resolvió hasta 1976 con la ayuda del ordenador.

Una coloración de un grafo G=(V,A) es una asignación de colores a los vértices de G, a cada vértice un color, de forma que vértices adyacentes reciban colores distintos. Si en la coloración se usan k colores diremos que es una K coloración. En algunas fuentes, estas coloraciones se denominan coloraciones admisibles; aquí, por comodidad, las denominamos coloraciones.

Grafos coloreables

Si existe una k coloración de G se dice que el grafo G es kcoloreable.

Las coloraciones siempre existen, pues podemos asignar a cada vértice del grafo un color diferente si fuera necesario. Cada coloración de G produce en el conjunto de vértices, V(G), una partición en conjuntos independientes denominados clases de color. Un conjunto de vértices I se llama independiente si dos vértices cualesquiera de I no son adyacentes.

Número cromático

El número cromático de un grafo G, χ(G), es el número mínimo de colores necesario para colorear G.

Coloración de vértices

Los algoritmos conocidos para colorear los vértices de un grafo se clasifican en dos grandes grupo: secuenciales e independientes. Dada una ordenación de los vértices del grafo, los algoritmos secuenciales asignan el mínimo color posible al siguiente vértice. Es decir, si queremos colorear el vértice v, teniendo ordenados numéricamente los colores, asignamos a v el color más pequeño que no aparece entre los asignados a los vecinos de v ya coloreados. La ordenación inicial es esencial para colorear con pocos colores.

Los algoritmos “independientes” buscan en primer lugar un conjunto independiente de vértices

I1 de cardinal grande, colorea todos los vértices con el color 1, elimina los vértices de I1 y repite el proceso en el grafo GI1, continuando así hasta colorear todos los vértices.

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

...