10
2 1 2
2 b d 45 20
3
55
s 4 40 25
1 t 30
5 3
3 25
3 2
a c 50 15
4
Grafos
Grafos 1
Indice general
1. Introducción.
2. Definiciones y representación.
3. Recorridos en grafos.
4. Algoritmos de caminos más cortos.
5. Árbol de cubrimiento de costo mínimo.
6. Flujo en redes. Flujo máximo.
Grafos 2
Indice
Introducción.
Definiciones.
Tipo de dato abstracto grafo.
Estructuras de datos para grafos.
– Lista de aristas.
– Lista de adyacencia.
– Matriz de adyacencia.
Grafos 3
Introducción
Los grafos se usan para modelar
problemas definidos en términos de
relaciones o conexiones entre objetos.
Tienen un amplio uso en ingeniería para
representar redes de todo tipo:
– transporte (tren, carretera, avión),
– servicios (comunicación, eléctrica, gas,
agua),
– de actividades en el planeamiento de
proyectos, etc.
Grafos 4
¿Qué es un grafo?
Un grafo G = (V, E) está compuesto de:
V : conjunto de vértices o nodos
E : conjunto de aristas o arcos que
conectan los vértices en V
Una arista e = (v, w) es un par de vértices
Ejemplo:
a b V = { a, b, c, d, e}
c E = { (a, b), (a, c), (a,d),
(b, e), (c, d), (c, e),
d e (d, e) }
Grafos 5
Aplicaciones
Grafo de transiciones (AFD) Tiempo de vuelos aéreos
b 2 2
b Santander Barcelona
Coruña
2 1
inicio a b b 1
0 1 2 3 Madrid
a 4
2 2
3 Valencia
a a Sevilla
Planificación de tareas Grafo asociado a un dibujo de líneas
(Pert/CPM) (visión artificial)
D(2)
inicio A(3)
I(1) C(4) E(3) final
B(2)
Grafos 6
Definiciones
Arista dirigida: par ordenado (u, v)
u v
Arista no dirigida: par no ordenado (u, v)
u v
Grafo dirigido o digrafo: grafo cuyas aristas son
todas dirigidas.
Grafo no dirigido o grafo: grafo cuyas aristas son
todas no dirigidas.
Grafo mixto: grafo con aristas dirigidas y no
dirigidas.
Grafos 7
Definiciones
Vértices finales o extremos de la arista: vértices unidos por una
arista.
– Vértice origen: primer vértice de una arista dirigida.
– Vértice destino: segundo vértice de una arista dirigida.
Arista incidente en un vértice: si el vértice es uno de los vértices de
la arista.
Aristas salientes de un vértice: aristas dirigidas cuyo origen es ese
vértice.
Aristas entrantes de un vértice: aristas dirigidas cuyo destino es ese
vértice.
a b
Grafos 8
Definiciones
Vértices adyacentes: vértices finales de una
arista.
– Un vértice w es adyacente a v sí y sólo si (v, w)
(ó (w, v)) pertenece a E.
– En grafos no dirigidos la relación de adyacencia es
simétrica.
– En grafos dirigidos la relación de adyacencia no es
simétrica.
a b Vértices adyacentes:
a = { b, c, d }
b={e}
c c = { a, d, e }
d = { a, c }
d e e={d}
Grafos 9
Definiciones
Grado de un vértice v (grado(v)) en un grafo:
número de aristas incidentes en v o número de
vértices adyacentes.
– En un digrafo:
• Grado entrante de un vértice v (graent(v)): número de aristas
entrantes a v.
• Grado saliente de un vértice v (grasal(v)): número de aristas
salientes de v.
– Si G es un grafo con m aristas, entonces
– Si G es un digrafo con m aristas, entonces
graent (v) grasal (v) m
vG vG
Grafos 10
Definiciones
– Sea G es un grafo con n vértices y m aristas.
• Si G es no dirigido, entonces m n(n-1)/2.
• Si G es dirigido, entonces m n(n-1).
Camino: secuencia de vértices <v1, v2,…., vn> tal
que (vi, vi+1) son adyacentes.
a b a b
c c
d e d e
C1= { a, b, e, d, c} C2= { b, e, d, c}
Grafos 11
Definiciones
Camino simple: todos los vértices son distintos.
Longitud de un camino: número de aristas del
camino = n – 1.
Ciclo: camino simple que tiene el mismo vértice
inicial y final.
a b
Camino simple = { a, b, e}
c
Ciclo = { c, e, d, c}
d e
Grafos 12
Definiciones
Dos vértices v, w están conectados si existe un
camino de v a w.
Grafo conectado (conexo): si hay un camino
entre cualquier par de vértices.
– Si es un grafo dirigido se llama fuertemente conexo.
a b a b
c c
d e d e
Conectado No conectado
Grafos 13
Definiciones
Subgrafo: subconjunto de vértices y aristas que
forman un grafo.
Componente conectado: subgrafo conectado
máximo.
3 componentes conectados
Grafos 14
Definiciones
Árbol: grafo conectado sin ciclos.
Bosque: colección de árboles.
Grafo completo: todos los pares de vértices son adyacentes. (m = n*(n-1)/2)
En un grafo no dirigido G con n vértices y m aristas se cumple lo siguiente:
– Si G es conectado, entonces m n - 1
– Si G es un árbol, entonces m = n - 1
– Si G es un bosque, entonces m n - 1
Grafos 15
Definiciones
Árbol de cubrimiento de un grafo G: subgrafo que
– es un árbol.
– contiene todos los vértices de G.
El fallo de una arista desconecta el sistema (menos
tolerante a fallos).
Grafos 16
Definiciones
Un grafo está etiquetado si asociamos a cada
arista un peso o valor.
Grafo con pesos: grafo etiquetado con valores
numéricos.
2
2 b d 3
s 4
1 t
3 3 2
a c
Grafos 17
Definiciones
Circuito de Euler: camino que recorre todas las
aristas una vez y retorna al vértice de partida.
grafo A D
Puentes de Koenigsberg B
Teorema de Euler (1736): un grafo tiene un circuito de Euler
si y solo si todos los vértices tienen grado par.
Más definiciones y teoremas en Teoría de Grafos.
Grafos 18
El tipo de dato abstracto Grafo
El TDA Grafo es un contenedor de posiciones que almacena los vértices y las aristas del grafo.
Operaciones para la información posicional:
– tamano(), devuelve el número de vértices más el número de aristas de G.
– estaVacio()
– elementos()
– posiciones()
– reemplazar(p, r)
– intercambiar(p, q)
donde p y q indican posiciones, y r indica un elemento de información.
Grafos 19
El tipo de dato abstracto Grafo
Operaciones generales: (v: vértice, e: arista, o: elemento de
información).
numVertices() Devuelve el número de vértices de G
numAristas() Devuelve el número de aristas de G
vertices() Devuelve una lista de los índices de los
vértices de G
aristas() Devuelve una lista de los índices de las
aristas de G
grado(v) Devuelve el grado de v
verticesAdyacentes(v) Devuelve una lista de los vértices adyacentes a v
aristasIncidentes(v) Devuelve una lista de las aristas incidentes en v
verticesFinales(e) Devuelve un array de tamaño con los vértices
finales de e
opuesto(v, e) Devuelve los puntos extremos de la arista e
diferente a v
esAdyacente(v, w) Devuelve verdadero si los vértices v y w son
Grafos adyacentes 20
El tipo de dato abstracto Grafo
Operaciones con aristas dirigidas:
aristasDirigidas() Devuelve una lista de todas las aristas dirigidas
aristasNodirigidas() Devuelve una lista de todas las aristas no
dirigidas
gradoEnt(v) Devuelve el grado de entrada de v
gradoSalida(v) Devuelve el grado de salida de v
aristasIncidentesEnt(v) Devuelve una lista de todas las aristas de
entrada a v
aristasIncidentesSal(v) Devuelve una lista de todas las aristas de salida a v
verticesAdyacentesEnt(v) Devuelve una lista de todas las aristas
adyacentes a v a través de las aristas de entrada
av
verticesAdyacentesSal(v)Devuelve una enumeración de todas las aristas
adyacentes a v a través de las aristas de salida a
v
destino(e) Devuelve el destino de la arista dirigida e
origen(e) Devuelve el origen de la arista dirigida e
esDirigida(e) Devuelve verdadero si la arista e es dirigida
Grafos 21
El tipo de dato abstracto Grafo
Operaciones para actualizar grafos:
– insertaArista(v, w, o) Inserta y devuelve una arista no dirigida entre
los vértices v y w, almacenando el objeto o
en
esta posición
– insertaAristaDirigida(v, w, o) Inserta y devuelve una arista dirigida entre los
vértices v y w, almacenando el objeto o en
esta
posición
– insertaVertice(o) Inserta y devuelve un nuevo vértice
almacenando el objeto o en esta posición
– eliminaVertice(v) Elimina vértice v y todas las aristas incidentes
– eliminaArista(e) Elimina arista e
– convierteNoDirigida(e) Convierte la arista e en no dirigida
– invierteDireccion(e) Invierte la dirección de la arista dirigida e
– asignaDireccionDesde(e, v) Produce arista dirigida e salga del vértice v
Grafos – asignaDireccionA(e, v) Produce arista dirigida e entrante al vértice v22
Estructuras de datos para Grafos
Se necesita almacenar los vértices y las aristas
del grafo y realizar eficientemente las
operaciones del TDA Grafo.
Las estructuras de datos usuales son:
– Lista de aristas.
– Lista de adyacencia.
– Matriz de adyacencia.
Grafos 23
Lista de Aristas
La estructura lista de aristas almacena los
vértices y las aristas en secuencias sin ordenar.
Fácil de implementar.
Hallar las aristas incidentes sobre un determinado
vértice es ineficiente porque requiere el examen
entero de la estructura que almacena las aristas.
a
1 2
a b c d e
d e
b
1 2 3 4
4 c 3
Grafos 24
Eficiencia de la estructura Lista de Aristas
Operación Tiempo
tamano, estaVacio, remplazarElemento,
O(1)
intercambiar
numVertices, numAristas O(1)
vertices O(n)
aristas, aristasDirigidas, aristasNodirigidas O(m)
elementos, posiciones O(n + m)
verticesFinales, opuesto, origen, destino,
O(1)
esDirigida, grado, gradoEnt, gradoSalida
aristasIncidentes, aristasIncidentesEnt,
aristasIncidentesSal, verticesAdyacentes, O(m)
verticesAdyacentesEnt, verticesdyacentesSal
esAdyacente O(m)
aristasIncidentes, aristasIncidentesEnt,
aristasIncidentesSal, verticesAdyacentes, O(1)
verticesAdyacentesEnt, verticesdyacentesSal
insertaVertice O(1)
eliminaVertice O(m)
Espacio requerido O(n + m)
Grafos 25
Lista de Adyacencia
Lista de adyacencia del vértice v: secuencia de
vértices adyacentes a v.
Representa el grafo por las listas de adyacencia
de todos los vértices.
Es la estructura más usada para representar
grafos con pocas aristas (dispersos).
a
1 2
1 2 a 4 d
e 2 3 b
d b
3 4 c
4 2 e
4 c 3
Grafos 26
Eficiencia de la estructura Lista de Adyacencia
Operación Tiempo
tamano, estaVacio, remplazarElemento,
O(1)
intercambiar
numVertices, numAristas O(1)
vertices O(n)
aristas, aristasDirigidas, aristasNodirigidas O(m)
elementos, posiciones O(n + m)
verticesFinales, opuesto, origen, destino,
O(1)
esDirigida, grado, gradoEnt, gradoSalida
aristasIncidentes, aristasIncidentesEnt,
aristasIncidentesSal, verticesAdyacentes, O(grado(v))
verticesAdyacentesEnt, verticesdyacentesSal
esAdyacente O(min(grado(u), grado(v))
aristasIncidentes, aristasIncidentesEnt,
aristasIncidentesSal, verticesAdyacentes, O(1)
verticesAdyacentesEnt, verticesdyacentesSal
insertaVertice O(1)
eliminaVertice O(grado(v))
Espacio requerido O(n + m)
Grafos 27
Matriz de Adyacencia
Matriz M[i][j] con entradas para todos los pares
de vértices.
– En grafos no etiquetados:
• M[i][j] = verdadero, si hay una arista (i, j) en el grafo.
• M[i][j] = falso, si no hay una arista (i, j) en el grafo.
– En grafos no dirigidos: M[i][j] = M[j][i]. La matriz es
simétrica.
1 2
1 2 3 4
1 F V F V
2 V F V V
3 F V F V
4 V V V F
4 3
Grafos 28
Matriz de Adyacencia
– En grafos etiquetados:
• M[i][j] = atributo de la arista (i, j) en el grafo, indicador especial
si no hay una arista (i, j).
Es la estructura más usada para representar
grafos con muchas aristas (densos).
a
1 2
1 2 3 4
1 - a - d
d e
b 2 - - b -
3 - - - c
4 - e - -
4 c 3
Grafos 29
Eficiencia de la estructura Matriz de Adyacencia
Operación Tiempo
tamano, estaVacio, remplazarElemento,
O(1)
intercambiar
numVertices, numAristas O(1)
vertices O(n)
aristas, aristasDirigidas, aristasNodirigidas O(m)
elementos, posiciones O(n + m)
verticesFinales, opuesto, origen, destino,
O(1)
esDirigida, grado, gradoEnt, gradoSalida
aristasIncidentes, aristasIncidentesEnt,
aristasIncidentesSal, verticesAdyacentes, O(n)
verticesAdyacentesEnt, verticesdyacentesSal
esAdyacente O(1)
aristasIncidentes, aristasIncidentesEnt,
aristasIncidentesSal, verticesAdyacentes, O(1)
verticesAdyacentesEnt, verticesdyacentesSal
insertaVertice O(n2)
eliminaVertice O(n2)
Espacio requerido O(n2)
Grafos 30
Indice
1. Introducción.
2. Definiciones y representación.
3. Recorridos en grafos.
4. Algoritmos de caminos más cortos.
5. Árbol de cubrimiento de costo mínimo.
6. Flujo en redes. Flujo máximo.
Grafos 31
