grafos

OBJETIVOS
Definiciones formales de grafo y conceptos relacionados
Estructuras de datos para representar grafos
Algoritmos para resolver diferentes variantes del problema de
encontrar el camino mínimo sobre un grafo
Algoritmos para resolver el problema de encontrar el árbol de
extensión de coste mínimo sobre un grafo

Tema 9: GRAFOS
Primera Parte
Estructuras de Datos y Algoritmos
Curso2002/03

Grafos. EDA. Curso 2002/03

ÍNDICE

BIBLIOGRAFÍA

1. Introducción
2. Conceptos Básicos
3. Implementación de grafos
4. Recorridos de grafos
5. Búsqueda del camino con peso mínimo: algoritmo de Dijkstra
6. Otros problemas de caminos en GAD
Ordenación topológica
Búsqueda de caminos mínimos

7. Problema de obtención de árboles de extensión sobre grafos
no dirigidosAlgoritmos de Prim y Kruskal

Grafos. EDA. Curso 2002/03

2

Básica:
Weiss, M.A. Estructuras de datos en Java. Adisson-Wesley, 2000.
Capítulos 14 y 23

Otros:
T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms. MIT
Press, 1990.
Capítulos 5 y 23.

Aho A.V., Hopcroft J.E., Ullman J.E. Estructuras de datos y Algoritmos.
Addison-Wesley, 1988.
Capítulos 6 y 7.

3Grafos. EDA. Curso 2002/03

4

CONCEPTOS BÁSICOS

1. INTRODUCCIÓN
Un grafo permite representar relaciones binarias entre los
elementos de un conjunto.
Ejemplos:

Grafos dirigidos y no dirigidos
Grafos etiquetados
Relaciones de incidencia y adyacencia
Caminos
Subgrafos
Conectividad
Árboles y Grafos

•Rutas de transporte
•Envío de correo electrónico

25

18

35

30
2149
25

23
39

Grafos. EDA. Curso 2002/03

Grafos. EDA. Curso 2002/03

5

Grafos Dirigidos (DiGrafos)

Grafos no dirigidos

Un grafo dirigido (g.d.) es un par G=(V,E)

Un grafo no dirigido (G.N.D) es un par G=(V,E)

V es un conjunto finito de vértices (nodos)
E es un conjunto de arcos (o aristas). Un arco es un par
ordenado(u,v) con u,v∈V

1
4

2
5

3

V es unconjunto finito de vértices (nodos)
E es un conjunto de arcos (aristas). Un arco es un par NO ordenado
(u,v) con u,v∈V, u≠v

V={1,2,3,4,5,6}

6

E={(1,2),(2,2),(2,4),(2,5),(4,1),
(4,5),(5,4),(6,3)}

Grafos. EDA. Curso 2002/03

6

1

2

3

V={1,2,3,4,5,6}
E={(1,2),(1,5),(2,5),(3,6)}

4

7

5

6
Grafos. EDA. Curso 2002/03

8

Grafos Etiquetados

Relaciones deIncidencia y Adyacencia

Un grafo etiquetado es un grafo G=(V,E) sobre el que se define
una función f:E->A, dónde A es un conjunto cuyas componentes
se llaman etiquetas.
Un grafo ponderado (o con pesos o costes) es un grafo
etiquetado con números reales (A≡ℜ)

Sea G=(V,E) un grafo dirigido. Si (u,v)∈E, decimos que incide
desde u (sale de..) e incide en v (llega a..).
Ejemplo: vértice 2

13

4

Grafos. EDA. Curso 2002/03

2
5

6

Grafos. EDA. Curso 2002/03

9

Relaciones de Incidencia y Adyacencia (cont.)

10

Relaciones de Incidencia y Adyacencia (cont.)

Sea G=(V,E) un grafo no dirigido. Si (u,v)∈E, decimos que incide
sobre u y v.
Ejemplo: vértice 2

Sea G=(V,E) un grafo. Si (u,v)∈E, decimos que el vértice v es
adyacente al u.
La relación es simétricaen grafos no dirigidos

2 es adyacente a 1
1 NO es adyacente a 2

2 es adyacente a 1
1 es adyacente a 2

1

2

3

1

2

3

1

2

3

4

5

6

4

5

6

4

5

6

Grafos. EDA. Curso 2002/03

11

Grafos. EDA. Curso 2002/03

12

Relaciones de Incidencia y Adyacencia (cont.)

Relaciones de Incidencia y Adyacencia (cont.)

Llamaremos grado de unvértice en un g.n.d. al nº de arcos que
inciden sobre él.

El grado de un vértice en un g.d. es el nº de arcos que salen de
él (grado de salida) más el nº de arcos que entran (grado de
entrada).

1

2

3

4

5

6

1

13

3

4

5

6

Grafos. EDA. Curso 2002/03

14

Caminos
Un camino de longitud k desde u a u’ en un grafo G=(V,E) es
una secuencia de vértices...