Redes De Flujo1

REPÚBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL POLITÉCNICA DE LA FUERZA
ARMADA

NÚCLEO MÉRIDA

Redes de Flujo
Ing. JosmaryFernández
Ing. Lucileima Rosales

Redes de Flujo




Las redes de flujo son modelos matemáticos
aplicables a situaciones tales como: sistemas de
tuberías (para fluídos como agua, petróleo o gas),
redes decableado eléctrico, sistemas de carreteras,
sistemas de transporte de mercancías, etc.
Así como modelamos los enlaces de una red y sus
nodos como un grafo dirigido, podemos interpretar
el grafo como unared de flujo de algún material.

Problema de flujo máximo: Cual es la tasa mayor a la
cual el material puede ser transportado de la fuente
al resumidero sin violar ninguna restricción de
capacidad?Definición formal





Una red de flujo es un digrafo G = (V;E) con una
función de capacidad c : E ! R+ y dos vértices
distinguidos, llamados fuente y sumidero.
Una
fuente
produce
material
enforma
estacionaria y un sumidero lo consume.
Cada arco puede ser considerado como un
conducto de cierta capacidad.

Múltiples fuentes y sumideros




Si hay múltiples fuentes y resumideros, el
problemase puede reducir al caso simple
previo de una fuente y un resumidero.
Supongamos que se tiene {s1,s2,s3,..sm}
fabricas y {t1,t2,t3,..,tn} puntos de venta.

Definiciones asociadas
Un flujo en una redG = (V;E) con capacidad c es una
función f : V £ V ! R que cumple las siguientes condiciones:

El problema del flujo máximo trata de maximizar
este flujo

Teorema de flujo máximo - corte mínimo
Para cualquier red el flujo máximo desde el nodo
fuente al nodo destino es igual a la capacidad del
corte mínimo.

Un corte separa el nodo fuente del nodo destino, es decir, es
una partición de losnodos de la red en dos subconjuntos S y
S* tal que el nodo fuente está en S y el nodo destino está en S *
Por ejemplo, un corte
para la red de la Figura
1 es el constituído por
S =(s; v)
T = (u; t)....