FLUJOS MÁXIMOS
Estructuras y Algoritmos de Procesamiento de Datos II
DEFINICIÓN
En teoría de grafos, un grafo dirigido con pesos es también conocido como una red. En los problemas de flujo en redes, las aristas representan canales por los que puede circular cierta cosa: datos, agua, coches, corriente eléctrica, etc. Los pesos de las aristas representan la capacidad máxima de un canal: velocidad de una conexión, volumen máximo de agua, cantidad máxima de tráfico, voltaje de una línea eléctrica, etc.; aunque es posible que la cantidad real de flujo sea menor.
ALGORITMO DE FLUJO MAXIMO
El algoritmo de flujo máximo, es un algoritmo que tiene como objetivo, encontrar el mayor flujo que se puede enviar desde una fuente origen hacia una fuente destino, a través de diferentes arcos que tienen una capacidad máxima de flujo.
CONCEPTOS BASICOS
FLUJO
Envió o circulación de algún producto o sustancia a través de una superficie en una unidad de tiempo.
NODO
Es la fuente por donde ingresa o sale el flujo.
ARCO
Es el canal por donde fluye el producto o sustancia entre dos nodos.
CAPACIDAD DE FLUJO
Es la cantidad máxima de flujo que puede ingresar o salir por un nodo.
NODO ORIGEN
Es el nodo por el cual el flujo ingresa.
NODO DESTINO
Es el nodo por el cual el flujo sale.
