Coloración De Grafos

Coloración de grafos Definiciones y 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 coloración.

Definición formal

Formalmente, una coloración de G con colores de C es una aplicación:

ωV(G) → C tal que si {v,w} ∈ E(G) entonces ω(v)҂ω(w).

Observació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 k­coloreable.

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 devé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.

No es fácil determinar el número cromático de un grafo. De hecho, el correspondiente problema de decisión, conocido por Chromatic Number Problem, es un problema NP­ completo: Dado un grafo G y un entero k, ¿es cierto que χ(G) ≤ k?

Algunas observaciones inmediatas sobre el numero cromático son las siguientes:

1. Para todo grafo G, χ(G)≤|V|, porque siempre podremos colorear con |V| colores, asignando a cada vértice un color distinto. Esta es, obviamente, la forma menos efectiva de colorear.

2. Si el grafo contiene al menos una arista, necesitaremos dos colores como mínimo; es decir, si

|A| ≥ 1, entonces χ(G) ≥ 2.

3. Si G contiene a G′ como subgrafo, entonces χ(G)≥χ(G′)

4. Si G tiene k componentes conexas, G1,G2, . . . ,Gk que tienen números cromáticos χ(G1), χ(G2), . . . , χ(Gk) respectivamente, entonces χ(G) = máx (1≤i≤k){χ(Gi)}

5. Si G y G′ son isomorfos, entonces χ(G) =χ(G′).

6. Todo grafo planar es 4­coloreable.

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 G­I1, 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 c1.

•k­ésimo paso. Para colorear el vértice vk buscamos todos los vértices del conjunto {v1,v2,...,vk−1} que son adyacentes a vk y determinamos los colores que han sido usados en sus coloraciones; luego usamos el primero disponible en el orden de C que no haya sido usado en la coloración de los vértices adyacentes a vk.

Ejemplo: En unas jornadas científicas se van a dictar cierto número de conferencias. Si los horarios de dos conferencias se solapan, éstas tienen que dictarse en salones distintos. Consideremos el grafo G que tiene como vértices a las conferencias, y en el cual dos conferencias son adyacentes si y sólo si sus horarios se solapan. Entonces decir que G es k­colorable equivale a decir que k salones son suficientes para dictar todas las conferencias.

El número cromático (G) representa el mínimo número de salones necesario para poder dictar todas las conferencias..

Usamos el algoritmo austero para asignar los colores: Al vértice v1 le asignamos el colora a; puesto que el vértice v2 es adyacente a v1 le asignamos el

...