Introducci´on: grafos y digrafos

2.1 Introducci´on: grafos y digrafos

En t´erminos generales, un grafo consiste en un conjunto de puntos, que llamaremos v´ertices, y l´ıneas

que unen los v´ertices, que denominaremos aristas.

Los grafos se est´an convirtiendo en herramientas poderosas de m´ultiples disciplinas: ingenier´ıa

electrica y civil, redes de comunicaci´on, computaci´on, economia, sociolog´ıa, etc. Tanto por su simplicidad

como modelo de muy variadas situaciones, como secillez para dar soluci´on a los problemas, en

muchos casos en forma de algoritmos computables en ordenador.

Aparecen en diferentes campos bajo denominaciones distintas: “redes” en ingenier´ıa electrica,

“estructuras moleculares” en qu´ımica, “mapas de carreteras”, “sociogramas”, “redes de telecomunicaciones”,

etc. El modelado es simple tomando los objetos (lugares, aparatos, personas, . . . ) como

v´ertices y las conexiones (cables, relaciones, tratos, . . . ) como aristas.

Ejemplo 1.- En la ciudad de K¨onigsberg, existen siete puentes

que unen las riberas y dos islas formadas por el r´ıo Pregel,

de la forma que indica el dibujo. ¿Hay alguna forma de recorrer

los siete puentes y volver al punto de partida, sin cruzar

dos veces por el mismo puente?













s

s

s

s

%

$

El grafo que aparece sobre el dibujo modela esa situaci´on: cuatro puntos, que representan las

partes de tierra firme y las l´ıneas que los unen, representando los puentes. El problema se reduce a

saber si pueden recorrerse todas las l´ıneas sin repetir ninguna y acabar en el mismo punto.

Cuando se plante´o esa pregunta a Euler ingeni´o la teor´ıa de grafos y prob´o los primeros resultados

antes de dar su respuesta: no.

Definici´on 2.- Un grafo est´a formado por un par de conjuntos finitos, y se denota por G = (V,A),

donde V es el conjunto de v´ertices y A es el conjunto de aristas.

Cada arista de a 2 A conecta dos v´ertices de V , que llamaremos extremos de la arista, y escribiremos

a = {x, y} para indicar que a conecta o une los v´ertices x e y . Diremos entonces que x e y

son adyacentes por a.

En un grafo podemos encontrarnos lazos (aristas cuyos extremos coinciden), aristas m´ultiples (m´as

de una arista conectando los mismos v´ertices) y v´ertices aislados (no est´an conectados a ning´un otro

v´ertice).

Pero tambi´en podemos hablar de grafos dirigidos donde cada arista tiene una direcci´on de recorrido;

modelos para una distribuci´on de agua por la red de tuberias de la ciudad, la red viaria con calles de

sentido ´unico, etc., son ejemplos de grafos dirigidos.

...