ED cosa tema 8

Índice
8.1 Introducción
8.2 Grafos. Especificación
8.3 Grafos. Posibles Implementaciones
8.4 Recorridos sobre Grafos.
8.5 Algoritmos sobre Grafos.

Tema 8: Grafos
Estructuras de Datos
Grado en Ingeniería de Computadores
Universidad Rey Juan Carlos
José Miguel Buenaposada Biencinto

Agradecimientos: a Ana Pradera y Juan Manuel Serrano por el planteamiento del curso ☺.
URJC-ED-GrafosReferencias

2

Motivación
redes de transporte
metro de madrid

•

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to
Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.
– Capítulo 22 (secciones 1,2,3), pp. 527–549.
– Ref. Biblioteca: 519.712 INT TOA

•

Allen B. Tucker (ed.). Computer science handbook, Chapman & Hall/CRC,
2004.
– Capítulo 7(secciones 1,2,3,4)
– Ref. Biblioteca: 004 COM SCI

•

WIKIPEDIA
– http://en.wikipedia.org/wiki/Graph_%28data_structure%29

•

Dictionary of Algorithms and Data Structures
– http://www.nist.gov/dads/HTML/graph.html
URJC-ED-Grafos

3

URJC-ED-Grafos

4

Motivación

Motivación

Estructuras moleculares

Redes
sociales
colaboraciones
científicas

Más ejemplos en:http://www.aisee.com
URJC-ED-Grafos

5

Motivación

URJC-ED-Grafos

6

Definiciones

Redes de
comunicaciones
World Wide Web

• Un grafo G es un par (V,E) formado por un conjunto V
de vértices o nodos y un conjunto E de pares no
ordenados de vértices distintos denominados arcos
• Un grafo dirigido o digrafo es un grafo cuyos arcos
consisten en pares ordenados de vértices, E⊆VxV
•Un pseudografo es un grafo en el que se permite que
los vértices de los arcos sean iguales
• Un multigrafo es un grafo cuya colección de arcos
consiste en una bolsa (es decir, en un multigrafo se
permite que haya más de una ocurrencia del mismo arco
entre un par de vértices).
• Un grafo valorado es un grafo cuyos arcos tienen
asociado un número real denominado coste del arco,
G=(V,E,E→R)URJC-ED-Grafos

7

URJC-ED-Grafos

8

Definiciones

Definiciones
grafo

Grafo

pseudo-grafo

multi-grafo

(conjunto de arcos, pares no ordenados, vértices distintos)

b
c

Grafo dirigido

Multigrafo

Pseudografo

(bolsa de arcos)

(vértices iguales permitidos)

(arcos con coste)

a

d

c

Multi-pseudo grafo dirigido valorado

URJC-ED-Grafospseudo-multi digrafo valorado
b

2.0

c
0.0

1.0

2.0

a

d

a

d

URJC-ED-Grafos

9

Definiciones

b
3.0

1.0

a

10

Definiciones

• Un grafo (V,E) de n vértices, |V|=n, se dice completo si
|E|=n*(n-1)/2.
• Un grafo (V,E) se denomina disperso si |E| TipoGrafo

• InsertarNodo: commutatividad
g1=InsertarNodo(InsertarNodo(g,n1),n2) =InsertarNodo(InsertarNodo(g,n2),n1)

g1
n1
n2

• InsertarNodo: idempotencia
g0: TipoGrafo

g1: TipoGrafo

g2=InsertarNodo(InsertarNodo(g,n),n) =
InsertarNodo(g,n)

g2: TipoGrafo
n4

c

n3
n2
g0=CrearGrafoVacio

g1=InsertarNodo(g0,n2)

URJC-ED-Grafos

n2

g2

g2=InsertarArco(g1,CrearArco(n3,n4,c))

23

n

URJC-ED-Grafos

24

Operaciones sobre Grafos

Operaciones sobre Grafos

•InsertarArco: conmutatividad

• InsertarArco/Nodo: conmutatividad

g1
a1:TipoArco

g1=InsertarArco(InsertarArco(g,a1),a2) =
SI NO ExtremosIguales(a1,a2) ->
InsertarArco(InsertarArco(g,a2),a1)

g1
a

g1=InsertarArco(InsertarNodo(g,n),a) =
InsertarNodo(InsertarArco(g,a),n)
n

a2:TipoArco

• InsertarArco: no idempotencia

• InsertarArco: inserción de nodos implícitag2=InsertarArco(InsertarArco(g,a1),a2) =
SI ExtremosIguales(a1,a2) ->
InsertarArco(g,a2)

g2=InsertarArco(g,CrearArco(n1,n2,c))=
InsertarArco(InsertarNodo(InsertarNodo(g,n1),n2),
CrearArco(n1,n2,c)))

g2=ia(g,ca(n1,n2,c2))

g

g1
n1

....

g2

g2

c1

n1

c2

n2

c

n1

n2

n2

g2=ia(g1,ca(n1,n2,c2))

g1=ia(g,ca(n1,n2,c1))
URJC-ED-Grafos

URJC-ED-Grafos

25...