Grafos

Grafos
8.1.

¿Qu´ es un grafo?
e

pr
eli
m
in
ar

Cap´
ıtulo 8

Los grafos, los objetos que estudiaremos en ´ste y los siguientes cap´
e
ıtulos, resultan ser
extremadamente utiles para analizar problemas muy diversos como, por ejemplo, los siguien´
tes:
Problemas de asignaci´n de tareas: tenemos un conjunto de trabajadores y otro de
o
tareas y la informaci´n de para qu´tareas est´ preparado cada trabajador y buscamos
o
e
a
una asignaci´n de tareas (a cada trabajador, una tarea distinta para la que est´ prepao
e
rado) de forma que consigamos ocupar al mayor n´mero de trabajadores posible.
u

Ve
rs
i´n
o

1.

2.

Construcci´n de redes: tenemos una serie de ciudades que queremos conectar meo
diante un oleoducto; un estudio de ingenier´ previo nospermite conocer el precio de
ıa
cada conexi´n. Se trata de conectar todas las ciudades con el menor coste posible.
o

3.

Problema de horarios: en una cierta licenciatura de una Universidad se deben impartir 10 asignaturas, y no se pueden programar a la misma hora dos asignaturas si
hay alg´n alumno matriculado en ambas. Lo que se busca es minimizar el n´mero de
u
u
horas necesario paraprogramar todas las asignaturas salvando esa dificultad; o bien
determinar cu´les son los posibles horarios si el n´mero de horas disponible es fijo.
a
u

Los grafos son, como veremos, un lenguaje, una notaci´n, que
o
permite representar relaciones binarias —es decir, entre pares de objetos— en un conjunto (recordemos la secci´n 3.5).
o
De una manera informal, podr´
ıamos decir que un grafoes
una colecci´n de v´rtices y de aristas que unen estos v´rtio
e
e
ces. Los v´rtices los dibujaremos como puntos del plano, y las aristas ser´n l´
e
a ıneas que unen
estos puntos. Vayamos con las definiciones formales:
Definici´n 8.1 Un grafo G es un conjunto no vac´ V (de v´rtices) y un conjunto A (de
o
ıo
e
aristas) extra´do de la colecci´n de subconjuntos de dos elementos de V. Unaarista de G es,
ı
o
pues, un subconjunto {a, b}, con a, b ∈ V , a = b.
555

Cap´
ıtulo 8. Grafos

556

pr
eli
m
in
ar

Para ser precisos, deber´
ıamos decir que esta definici´n se refiere a lo que se conoce como
o
un grafo simple y sin lazos. En la subsecci´n 8.1.1 presentaremos varias generalizaciones
o
de este concepto, que resultar´n muy utiles para otras cuestiones.Mientras no se diga lo
a
´
contrario, cuando hablemos de un grafo siempre estaremos refiri´ndonos a este caso sencillo.
e
Por supuesto, diremos que dos grafos son iguales si tienen el mismo conjunto de v´rtices y la
e
misma colecci´n de aristas. Nombraremos un grafo G mediante G = (V, A). A veces, cuando
o
manejemos varios grafos a la vez, utilizaremos s´
ımbolos como V (G) y A(G) para recordara
qu´ grafo corresponden los conjuntos de v´rtices y aristas a las que nos estamos refiriendo.
e
e
Ejemplo 8.1.1 Traducimos al lenguaje de grafos los problemas enunciados anteriormente:
El problema de la asignaci´n de tareas tiene una traducci´n inmediata: los v´rtices
o
o
e
estar´n etiquetados con los nombres de los trabajadores y de las tareas (en este tipo de
a
problemas, generalmentese dibujan los v´rtices correspondientes a las tareas a un lado
e
y los correspondientes a los trabajadores, a otro). Y dibujaremos una arista entre un
v´rtice que represente a un trabajador y otro que represente a una tarea si efectivamente
e
el trabajador est´ preparado para realizar dicha tarea.
a

2.

Para el problema de la construcci´n de la red, las ciudades ser´n los v´rtices ylas
o
a
e
conexiones, las aristas. Y, por supuesto, lo que buscaremos ser´ unir todos los v´rtices
a
e
con el menor n´mero posible de aristas y de manera que la red resultante sea lo m´s
u
a
barata posible.

3.

En el problema de horarios, representaremos las asignaturas con los v´rtices y las ine
compatibilidades entre asignaturas, con aristas. Para abordar el problema, a´n nos...