Grafos

Pablo Rojas V.

¿Qué es un Grafo?

• Un grafo es un conjunto de nodos o vértices (V) y

un conjunto de aristas (E) donde cada arista crean

las relaciones entre nodos pertenecientes a V.

Los grafos se clasifican en 2:

1. Grafos dirigidos

2. Grafos no dirigidos

Grafo Dirigido

• Sea un grafo dirigido (G) donde un conjunto de

vértices corresponde a (V) y un conjunto de aristas

a (E).

• Los enlaces de un grafo dirigido se realizan solo en

una dirección entre vértices.

Ejemplo: Si se tiene un vértice A y un vértice B, el

enlace puede realizarse solo de A a B o de B a A, pero

no en ambas direcciones.

A B

Grafo Dirigido

• Los vértices pueden utilizarse para representar

objetos y los enlaces representar a las relaciones

entre ellos, por ejemplo, los vértices podrían

representar ciudades y los enlaces las autopistas

que las conectan.

• Un enlace es un par ordenado de vértices (V, W),

donde V es la cola y W corresponde a la cabeza del

enlace.

V W

Ejemplo Grafo Dirigido

A D

F J

V= {a, d, f, j}

E= {(a,f), (a,d), (d,f), (d,j), (f,j)}

Grafo No Dirigido

• Sea un grafo no dirigido (G) donde un conjunto de vértices

corresponde a (V) y un conjunto de aristas a (E).

• La diferencia del grafo dirigido es que el enlace de un grafo

NO dirigido entre 2 vértices es en ambas direcciones.

• Ejemplo: Si se tiene un vértice A y un vértice B el enlace se

realiza de A a B y de B a A.

A B

Un Grafo no Dirigido se diferencia de un Grafo Dirigido debido a que cada

arista en E es un par no ordenado de vértices.

Si (V,W) es una arista no dirigida –> (V,W) = (W,V).

Ejemplo Grafo No Dirigido

A D

F J

V={a, d, f, j}

E={(a,f), (f,a), (a,d), (d,a), (d,f), (f,d), (d,j), (j,d),

(f,j), (j,f)}

25 25

Costos

• Los enlaces tanto para los grafos dirigidos como no

dirigidos tienen un costos (valor), por lo tanto son

grafos etiquetados.

A

50

30

35

D

40

A

50

30

35

D

40

F J

Grafo dirigido

etiquetado

F J

Grafo No dirigido

etiquetado

Fin