Para entender el problema de flujo máximo primero debemos entender qué es una red.
Una red $N = (V, E, c)$ es un grafo orientado que:
Luego, una función de flujo $f : E \to \R_{\geq 0}$ es una función de flujo sobre la red $N$ si cumple las siguientes características:
Restricción de capacidad: $f(e) \leq c(e)$ para toda arista $e \in E$.
Conservación de flujo: para todo vértice $v \in V \setminus \{s, t\}$
$$ \sum_{w \in N^+(v)} f(w, v) = \sum_{w \in N^-(v)} f(v, w) $$
donde $N^+$ es la vecindad de entrada de $v$ y $N^-(v)$ es su vecindad de salida.
El valor de la función de flujo es la cantidad de flujo neto que sale de $s$, es decir
$$ F = \sum_{w \in N^-(v)}f(s, w) - \sum_{w \in N^+(v)}f(w, s) $$
Entonces, el problema de flujo máximo es un problema de optimización que toma como entrada una red $N$ y devuelve una función de flujo de valor máximo.
Varios problemas pueden resolverse modelándose como problemas de flujo. El ejemplo más conocido es una red de cañerías, donde cada intersección entre caños está representada como un nodo y cada trecho de cañería que los une como una arista. A cada caño le corresponde una capacidad máxima, y queremos averiguar cuántas unidades de líquido podemos enviar desde $s$ sin averiar los caños a causa de sobrecargarlos. Claramente queremos enviar la cantidad máxima posible, y el modelado como red de flujo nos es muy útil para representar que toda unidad en la red debe salir de $s$ y llegar a $t$, es decir, no puede producirse en otro lado de la red ni perderse en ella. Esto nos es garantizado por la restricción de conservación de flujo. Asimismo sabremos que no sobrecargamos los caños ya que la función de flujo cumple con la restricción de capacidad.
¿Cómo sabemos que un flujo es máximo? Gracias al teorema de flujo máximo-corte mínimo que afirma que
Dada una red $N = (V, E, c)$ el valor del flujo máximo $f$ es igual a la capacidad del corte mínimo y la red residual $R(G, f)$ no contiene caminos de aumento.
Pero, ¿a qué llamamos un corte mínimo? Definimos un corte como un subconjunto de nodos $S \subseteq V$ tal que $s \not \in S$, y este es mínimo cuando su capacidad $c(S) = \sum_{e \in S^+} c(e)$ ($S^+$ es el conjunto de aristas salientes de $S$) lo es.
Uno de los algoritmos más conocidos para encontrar el flujo máximo de una red es Ford-Fulkerson. Para entenderlo en su totalidad primero debemos definir a la red residual $R(N, f)$, donde $N = (V, E, c)$ es una red y $f$ una función de flujo válida sobre la misma:
$$ R(N, f) = (V, E_R, w) $$