estudiante

Grado en Gestión Informática Empresarial
Matemáticas Básicas

3.3 Coloreado de vértices. Algoritmo voraz de
coloreado.

Tema 3: Grafos y árboles

Grado en Gestión Informática EmpresarialDefinición
D fi i ió
 Definición: Sea G = (V,E) un grafo. Un “coloreado de vértices” de G
con “ l
“colores” d un conjunto fi it C es cualquier f
” de
j t finito
l i función c : V -> C
ió
talque
si x y vecinos entonces c(x)  c(y)
x,
• marcamos los vértices del grafo
• vértices vecinos con marcas distintas

 Ejemplo: Coloreado de mapas

a

a
d

e

h

Matemáticas Básicas– Tema 3 – Sección 3.3

g

c

b

c

b

e

f

f
d
i

g
h

i
2

Grado en Gestión Informática Empresarial

 Ejemplo: Asignación de horarios
• Problema: asignación de horariosa 6 cursos c1, c2, c3, c4, c5, c6, de
modo que cursos con alumnos comunes no compartan horario.
• Comparten alumnos: c1 y c2, c1 y c4, c1 y c6, c2 y c6, c3 y c5, c4 y c5, c5 y
c 6.

 G fGrafo:
• vértices = {c1, c2, c3, c4, c5, c6}
•

arista de x a y = “x comparte alumnos con y”
x
y

c4 H2

H1 c1

H2
c3

H1

c5 H
3

c6 H
4

c2

3

Matemáticas Básicas – Tema 3 –Sección 3.3

Grado en Gestión Informática Empresarial

 ¿Podemos colorear el grafo con menos colores?
 Definición: El “número cromático” de un grafo G = (V,E) es el
menor número matural k talque puede colorearse con k colores.
 Número crómatico de G = χ (G)
 Ejemplo:
c4 H2

H1 c1

H2
c3

H2
c5 H
1

c6 H
3

χ (G)) = 3
(

c2

– triángulo a la dcha: no se puedecolorear con dos colores

Matemáticas Básicas – Tema 3 – Sección 3.3

4

Grado en Gestión Informática Empresarial

 Ejemplos:

1

2

2

2

1

3

3

2

2
1

2

1

2

2χ (G) = 3

2

2

3

3

2

1

2

2

– Si Kn grafo completo con n vértices:

χ (G) = 2

2

1

χ (K ) = n
n

Matemáticas Básicas – Tema 3 – Sección 3.3

5

Grado en...