Scribd
Cargar
55 vistas2 páginas

Análisis de Flujo Máximo en Redes

El documento describe el algoritmo de flujo máximo para determinar la capacidad máxima de flujo que puede pasar a través de una red dirigida. El algoritmo funciona iterativamente asignando flujo a caminos de la fuente al sumidero hasta que no queden caminos disponibles. Primero se construye la red residual y luego se encuentra un camino con capacidad positiva para aumentar el flujo asignado.

Cargado por

Abel González Antuna
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
55 vistas2 páginas

Análisis de Flujo Máximo en Redes

El documento describe el algoritmo de flujo máximo para determinar la capacidad máxima de flujo que puede pasar a través de una red dirigida. El algoritmo funciona iterativamente asignando flujo a caminos de la fuente al sumidero hasta que no queden caminos disponibles. Primero se construye la red residual y luego se encuentra un camino con capacidad positiva para aumentar el flujo asignado.

Cargado por

Abel González Antuna
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

ANALISIS DE FLUJO (flujo máximo)

Tenemos el conocido problema de: ¿cuál es la tasa mayor a la cual el material puede ser transportado
de la fuente al sumidero sin violar ninguna restricción de capacidad?
el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la
fuente y salir por el nodo de destino pasando por una red de arcos dirigidos cada arco tiene una
capacidad máxima de flujo admisible.
El procedimiento para obtener el flujo máximo de una red consiste en seleccionar repetidas veces
cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.

 Dada una red de flujo máximo, plantee la red residual asociada, hasta conseguir una red
residual con valor de cero.

 Encuentre la trayectoria de la fuente al destino con capacidad de flujo estrictamente


positivo (si no existe alguno, es porque se ha encontrado el óptimo).

 Examine estas trayectorias para encontrar la rama o arco con la menor capacidad de flujo


restante e incremente en este valor, la capacidad del flujo en sentido contrario.

 Determine todas las trayectorias estrictamente positivas, hasta que no se permita flujo del
nodo a un nodo destino.

Características del grafo:


Todo flujo a través de una red dirigida se origina un nodo llamado fuente y termina en otro
llamado destino.

Los nodos restantes son nodos de transbordo.

 Dirección de los grafos


Se permite el flujo a través de un arco solo en la dirección indicada por la flecha, en la fuente
todos los arcos señalan hacia afuera. En el destino todos señalaran hacia el nodo. E l flujo que entra
en un nodo es igual al que sale.

 Restricciones
Cada arco cuenta con un flujo con una capacidad. La cantidad que se obtiene en nodo fuente debe
ser igual a la cantidad obtenida en el nudo destino. El flujo va a ser siempre positivo y con unidades
enteras.

En conclusión:
Este algoritmo es un método iterativo, el cual, empieza con un flujo nulo y en cada iteración se va
obteniendo un valor del flujo que va aumentando el camino, hasta que no se pueda aumentar más, por
lo tanto, tenemos:

 Red residual: camino de la fuente al sumidero, donde cada una de las aristas tiene un flujo
residual mayor que cero. Siendo el flujo residual, el flujo que se puede obtener en una
arista una vez que haya pasado un flujo por ella.
 Aumento de camino: se basa en ir aumentando el camino, hasta alcanzar el máximo
(capacidad residual, definido anteriormente).

También podría gustarte