REDES Flashcards
Árbol de expansión mínima.
Algoritmo de Kruskal.
El problema del árbol de expansión mínima consiste en conectar todos los nodos de una red, sin formar un ciclo, de manera tal que se minimice la longitud total.
- Parto desde cualquier nodo, seleccionado aleatoriamente.
- Busco el arco con menor tamaño y conecto a otro nodo
- Hay n-1 arcos? Siendo n la cantidad de nodos.
- Si no se cumplio la condicion vuelvo a buscar el arco mas corto desde los nodos que ya forman parte del arco.
Ruta más corta.
Algoritmo de Dijkstra. Modelo lineal para problemas de ruta más corta.
Existe un nodo inicial y un nodo final
Usualmente los arcos no estan orientados por lo cual se permite el trafico en ambos sentidos.
→ Etiqueta [suma de distancias / desde que nodo viene]
La ruta más corta entre el nodo inicial y cualquier otro nodo se determina retrocediendo por los nodos a partir del nodo destino, con la información que dan las etiquetas permanentes
Flujo máximo.
Algoritmo de la trayectoria en aumento
- Todo flujo en una red conexa dirigida se origina en un nodo fuente y finaliza en un nodo destino.
- Los nodos restantes son nodos de transbordo y en cada uno de ellos debe cumplirse la relación de equilibrio flujo que sale = flujo que entra.
- Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco.
- El objetivo es maximizar la cantidad total de flujo de la fuente al destino sin exceder la capacidad de los arcos.
Para la resolucion se utiliza la red residual. Una red residual muestra las capacidades restantes en cada arco luego de haber asignado determinado flujo a cada uno
Flujo capacitado con costo mínimo. Modelo lineal para problemas de flujo capacitado con costo mínimo.
El problema de flujo con costo mínimo tiene una posición medular entre los problemas de optimización de redes, debido a dos motivos:
- Todos los problemas transporte, transbordo, asignación, ruta más corta,flujo máximo e inclusive CPM, son casos especiales del problema de flujo con costo mínimo.
- Su solución, mediante el algoritmo simplex capacitado para redes, es muy eficiente.
Las características del problema son las siguientes
- La red es una red dirigida conexa.
- Al menos uno de los nodos es fuente (suministro). Al menos uno de los nodos es destino (demanda). Los nodos restantes son nodos de transbordo.
- Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco. (Si el flujo puede ocurrir en ambas direcciones, debe representarse por un par de arcos con direcciones opuestas).
- El costo del flujo a través del arco es proporcional a la cantidad de ese flujo. Se conoce el costo por unidad.
El problema consiste en minimizar el costo total sujeto a la disponibilidad y la demanda de algunos nodos, y a la capacidad máxima de flujo de cada arco.
Terminologia de Redes
