Terminologia

5.1 TERMINOLOGÍA 
Una red consiste de puntos llamados nodos o vértices y las líneas que llaman arcos. Dos nodos pueden estar conectados por un conjunto de arcos. Una trayectoria es una secuencia de arcos distintos (con nodos no repetidos) conectando a los nodos. Los arcos pueden tener una dirección asociada, que se denominan arcos dirigidos, si un arco no tiene dirección se le denomina rama. Sitodos los arcos en la red son dirigidos, la red se denomina una red dirigida. Si todos los arcos son no-dirigidos, la red es una red no-dirigida. 
Una trayectoria no dirigida puede incluir arcos dirigidos apuntando en cualquiera de dirección. Una trayectoria que comienza y que termina en el mismo nodo se denomina ciclo y puede ser ya sea dirigida o no-dirigida. 
Terminología de Redes 

• Red:conjunto de puntos y líneas que unen ciertos pares de puntos. 
• Nodos: Puntos (o vértices). 
• Arcos: Líneas, ligaduras, aristas o ramas. Se etiquetan para dar nombre a los nodos en sus puntos terminales. 
• Arco dirigido: Si el flujo a través de un arco se permite sólo en una dirección. La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco. 
• Arco nodirigido: Si el flujo a través de un arco se permite en ambas direcciones. 
• Red dirigida: Red que tiene sólo arcos dirigidos. 
• Red no dirigida: Todos sus arcos son no dirigidos. 
• Trayectoria: Sucesión de arcos distintos que conectan nodos. 
• Ciclo: Trayectoria que comienza y termina en el mismo nodo. 
• Red conexa: Red en la que cada par de nodos está conectado. 
• Árbol: Red conexa (para algúnsubconjunto de n nodos) que no contiene ciclos no dirigidos. 
• Árbol de expansión: Red conexa para los n nodos que contiene ciclos no dirigidos. 
• Capacidad del arco: Cantidad máxima de flujo (quizá infinito) que puede circular en un arco dirigido. 
• Nodo fuente: Nodo origen, tiene la propiedad de que el flujo que sale del nodo excede el flujo que entra a él. 
• Nodo de demanda: Nodo dedestino, donde el flujo que llega excede al que sale de él. 
• Nodo de trasbordo: Intermedio, satisface la conservación del flujo, es decir, el flujo que entra es igual al que sale. 

http://www.taringa.net/post/apuntes-y-monografias/17636522/Optimizacion-de-Redes.html
5.2 PROBLEMA DE LA RUTA MAS CORTA 
Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cadaligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino. 
Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en ordenascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino. 

Algoritmo de la ruta más corta: 
1. Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano sea el nodo destino.) 
2. Datos para la n-ésima iteración: n-1 nodos máscercanos al origen (encontrados en las iteraciones previas), incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos.) 
3. Candidatos para el n-ésimo nodo más cercano: Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo noresuelto que tiene la ligadura más corta. (Los empates proporcionan candidatos adicionales.) 
4. Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. 
5.3 PROBLEMA DEL ÁRBOL DE MÍNIMA EXPANSIÓN 
Este problema se refiere a utilizarlas ramas o arcos de la red para llegar a...