Callado

1.1. REDES
1.1.1. MODELOS DE REDES
Una red de transporte es una herramienta que nos permite modelar problemas sobre flujo de materiales. Imagine, por ejemplo, un producto navegando a través de un sistema desde una fuente, en donde el material es producido, hasta un destino, en donde es consumido o almacenado. La fuente produce el material y es capaz de bombearlo a una cierta velocidad fija, desuerte que los destinatarios pueden consumirlo o almacenarlo a la misma velocidad. Intuitivamente podemos pensar que el "flujo" del material en cualquier punto del sistema es la velocidad a la cual el material se mueve. De esta forma las redes de transporte pueden ser usadas para modelar líquido fluyendo a través de tuberías, partes a través de líneas de ensamblaje, corriente a través de redeseléctricas, información a través de redes de comunicación, etc. El problema de flujo máximo en redes de transporte se refiere a la consecución de la tasa o velocidad máxima a la cual el material puede ser bombeado de la fuente al destino sin violar las capacidades de los conductos intermedios. 
Definición
Una red de transporte (o simplemente red) es un digrafo [pic]simple (i.e. sin lazos o rizosni lados paralelos), con las siguientes propiedades:
• Existe un solo nodo en [pic], que solo tiene lados de salida y no tiene lados de llegada; tal nodo se denomina la fuente.
• Existe un solo vértice en [pic], que solo tiene lados de entrada y no tiene lados de salida; tal nodo se denomina el depósito o destino.
• Para cada lado [pic]que une digamos, los vértices [pic]y [pic]seasocia un número real [pic], que se conoce como la capacidad de la arista [pic]. Formalizando un poco más este concepto, podemos pensar que existe una función de valor real [pic], tal que si el par [pic], entonces [pic]. Dicha función se llama la función capacidad
• Para cualquier vértice [pic]en [pic], existirá al menos un lado de entrada o un lado de salida.
No se debe confundir losconceptos de capacidad (que acabamos de definir) y flujo (que es la próxima definición), el hecho de que una tubería tenga capacidad 50, no quiere decir que ese será el flujo que transportará.
Definición
Sea [pic]una red de transporte, y [pic]la capacidad de la arista (dirigida) [pic], definimos el flujo en la arista [pic]como una cantidad real [pic]que satisface las siguientes características:
•(RESTRICCIÓN DE CAPACIDAD) El flujo no supera la capacidad en cada lado, i.e. [pic].
• (FLUJO NULO) Si entre el vértice [pic]y el vértice [pic]no hay arista, se define [pic].
• (CONSERVACIÓN DEL FLUJO) La cantidad de flujo que entra a un nodo (que no es ni fuente ni destino) es la misma cantidad que sale de él. Más detalladamente, para cada nodo [pic], que no es ni fuente ni depósito, secumple
[pic]
Formalizando un poco más el concepto de flujo podemos pensar de éste como una función [pic]tal que [pic]y [pic]son vértices de [pic], entonces [pic].
Utilizamos la notación [pic]/[pic] para indicar que la arista con capacidad [pic]está transportando [pic]unidades de flujo. Note que al nodo [pic]llegan 4 unidades de flujo y salen 4 unidades de flujo. Esto ilustra lapropiedad de la conservación del flujo. Observe también que de la fuente salen 9 unidades de flujo y al depósito llegan 9 unidades de flujo. Esta propiedad se cumple siempre, y la registramos en el siguiente teorema.
Teorema 1
Sea [pic]un flujo sobre una red [pic], entonces se cumple que el flujo que sale de la fuente es igual al flujo que llega al depósito; más exactamente
[pic]En donde [pic]es elnodo fuente y [pic] es el nodo destino.

Consideremos la red G de la siguiente figura. Si hacemos P = {a, b. d}, entonces y (p, p es un corte en G. Como muestra la figura, a veces indicamos un corte teniendo una línea punteada para separar los vértices.
[pic]
Capacidad de corte: La capacidad del corte (p p) es el número

[pic]
Ejemplo: La capacidad del corte de la...