FLUJO MÁXIMO
Definiciones básicas
Flujo: Circulación de unidades homogéneas de un lugar a otro.
Capacidad de flujo: es la capacidad de unidades que pueden entrar por el nodo fuente y salir por el nodo destino.
Origen o fuente de flujo: nodo por el cual el flujo ingresa.
Destino o Sumidero de flujo: nodo por el cual el flujo sale.
Capacidades residuales: capacidades restantes unas vez que el flujo pasa el arco.
Ford Fulkerson
Para la resolución de problemas de flujo máximo se requiere el uso del método Ford Fulkerson. Este método propone buscar caminos en los que se pueda aumentar el flujo hasta que se alcance el flujo máximo, la idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos de origen y destino.
- El flujo es siempre positivo y con unidades enteras.
- El flujo a través de un arco es menor o igual que la capacidad.
- El flujo que entra en un nodo es igual al que sale de él.
Hallar el flujo máximo del siguiente problema:
Método Ford Fulkerson
El nodo de origen como se puede observar es el numero 1 de color amarillo, y el nodo de destino es el numero 5 de color azul.
Flujo Máximo = 20+10+10+10+10
El flujo máximo que puede pasar del nodo origen 1 hasta el nodo destino es de 60.
No hay comentarios:
Publicar un comentario