En teoría de grafos, 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 o sistemas similares por lo que viaje algo entre nodos.
Una red de flujo es un grafo dirigido
Se distinguen dos vértices: la fuente s y el destino t. Se supone que cada vértice se encuentra en alguna ruta de s a t.
tal que El valor del flujo es
Tenemos el conocido problema de flujo máximo o maximal: ¿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?
En otras palabras, 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.
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.
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.