Teoria De Grafos

ESTRUCTURA DE DATOS




Los grafos son estructuras de datos
Representan relaciones entre objetos
◦ Relaciones arbitrarias, es decir
◦ No jerárquicas



Son aplicables en
◦
◦
◦
◦

Dado un escenario
donde ciertos objetos
se relacionan, se
puede “modelar el
grafo” y luego aplicar
algoritmos para
resolver diversos
problemas

Impresora
PC1

Química
Modem
Geografía
Ing. Eléctrica e Industrial,etc.
Modelado de Redes
 De alcantarillado
 Eléctricas
 Etc.

Servidor

PC2

Oviedo

4

Zaragoza

3 95

32

3
19

Valladolid

29 6

1

0
15

Jaén
12
5

Cádiz

99

Sevilla

2
24
25 6

19 1

Valencia

241

3 35

Badajoz

25

Gerona

Barcelona

5

Madrid
3
40

0
10

34
9

Vigo

Bilbao

28
0

45
5
356

304

32

171

Coruña

278

Granada

Murcia



No hay restricciones para formar un grafo



Puedehaber varias aristas entre dos vértices



El vértice de partida y el de llegada puede ser
el mismo.–Las aristas pueden o no llevar
flechas.




Un grafo G = (V,A)
V, el conjunto de vértices o nodos

1

◦ Representan los objetos


A, el conjunto de arcos

4
5

7

◦ Representan las relaciones
V = {1, 4, 5, 7, 9}
A= {(1,4), (5,1), (7,9), (7,5), (4,9), (4,1), (1,5), (9,7), (5, 7), (9,4)}

9

C

E

◦ Si los pares de nodos tienen
un sentido.
◦ Existe un camino
preestablecido

F
D

Grafos dirigidos

H

V = {C, D, E, F, H}

1

A= {(C,D), (D,F), (E,H), (H,E), (E,C)}



4

5

Grafos no dirigidos


Si los pares de nodos no tienen un
sentido

7

9

Grafo del ejemplo anterior



Arista

◦ Es un arco de un grafo no dirigido



Vértices adyacente

◦ Vértices unidos por un arco



 Grafovalorado



Guayaquil

Ciclos

Quito
8

7

Factor de Peso

◦ Valor que se puede asociar con un
arco
◦ Depende de lo que el grafo
represente
◦ Si los arcos de un grafo tienen F.P.

9

Ambato
7

5

5

Riobamba

Cuenca



Grafo No Dirigido
◦ Conexo (enlazado)

9

 Existe un camino entre
cualquier par de nodos
4

2


8

5



B
D

Fuertemente Conexo


A

7

Grafo Dirigido

6

H

5

3



Existe uncamino entre cualquier par
de nodos

Conexo (débilmente enlazado)


Existe una cadena entre cualquier
par de nodos



C

En Grafo No Dirigido

E

◦ Grado(V)
 Numero de aristas que contiene a V

F
D

H

Grado(Guayaquil) = 3
9

Guayaquil

Gradoent(D) = 1 y Gradsal(D) = 1

Quito
8

7

Ambato
7

5

5

Riobamba

Cuenca



En Grafo Dirigido


Grado de entrada, Graden(V)




Numero de arcos quellegan a V

Grado de Salida, Gradsal(V)


Numero de arcos que salen de V



Definición

◦ Un camino P en un grafo G,
desde V0 a Vn
◦ Es la secuencia de n+1 vértices
◦ Tal que (Vi, Vi+1)  A para 0 i 
n
◦ Trayectoria de un punto a otro

A

B

C

D

E

F

Camino A y A
P = {A, E, B, F, A}
4

7
10
11



Longitud de camino


El número de arcos que lo
forman

6

9

Camino entre 4 y 7

P = {4, 6,9, 7}
Longitud: 3



E

Un trayectoria o recorrido es
una secuencia de nodos
w1,w2,…,wn tal que (wi,wi+1) 
E.

210


M
450
60

190

◦ Longitud: número de ramas en
el recorrido.

B
200

P

130

Un recorrido es una lista
ordenada de nodos.

L

◦ Costo o peso: suma de los
pesos de las ramas del
recorrido
◦ Ciclo: es un recorrido que
vuelve al nodo de partida.



Datos

◦ Vértices y
◦Arcos(relación entre vértices)



Operaciones

◦ void AñadirVertice(Grafo G, Vértice V)
 Añadir un nuevo vértice

◦ void BorrarVertice(Grafo G, Genérico clave)
 Eliminar un vértice existente

◦ void Union(Grafo G, Vertice V1, Vertice V2)
 Unir dos vértices

◦ Void BorrarArco(Grafo G, Vertice V1, Vertice
V2)
 Eliminar un Arco

◦ bool EsAdyacente(Grafo G, Vertice V1,
Vertice V2)
 Conocer si dos vérticesson o no adyacentes



Dos posibles representaciones
◦ Estática: Matriz de Adyacencia
 Los vértices se representan por indices(0…n)
 Las relaciones de los vértices se almacenan en una
Matriz

◦ Dinámica: Lista de Adyacencia
 Los vértices forman una lista
 Cada vértice tiene una lista para representar sus
relaciones(arcos)

Si el grafo fuese valorado, en vez
de 1, se coloca el factor de...