Tecnico

Cap´ ıtulo 8

Grafos
8.1. ¿Qu´ es un grafo? e

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: 1. 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 cadatrabajador 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 Construcci´n de redes: tenemos una serie de ciudades que queremos conectar meo diante un oleoducto; un estudio de ingenier´ previo nos permite conocer el precio de ıa cada conexi´n. Se trata de conectar todaslas ciudades con el menor coste posible. o 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 para programar todas las asignaturas salvando esa dificultad; o bien determinar cu´les son losposibles horarios si el n´mero de horas disponible es fijo. a u

2.

3.

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 grafo es una colecci´n de v´rtices y de aristas que unen estos v´rtio e e ces. Losv´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. Una arista de G es, ı o pues, un subconjunto {a, b}, con a, b ∈ V , a = b. 555

Ve rs i´n o

preli m in ar

556

Cap´ ıtulo 8. Grafos

Ejemplo 8.1.1 Traducimos al lenguaje de grafos los problemas enunciados anteriormente: 1. 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, generalmente se dibujan los v´rtices correspondientes a las tareas a unlado 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 Para el problema de la construcci´n de la red, las ciudades ser´n los v´rtices y las 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. 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 falta u ver un ingrediente: c´mo se colorea un grafo. En este caso, los colores ser´n las horas o ade que dispongamos. Pero esto lo veremos m´s adelante. a ♣

2.

3.

Ve rs i´n o
G1
2

Ejemplo 8.1.2 Consideremos un conjunto de v´rtices V = {1, 2, 3}. Construyamos algunos e e grafos distintos con ese conjunto de v´rtices.

Los subconjuntos de dos elementos de V son {1, 2}, {1, 3} y {2, 3}. Dos elecciones distintas de conjunto de aristas son A1 = {{1, 2}, {2, 3}} y A2 = {{1, 2}}, quedan lugar a los grafos G1 y G2 que dibujamos a continuaci´n: o ◦ G2
1 2

1

◦

pr eli m in ar
◦
3 3

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