Tema VI: Introducción
Grafos
Introducción
Ciudad B
Ciudad A Ciudad D
Ciudad C
Ciudad F
Ciudad E
Caminos entre ciudades
Introducción
En ocasiones, incluso, se requiere tener acceso a un
nodo determinado a partir de más de un nodo de la
estructura. Existen varios caminos entre un nodo y
otro.
Ejemplo:
• Una red hidráulica,
• Caminos entre ciudades,
• Afinidad entre miembros de un colectivo, entre
otros.
Grafos
Un grafo (en inglés graph) es un conjunto finito N de
nodos, llamados vértices, relacionados entre sí por
un conjunto R de arcos.
Grafo con 5 vértices y 6 arcos. A
B
• Vértices del Grafo
N ={ A, B, C, D, E } C
D
E
• Arcos del Grafo
R={(A, A), (A, B), (A, D), (A, C), (D, C), (C, E)}
Grafos: Aclaraciones
•Si el conjunto N es vacío, el grafo será vacío.
• Cada arco de un grafo establece una única relación
entre dos nodos.
• No existe restricción en la relación que establece
un arco, o sea, un nodo puede estar relacionado
consigo mismo o con otro nodo.
• Cada arco se representa a través de un par, donde
cada elemento determina uno de los nodos.
Observación
Dado que no hay restricciones en cuanto a los arcos
de un grafo, todas las estructuras vistas con
anterioridad pueden ser consideradas como un
grafo.
Ejemplo, una lista lineal puede ser vista como un
grafo donde cada nodo está relacionado con
exactamente un nodo distinto de él.
Clasificación de los Grafos
Un grafo es no orientado o no dirigido (en inglés
not directed o not oriented graph) si el hecho de
que el arco (Nj, Nk) pertenezca a R implica que el
arco (Nk, Nj) pertenece a R, para todo j y k.
• Es irrelevante el sentido de las saetas en los arcos
• Al representarlos, los arcos se grafican sin saeta.
• El arco que los relaciona aparece una sola vez en
el conjunto R de arcos del grafo.
Si el grafo es no orientado, al arco se le llama arista.
Clasificación de los Grafos
Un grafo es orientado o dirigido (en inglés:
oriented graph o directed graph) si el hecho de
que el arco (Nj, Nk) pertenezca a R no implica que el
arco (Nk, Nj) pertenece también a R, para todo j y k.
• El sentido de las saetas en los arcos es importante.
• Es importante la dirección del arco, o sea, el nodo
origen del arco y el nodo destino.
• El hecho que exista un arco de Nj a Nk no implica
que exista de Nk a Nj.
Se conocen como digrafos (en inglés: digraph).
Clasificación de los Grafos
A A
B B
C C
D D
E E
Grafo No Orientado Grafo Orientado o
o No Dirigido Dirigido
Adyacencia
El nodo n es adyacente al m, si existe un arco o
arista de m a n.
Adyacencia:
A • B es adyacente a A
B
• D es adyacente a A
C
D • C es adyacente a A
E
• A es adyacente a A
• C es adyacente a D
• E es adyacente a C
Incidencia
El vértice n es incidente al arco o arista x, si n es
uno de los vértices relacionados con el arco o arista
x. Del mismo modo, se dice que el arco o arista x es
incidente al vértice n.
.
Así, todos los arcos que llegan o salen de un nodo
son incidentes a él
A Incidencia:
B
• B es incidente al arco (A,B)
C
D • (A,B) es incidente a B
E
Grado de un Vértice
El grado de un vértice n es el número de arcos
incidentes a él.
En el caso de los grafos orientados, el grado de
entrada de un vértice n es el número de arcos que
llegan a él y el grado de salida de un vértice n es el
número de arcos que salen de él.
Por lo tanto, el grado de un vértice es la suma de
los grados de entrada y de salida del vértice.
Grado de un Vértice
Sobre el Nodo D:
A B • Grado de Entrada: 3
D • Grado de Salida: 2
C F
• Grado del Nodo: 5
E
Ponderando arcos y vértices
En muchas aplicaciones resulta de interés asignar
valores de ponderación, también llamados pesos,
a los arcos o a los vértices, obteniéndose así:
• Grafos ponderados por los arcos
• Grafos ponderados por los vértices
Ejemplo: Grafo ponderado por los arcos
Problema del agente viajero
Un agente necesita repartir paquetes en diferentes
ciudades. Se sabe en qué ciudades el agente debe
repartir los paquetes, así como la distancia entre
cada ciudad y las otras.
El problema consiste en saber cuál es la mejor ruta a
seguir por el agente para repartir todos los paquetes.
Ejemplo: Grafo ponderado por los arcos
El problema se puede modelar con un grafo, donde:
• Las ciudades son vértices.
• Los caminos entre las ciudades son arcos.
Si para todas las ciudades se cumple que la
distancia entre una ciudad origen y una ciudad
destino y la distancia de la ciudad destino a la ciudad
origen es la misma, entonces, se puede utilizar un
grafo no orientado.
Podemos ponderar los arcos con la distancia que
existe entre las ciudades.
Ejemplo: Grafo ponderado por los arcos
El agente debe visitar tres ciudades A, B y C,
partiendo de la ciudad A. Entre las ciudades A y B
hay 50 km, entre las ciudades B y C hay 20 km y
entre las ciudades A y C hay 15 km.
50 Km
A B
Caminos:
C A-B-C: 70 Km
A-C-B: 35 Km
El camino más corto es de A a C y de C a B.
Ejemplo: Grafo ponderado por los vértices
Se tiene una secuencia de actividades, de las que se
conoce su duración y se quiere saber, en un
momento dado, en qué orden debieran realizarse, de
forma tal que se realicen primero las de menor
duración.
• Las actividades se pueden representar por los
vértices de un grafo no orientado.
• En cada vértice se puede almacenar la duración de
la actividad como factor de ponderación.
Ejemplo: Grafo ponderado por los vértices
A B
10 25
C
20
Resulta más conveniente realizar la actividad A,
luego la C y, por último, la B.
Camino entre nodos
Existe un camino de longitud k desde el nodo A al
B, si existe una secuencia de k+1 nodos n1, n2, ...,
nk+1, donde n1 = A, nk+1 = B y (ni, ni+1) son
adyacentes para todo i entre 1 y k.
En un grafo no orientado, al camino se le llama
cadena.
Caminos entre los nodos A y C:
A Camino de longitud 1: (A,C)
B
Camino de longitud 2: (A,D,C)
C
D Camino de longitud 2: (A,A,C)
E
Camino de longitud 3: (A,A,D,C)
Ejemplo: Camino entre nodos
¿Existe un camino de longitud mayor que 1 entre los
nodos C y D?
A
B
C
D
• Camino de longitud 3: (C, B, A, B)
• Camino de longitud 4: (C, B, A, C, B)
• Camino de longitud 5: (C, B, A, B, A, B)
Camino simple
Entre dos nodos existe un camino simple si todos
los vértices, excepto posiblemente el primero y el
último, son distintos dos a dos.
O sea, un camino simple es aquel en el que no se
repiten los arcos.
Ejemplo:
A (A, B, D)
B
(A, B, A, C)
C
D
Camino simple
Un ciclo, o también circuito, es un camino simple
de cualquier longitud de un nodo a sí mismo. Si el
ciclo es de longitud 1, entonces se denomina bucle o
lazo.
A Ejemplo:
B
Ciclo: A,D,C,A
Bucle: A,A
C
D
E
Grafo cíclico y acíclico
Si un grafo contiene al menos un ciclo se llama
cíclico.
Un grafo acíclico es aquel que no tiene ningún
circuito o ciclo.
A A
B B
C C
D D
E
Grafo cíclico Grafo acíclico
Operaciones sobre Grafos
• Construir un grafo dada la información de sus
vértices. (Convenio: se crea inicialmente vacío).
• Verificar si un grafo está vacío o no.
• Insertar vértices y arcos.
• Eliminar vértices y arcos.
• Dados dos vértices, determinar si son adyacentes.
• Dado un vértice, determinar cuáles vértices son
adyacentes a él.
Operaciones sobre Grafos
• Dados dos vértices, determinar un camino de
longitud k entre ellos.
• Dado un arco, determinar vértices incidentes a él.
• Determinar si el grafo es cíclico.
Representación matricial de Grafos
• La representación matricial permite establecer si
hay relación entre cada vértice del grafo y los
demás.
• Para ello, se utiliza una matriz cuadrada.
• Se utiliza un arreglo bidimensional.
• Esto significa que la representación matricial es
una representación secuencial.
Representación matricial de Grafos
B A
C
D
A partir de un grafo, siempre es posible definir un
orden arbitrario de los nodos.
A B C D E
0 1 2 3 4
Matriz de Adyacencia
La matriz de adyacencia representa para cada
nodo cuáles son sus vértices adyacentes.
• Cada fila y cada columna de la matriz se
corresponde con un vértice en particular.
• Los elementos de la matriz son booleanos
• Si el elemento (i, j) es verdadero, existe un arco
que va del vértice i al vértice j y, si el elemento (i, j)
es falso, no existe arco del vértice i al vértice j.
• Si el grafo es no orientado, si existe el arco del
vértice i al vértice j existe el arco del vértice j al
vértice i.
Representación matricial de Grafos
Vértices
B A A B C D E
0 1 2 3 4
C
D A B C D E
A 0 0 1 1 0
E
B 0 0 1 0 0
Matriz de Adyacencia C 0 0 0 1 1
D 0 0 0 0 1
E 0 0 0 1 0
Ejemplos de matriz de adyacencia
3 1 3 2
1 1 2
5 4 5
1 6
2 2 2 1
4 3 4
0 1 0 0 0 0 1 0 0 0
0 1 1 1 0 0 2 0 0
0 0 1 0 0
1 0 0 1 0 6 0 0 2
0 1 0 0 1
1 0 0 0 0 0 0 0 0
0 0 0 0 0
1 1 0 0 0 0 0 1 0
0 0 0 1 0
Problemas
La representación de la matriz de adyacencia de
un grafo exige conocer por adelantado la cantidad
de nodos del grafo.
Esta representación no es suficientemente flexible
cuando la cantidad de vértices varía con relativa
frecuencia o cuando la estructura del grafo cambia
durante la ejecución de la aplicación que lo usa.
Esto implica crear la matriz cada vez que se inserte
o elimine un nuevo nodo.
Problema: Solución costosa en tiempo y recursos.
Representación enlazada de Grafos
Problemas B A
Variante 1:
• Es difícil saber cuántos arcos
llegan
Una a de
lista un vértices
nodo y cada uno tiene C
• Selista
repite D
una de la
losinformación del
vértices adyacentes a él.
vértice
E
A C D • Las listas pueden ser
B C indistintamente secuenciales o
enlazadas o una combinación.
C D E
• El grafo está vacío si no
D E existen vértices.
E D
Representación enlazada de Grafos
Variante 2: Representación multienlazada
• Cada vértice se representa a través de un nodo que
contiene:
• Apuntador a su información,
• Apuntador a una lista de arcos
• Apuntador al siguiente vértice en la lista
•Cada arco se representa por un nodo que contiene:
• Apuntador al próximo arco de su vértice origen
• Apuntador al nodo de su vértice destino
Representación enlazada de Grafos
Variante 2: Representación multienlazada
• El grafo está vacío si no hay B A
vértices.
C
D
A B C D E E