Reticulados Ordenamiento De Los Elementos Teoría De Grafos

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 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. 
Definición formal
Formalmente, una coloracion de G con colores de C es una aplicacion:
ω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 coloreablesSi 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   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.
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?

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

Definiciones y Grafos
UNEFA Núclo Mérida

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