Informática

P.Reyes

Introducción
Coloreado de mapas:

Matem mática Discreta

P.Reyes

Introducción
Coloreado de mapas:

Matem mática Discreta

P.Reyes

Introducción
Coloreado de mapas:

Matem mática Discreta

P.Reyes

Introducción
En un laboratorio hay una serie de compuestos químicos {A,B,C,D,E,F,G,H} que hay que almacenar en cajas para su traslado. No pueden ser almacenados enuna misma caja dos compuestos que reaccionen entre sí (como ácidos y bases). Los productos que reaccionan vienen dados por la siguiente tabla. ¿Cómo podemos elegir los i i d d l i i t t bl Có d l i l elementos que hemos de introducir en cada caja?, ¿cuántas cajas serán necesarias para poder trasladar los productos?, etc.
A B A D E C A E F D B E G E B C D G H F C H G D E H H E F G

Matemmática Discreta

B C

A

B

A

B

H

C

H

C

G

D

G

D

F

E

F

E

P.Reyes

Tema 5: Coloreado

• Coloración de vértices.
Matem mática Discreta

• Coloración de aristas

P.Reyes

Coloración de vértices
Dado un grafo G=(V,A), se llama vértice-coloración de G a toda función c: V que verifique c(u)  c(v) si {u,v}A. c(u)=1, c(v)=2, ... ( ) 1 ( ) 2 colores l|c(V)|=k | (V)| k N,

Matemática  Discreta

k-vértice-coloración k é ti l ió

Colorac ción de grafos e

Una vértice-coloración de un grafo efectua una partición del g g p grafo en conjuntos j independientes de vértices V = V1  V2  ... Vk Vi = { v V | c(v)=i }

A

B

4-vértice-coloración
H C

V = V1 V2  V3 V4 V1 = { A,E }

G

D

V2= { B,F } V3 = { C,G } V4 = { D,H }F

E

Tema 6: 6

P.Reyes

Coloración de vértices
Dado un grafo G=(V,A), se llama número cromático de G ( (G) ) al menor número entero k, de forma que existe una vértice-coloración de G con k colores.
A B
A B

Matemática  Discreta

H

C

Colorac ción de grafos e

H

C

G

D

G

D

F

E

F

E

4-vértice-coloración

3-vértice-coloración

(G) = 3
Eltraslado de los compuestos químicos se puede llevar a cabo con tan sólo 3 cajas.
Tema 6: 7

P.Reyes

Coloración de vértices
Propiedades del número cromático:

Matemática  Discreta

(G) = 1

G es un grafo trivial (n vértices aislados)

Si G es un grafo con n vértices, 1  (G)  n .

Colorac ción de grafos e

Si G’ es un subgrafo de G, (G’)  (G) .

grafo G: (G) = max {(G1),(G2), ...., (Gc) }.

Si G1, G2, ... , Gc son las componentes conexas del

Tema 6: 8

P.Reyes

Coloración de vértices
¿Cuáles serán los números cromáticos de los grafos Kn y Cn?)

Matemática  Discreta

1 1
K2

2 4 3
K4

(Kn) = n
2 5 1 2

Colorac ción de grafos e

1

3
K3

2 4 1 3 C5 2
K5

3

1 2 C8 1

2 1

2

(Cn) =

2 si n es par 3 si n es impar
1Tema 6: 9

2

1

2

P.Reyes

Coloración de vértices
Calcular el número cromático de un grafo cualquiera es un “problema intratable”. Dado un número natural k y un grafo G , ¿es (G)  k? (Problema NP-completo)

Matemática  Discreta

ALGORITMO VORAZ DE COLORACIÓN DE VÉRTICES:

Colorac ción de grafos e

Paso 1: Paso 2:

g Ordenar los vértices del grafo.

{ A,B,C,D,E,F,G,H }Comenzando con el primer vértice, y de forma ordenada, asignar a cada vértice el primer color no asignado a sus vértices adyacentes anteriores.

A( 1 )
( 4 )H

B( 2 ) C(2)

(2)G (1)F
Tema 6: 10

D( 1 ) E(3)

P.Reyes

Coloración de vértices
Calcular el número cromático de un grafo cualquiera es un “problema intratable”. Dado un número natural k y un grafo G , ¿es (G)  k?(Problema NP-completo)

Matemática  Discreta

ALGORITMO VORAZ DE COLORACIÓN DE VÉRTICES:

Colorac ción de grafos e

Paso 1: Paso 2:

g Ordenar los vértices del grafo.

{ G,H,E,D,B,A,C,F }

Comenzando con el primer vértice, y de forma ordenada, asignar a cada vértice el primer color no asignado a sus vértices adyacentes anteriores.

A( 1 )
( 4 )H

B( 2 )
( 2 )H

A( 2 )

B(1)...