Maximum Flow calcula el flujo máximo desde un nodo fuente s hasta un nodo sumidero t en una red de flujo con capacidades en las aristas.

Es uno de los problemas más importantes en optimización de redes con aplicaciones en routing, asignación de recursos, y matching bipartito.

Red de Flujo

Componentes:

• Source (s): nodo origen.
• Sink (t): nodo destino.
• Capacities: cada arista (u,v) tiene capacidad c(u,v).
• Flows: f(u,v) satisface:
  • 0 ≤ f(u,v) ≤ c(u,v) (capacity constraint)
  • f(u,v) = -f(v,u) (skew symmetry)
  • Σ f(u,v) = 0 para todo u excepto s y t (conservation)

Ford-Fulkerson Method

flow = 0
mientras exista augmenting path de s a t en residual graph:
  bottleneck = minimum residual capacity en el path
  flow += bottleneck
  actualiza residual capacities

Augmenting path: camino de s a t en el residual graph donde cada arista tiene capacidad residual > 0.

Residual Graph

Para cada arista (u,v) con capacidad c y flujo f:

• Arista forward (u,v) con capacidad residual c - f.
• Arista backward (v,u) con capacidad residual f (permite “deshacer” flujo).

Min-Cut Max-Flow Theorem

El flujo máximo desde s hasta t es igual a la capacidad mínima del cut (corte) que separa s de t.

Edmonds-Karp

Usa BFS para encontrar augmenting paths (el más corto en términos de aristas). Complejidad: O(VE²).

Ejemplo

Red:

s → A (capacity 3)
s → B (capacity 2)
A → B (capacity 1)
A → t (capacity 2)
B → t (capacity 3)

Augmenting path 1: s-A-t con bottleneck 2. Augmenting path 2: s-B-t con bottleneck 2. Flujo máximo = 4.

Comparación

Aplicaciones

• Network routing — máximo throughput
• Bipartite matching — máximo número de parejas
• Image segmentation — graph cut
• Scheduling — asignación de recursos
• Enseñanza — introduce augmenting paths y min-cut theorem

Trayectoria de Práctica

1. Implementa Edmonds-Karp; traza el ejemplo paso a paso.
2. Investiga Dinic: ¿por qué blocking flow mejora?
3. Investiga Push-Relabel: ¿cómo funciona gap heuristic?
4. Aplica max-flow a bipartite matching.
5. Investiga min-cut: ¿cómo recuperas el cut desde el residual graph?