RED DE FLUJO MAXIMO




Modelo de Red de Flujo Máximo

M.A. José Manuel Vera Reyes


Animas Salinas Alejandra Gabriela
Castro Corona Ricardo
Contreras Torres Ana Laura
Hernández Miguel Laura

26/07/13 9° “A”



Índice:

Introducción_____________________________________________3

Red de flujomáximo_______________________________________4

Ejercicio 1_______________________________________________7

Ejercicio 2_______________________________________________9

Ejercicio 3_______________________________________________11

Ejercicio 4_______________________________________________13

Bibliografia______________________________________________17





Introducción

Así como modelamos los enlaces de unared y sus nodos como un grafo dirigido, podemos interpretar el grafo como una red de flujo de algún material.
• Una fuente produce material en forma estacionaria y un resumidero lo consume.
• Cada arco puede ser considerado como un conducto de cierta capacidad.
• Como con la ley de corrientes de Kirchhoff, la suma de flujos entrantes a un vértice debe ser igual a la saliendo del vértice.Red de flujo máximo
El problema de flujo máximo se interpreta cuando hay una red conexa dirigida con arcos con base en una capacidad limitada para encontrar el flujo máximo que puede enviarse desde su origen a si destino.
Nos permite conocer (calcular) la máxima cantidad de cualquier artículo o información que podemos ubicar.

Principalmente este modelo se utiliza para reducir losembotellamientos entre puntos de partida y destino de una red.
Existe un flujo que existe desde un único lugar de origen hasta un único lugar de destino a través de arcos que conectan nodos intermedios.
Cada arco tiene una capacidad que no puede ser extendida.
La capacidad no debe ser necesariamente la misma para cada dirección del arco.


Pasos a seguir:  
Primer paso: Elegir una rutaarbitraria.
Segundo paso: En dicha ruta escoger aquel ramal de menor flujo en ese sentido y transportar por esa ruta la cantidad escogida.
Hacer esto repetitivamente hasta que no sea posible encontrar una ruta con capacidad de flujo






Modelo del flujo máximo: En algunas redes circula por los arcos un flujo (envío o circulación de unidades homogéneas de algún producto: automóviles en unared de carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra óptica) desde el origen o fuente al destino, también denominado sumidero o vertedero. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:
El flujo es siempre positivo y con unidades enteras.
El flujo a través de unarco es menor o igual que la capacidad.
El flujo que entra en un nodo es igual al que sale de él.
En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:

Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujoentre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad proporciona el flujo máximo en la red.
El siguiente grafo ilustra 3 cortes: el Corte 1 con capacidad 60, el Corte 2 con capacidad 110 y el Corte 3 con capacidad 70. Todo lo que podemos obtener de los 3 corteses que el flujo máximo en la red no excede de 60 unidades. No podemos saber cuál es el flujo máximo hasta que se hayan enumerado todos los cortes en la red:



Las capacidades se identifican como sigue: por ejemplo, para el arco (3,4), el límite de flujo es de 10 unidades de 3 a 4 y de 5unidades de 4 a 3.

















Ejercicio 1
En una ciudad se va a construir una...