Grafos

1 – Laboratorio de Matem´ticas : Teor´ de Grafos a ıa

Cap´ ıtulo 1

Teor´ de Grafos ıa
1.1 Introducci´n: grafos y digrafos o

En t´rminos sencillos, un grafo consiste en un conjunto de puntos, que llamaremos v´rtices, y l´ e e ıneas que unen o relacionan pares de v´rtices, que denominaremos aristas. e Los grafos se est´n convirtiendo en herramientas poderosas de m´ltiples disciplinas:ingenier´ electrica a u ıa y civil, redes de comunicaci´n, computaci´n, economia, sociolog´ etc. Tanto por su simplicidad como o o ıa, modelo de muy variadas situaciones, como secillez para dar soluci´n a los problemas, en muchos casos en o forma de algoritmos computables en ordenador. Aparecen en diferentes campos bajo denominaciones distintas: “redes” en ingenier´ electrica, “esıa tructurasmoleculares” en qu´ ımica, “mapas de carreteras”, “sociogramas”, “redes de telecomunicaciones”, etc. El modelado es simple tomando los objetos (lugares, aparatos, personas, . . . ) como v´rtices y las e conexiones (cables, relaciones, tratos, . . . ) como aristas. Ejemplo 1.- En la ciudad de K¨nigsberg, existen siete puentes o que unen las riberas y dos islas formadas por el r´ Pregel, de la ıo forma queindica 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´n: cuatro puntos, que representan las partes de o tierra firme y las l´ ıneas que los unen, representando los puentes. El problema se reduce a saber si pueden recorrersetodas las l´ ıneas sin repetir ninguna y acabar en el mismo punto. Cuando se plante´ esa pregunta a Euler ingeni´ la teor´ de grafos y prob´ los primeros resultados antes o o ıa o de dar su respuesta: no. Definici´n 2.- Un grafo est´ formado por un par de conjuntos finitos, y se denota por G = (V, A), o a donde V es el conjunto de v´rtices y A es el conjunto de aristas. e Cada arista de a ∈ A conectados v´rtices de V , que llamaremos extremos de la arista, y escribiremos e a = {x, y} para indicar que a conecta o une los v´rtices x e y . Diremos entonces que x e y son e adyacentes por a. En un grafo podemos encontrarnos lazos (aristas cuyos extremos coinciden (en rojo en la figura, va de v3 a v3 ), aristas m´ltiples (m´s de una arista conectando los mismos v´rtices u a e (arista de v1 a v6 , endorado)) y v´rtices aislados (no est´n e a conectados a ning´n otro v´rtice ( v7 en la figura)). u e v6
t tv7 t v3 t

v1 t v4
t

t

v2 v5

Pero tambi´n podemos hablar de grafos dirigidos donde cada arista tiene una direcci´n de recorrido; e o modelos para una distribuci´n de agua por la red de tuberias de la ciudad, la red viaria con calles de sentido o unico, etc., son ejemplos de grafosdirigidos. ´

Prof: Jos´ Antonio Abia Vian e

I.T.I. en Electricidad

2 – Matem´ticas I : Teor´ de Grafos a ıa

1.1 Introducci´n: grafos y digrafos o

Definici´n 3.- Un digrafo o grafo dirigido est´ formado por un par de conjuntos finitos, y lo denotaremos o a por D = (V, A), donde V es el conjunto de v´rtices y A es el conjunto de arcos o aristas dirigidas e entre los v´rtices. e Cadaarco a ∈ A conecta dos v´rtices de V , que llamaremos respectivamente extremo inicial y extremo e final del arco, y escribiremos a = (x, y) para indicar que a conecta o une el v´rtice x con el v´rtice y . e e Diremos tambi´n que x es adyacente a y y que a incide en y . e Si los grafos se representan con puntos y l´ ıneas que los unen, los digrafos se representan con puntos y flechas entre ellos.Desgraciadamente no hay una nomenclatura est´ndar para designar los tipos a de grafos ni los elementos que aparecen, por lo que es preciso fijarla y tenerlo presente al consultar cualquier bibliograf´ sobre el tema. ıa
t   cT     t   ' c t Et     

En una primera clasificaci´n en grandes bloques, los grafos se distinguen por ser dirigidos o no, y por o tener o no aristas/arcos m´ltiples y lazos....