Diagrama de flujo
Flujo máximo
Contenido del diagrama
Flujo máximo
Una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se le asocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva.
Puede ser utilizada para modelar:
El tráfico en un sistema de autopistas
Fluidos viajando en tuberías
Corrientes eléctricas en circuitos eléctricos
Sistemas similares por lo que viaje algo entre nodos
Algoritmo de flujo máximo
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
Ford-Fulkerson
Depende de tres puntos vitales:
Red residual
Aumento de camino
Corte en redes de flujo
Camino de la fuente al sumidero, donde cada una de las aristas tiene un flujo residual mayor que cero.
Se basa en ir aumentando el camino, hasta alcanzar el máximo (capacidad residual).
Consiste simplemente en realizar una partición del conjunto de vértices en dos subconjuntos.
Restricciones
Los valores de flujo existentes en cada arista no pueden sobrepasar los valores máximos
La suma de las entradas de cada nodo interior tiene que ser igual a la suma de sus salidas
Características principales
El flujo va a ser siempre positivo y con unidades enteras.
El flujo que entra en un nodo es igual al que sale.
El flujo que atraviesa un arco nunca será mayor que la capacidad, solo puede ser menor o igual que ella.
Información
- Descripción
- Diagrama sobre Flujo máximo , creado por Rodrigo Ivan Barron Peraza el 29/03/2019.
- Creado por
- Rodrigo Ivan Barron Peraza
- Visitas
- 0
- Valoración
Más sobre Flujo máximo en redes