Clase 2: Modelos Basados en Redes
Redes - árbol de expansión mínima - Ruta más corta
Cristian E García
cegarcia@[Link]
Facultad de Ingeniería
Universidad Antonio José Camacho
2024
Outline
1. Modelos de Redes
1.1. Teoría de Grafos
1.2. Ruta más corta
1.3. Flujo Máximo
1.4. Arbol de mínima expansión
2. Ejemplos
3. Ejercicio en Clase
Introducción a la Teoría de Grafos
Grafo no dirigido:
Un grafo no dirigido G consiste en un conjunto V de vértices (o nodos) y un conjunto E de
lados (ramas o enlaces) tales que cada lado e ε E está asociado a un par no ordenado de
vértices v y w. Si un lado e está asociado a un único par de vértices v y w, entonces e= (v,w) o
e=(w,v).
Introducción a la Teoría de Grafos
Grafo no dirigido:
Un grafo no dirigido G consiste en un conjunto V de vértices (o nodos) y un conjunto E de
lados (ramas o enlaces) tales que cada lado e ε E está asociado a un par no ordenado de
vértices v y w. Si un lado e está asociado a un único par de vértices v y w, entonces e= (v,w) o
e=(w,v).
Grafo dirigido:
Un grafo dirigido G consiste en un conjunto V de vértices (o nodos) y un conjunto E de lados
(ramas) tales que cada lado e ε E está asociado a un par ordenado de vértices. Si un lado e
está asociado a un par ordenado único de vértices v y w, se escribe e = (v, w)
Introducción a la Teoría de Grafos
Se dice que un lado e = (v,w) de un grafo (dirigido o no dirigido) es incidente en v y w. Se dice que los vértices v y w
son incidentes en e y también son vértices adyacentes.
Si G es un grafo (dirigido o no dirigido) con un conjunto de vértices V y un conjunto de lados E, se escribe G = (V,E)
Nodo (Vértice):
Un círculo de una red utilizada para representar una planta, almacén o tienda.
Nodo de Suministro:
Nodo desde le cual los productos se van a enviar.
Introducción a la Teoría de Grafos
Nodo de demanda:
Nodo que va a recibir los productos para cumplir con una demanda conocida.
Nodo de transbordo:
Nodo que recibe productos desde otros nodos para su distribución.
Arco (enlace):
Línea de una red que conecta un par de nodos. Se le utiliza para representar una ruta válida
desde el nodo origen al nodo de distribución.
Introducción a la Teoría de Grafos
Representación de un grafo: Representación Matricial
Un grafo se puede representar i) Matriz de Adyacencia
matemáticamente como: ii) Matriz de costo (bene cio)
a) Una matriz
b) Una lista enlazada
c) Árbol
fi
Introducción a la Teoría de Grafos
Matriz de Adyacencia:
Para un grafo G, es una matriz A de dimensión NxN, donde A[i,j] es verdadero (1) si, y sólo si,
existe un arco que vaya del vértice i al vértice j. En ausencia de arco directo se representa
generalmente por 0.
Introducción a la Teoría de Grafos
Ejemplo: Dado el siguiente grafo encontrar su matriz de adyacencia
Introducción a la Teoría de Grafos
Ejemplo: Dado el siguiente grafo encontrar su matriz de adyacencia
1 2 3 4
1 1 1
2 1
3 1
4 1
Introducción a la Teoría de Grafos
Matriz de Costo:
Para un grafo G etiquetado, es una matriz C de dimensión NxN, donde A[i,j] es el costo (valor de
la etiqueta) si, y sólo si, existe un arco que vaya del vértice i al vértice j. En ausencia de arco
directo se representa generalmente por in nito (costo extremadamente alto, para la simulación
se hace uso de un valor fuera de contexto).
fi
Introducción a la Teoría de Grafos
Ejemplo: Dado el siguiente grafo encontrar su matriz de costo
Introducción a la Teoría de Grafos
Ejemplo: Dado el siguiente grafo encontrar su matriz de costo
1 2 3 4
1 10 15
2 12
3 20
4 5
Introducción a la Teoría de Grafos
Para un grafo no dirigido, tanto la matriz de adyacencia como la matriz de costo
son simétricas, esto es:
A[i, j] = A[ j, i]
ó
C[i, j] = C[ j, i]
Modelo de la Ruta más Corta
Modelo de la Ruta más corta
Situaciones:
Se pueden dar dos casos para representar la red:
a Como grafo no dirigido
b Como grafo dirigido
Cualquiera que sea el caso corresponde a grafos
ponderados (con peso)
Modelo de la Ruta más corta
a) Algoritmo: Grafo no dirigido
[Link]énse todos los nodos que estén directamente conectados con el origen.
Etiquetarlos con la distancia al origen y su nodo predecesor. Etiquetas temporales,
[distancia, nodo].
[Link] entre todos los nodos con etiquetas temporales, escoger el que tenga la distancia
menor y se marca como permanente. Si todos están con etiquetas permanentes se va al
paso cuatro.
Modelo de la Ruta más corta
a) Algoritmo: Grafo no dirigido
3. Todo nodo que no tenga etiqueta permanente, tendrá etiqueta temporal o estará sin
etiqueta. Sea L el último nodo con etiqueta permanente. Considerénse todas las etiquetas
de los vecinos de L (directamente conectados a L mediante un arco). Para cada uno de
estos nodos calcúlese la suma de su distancia a L. Si el nodo en cuestión no está
etiquetado, asígnese una etiqueta temporal que conste de esta distancia y de L como
predecesor. Si el nodo en cuestión ya tiene etiqueta temporal, cámbiese sólo si la distancia
recién calculada es menor que la componente de distancia de la etiqueta actual. En este
caso, la etiqueta contendrá esta distancia y a L como predecesor. Regresar al paso 2
Modelo de la Ruta más corta
a) Algoritmo: Grafo no dirigido
4. Las etiquetas permanentes indican la distancia más corta entre el nodo origen a cada
nodo de la red. También indican el nodo predecesor en la ruta más corta hacia cada
nodo. Para encontrar el camino más corto de un nodo dado, comiéncese en él y
retroceda al nodo anterior. Continuar con el recorrido hasta llegar al origen.
Modelo de la Ruta más corta
Ejemplo: Para el siguiente grafo encontrar la distancia más corta desde el nodo H al resto de los
nodos.
Modelo de la Ruta más corta
Solución
Algoritmo de Dijkstra
Es una técnica exhaustiva, esto es, prueba todas las alternativas posibles.
Opera a partir de un conjunto S de vértices cuya distancia más corta desde el origen ya es
conocida. Inicialmente S contiene sólo el nodo de origen. En cada paso se agrega algún
vértice restante v a S, cuya distancia desde el origen es la más corta posible.
Para cada paso del algoritmo, se utiliza una matriz D para registrar la longitud del camino
más corto a cada vértice.
Algoritmo de Dijkstra
INICIO
0) V = {1, 2, 3, 4, ..., n}
1) S = {1} // nodo 1 se supone que es el
origen
2) Para i=2 Hasta n Hacer
3) Di = C1i
4) Para i=1 Hasta n-1 Hacer
5) Elegir un vértice w en V-S tal que Dw sea un
mínimo
6) agregar w a S
7) Para cada vértice v en V-S Hacer
SI ((Dw+Cwv)<Dv)
//Pv = w
Dv = Dw+Cwv
8) //Dv = mínimo(Dv,Dw+Cwv)
FIN
Algoritmo de Dijkstra
Ejemplo: Aplicar el algoritmo al siguiente grafo dirigido
Algoritmo de Dijkstra
Inicial
0) V = {1, 2, 3, 4, 5}
1) S = {1}
2)
3) D2 = 10, D3 = inf, D4=30, D5 = 100
Iteración S w D2 D3 D4 D5
Inicial {1} -- 10 inf 30 100
4) Iterar 4 veces
5) Seleccionar nodo con distancia más corta de V-S,
En el ejemplo es el nodo 2
Algoritmo de Dijkstra
Iteración S w D2 D3 D4 D5
Inicial {1} -- 10 inf 30 100
1 {1,2} 2 10 60 30 100
Algoritmo de Dijkstra
Iteración S w D2 D3 D4 D5
Inicial {1} -- 10 inf 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
Algoritmo de Dijkstra
Iteración S w D2 D3 D4 D5
Inicial {1} -- 10 inf 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
3 {1,2,4,3} 3 10 50 30 60
Algoritmo de Dijkstra
Modelo de árbol extensión mínima
Modelo de árbol extensión mínima
De nición 1: Un árbol es un grafo que tiene sus n nodos (vértices) conectados (conexo) con n-1
arcos (aristas), no existiendo ciclos (caminos cerrados)
De nición 2: Un árbol de expansión de costo mínimo es aquel en que todos los enlaces tienen
longitudes (costos) mínimas
fi
fi
Modelo de árbol extensión mínima
Método Grá co
1. Se selecciona un nodo cualquiera y se conecta al nodo más
cercano a éste.
2. Se identi ca el nodo no conectado más cercano a un nodo
conectado y se conectan estos dos nodos.
Nota: Empates se deciden en forma arbitraria. Los empates
indican que existen soluciones alternativas para la construcción.
fi
fi
Modelo de árbol extensión mínima
Método Grá co
1. Se selecciona un nodo cualquiera y se conecta al nodo más
cercano a éste.
2. Se identi ca el nodo no conectado más cercano a un nodo
conectado y se conectan estos dos nodos.
Nota: Empates se deciden en forma arbitraria. Los empates
indican que existen soluciones alternativas para la construcción.
fi
fi
Modelo de árbol extensión mínima
Método Grá co
Ejemplo: Encontrar el AEM para el siguiente grafo
fi
Modelo de árbol extensión mínima
Método Grá co
Ejemplo: Encontrar el AEM para el siguiente grafo
fi
Modelo de árbol extensión mínima
Método Grá co
fi
¿Preguntas?
