Problema del flux màxim

En optimització i teoria de grafs, el problema de flux màxim serveix per trobar la quantitat màxima de flux que pot passar per una xarxa de flux, des d'una sola font fins a un sol pou.

El problema de flux màxim pot ser vist com un cas especial d'altres problemes de xarxes més complexes, com ara el problema de circulació. El valor màxim d'un flux s-t és igual a la capacitat mínima d'un tall s-t a la xarxa, tal com demostra el teorema de flux màxim tall mínim.

Definició matemàtica

Sigui $\scriptstyle N=(V,E)$ una xarxa en què els vèrtexs $\scriptstyle s,t\in V$ són la font i el pou de $\scriptstyle N$, respectivament.

La capacitat d'una aresta ve donada per la funció $\scriptstyle c:E\to \mathbb {R} ^{+}$, denominada $\scriptstyle c_{uv}$ o $\scriptstyle c(u,v)$. Representa la quantitat màxima de flux que pot passar a través de l'aresta.

El flux ve donat per la funció $\scriptstyle f:E\to \mathbb {R} ^{+}$, denominat $\scriptstyle f_{uv}$ o $\scriptstyle f(u,v)$, i subjecte a les següents restriccions:

1. $\scriptstyle f_{uv}\leq c_{uv}$, per cada $\scriptstyle (u,v)\in E$ (restricció de capacitat)

2. $\scriptstyle \sum _{u:(u,v)\in E}f_{uv}=\sum _{u:(v,u)\in E}f_{vu}$, per cada $\scriptstyle v\in V\setminus \{s,t\}$ (conservació del flux)

El valor del flux es defineix com $\scriptstyle |f|=\sum _{v\in V}f_{sv}$, on $\scriptstyle s$ és la font de $\scriptstyle N$. Representa la suma total de flux que passa des de la font fins al pou.

El problema de flux màxim pretén maximitzar $\scriptstyle |f|$, és a dir, enviar tant flux com sigui possible des de $\scriptstyle s$ fins $\scriptstyle t$.