Xarxa de flux

En teoria de grafs, una xarxa de flux és un graf dirigit en que cada aresta està ponderada amb un flux i una capacitat. La suma del flux d'una aresta no pot ser superior a la seva capacitat. Moltes vegades s'anomena al graf dirigit, xarxa, als vèrtexs, nodes, i a les arestes, arcs. La suma de flux que entra en un node ha de ser igual a la suma de flux que en surt, a excepció de les fonts, que tenen més flux sortint, o els pous, que tenen més flux entrant. Una xarxa pot ser utilitzada per modelitzar el tràfic en un sistema de carreteres, líquids dins de canonades, corrents en un circuit elèctric, o qualsevol cosa que viatgi a través d'una xarxa de nodes.

Descripció matemàtica

$\ G(V,E)$ és un graf dirigit finit on cada aresta $\ (u,v) \in E$ té una capacitat real i no negativa $\ c(u,v)$. Si $\ (u, v) \not \in E$, assumim que $\ c(u, v) = 0$. Distingim dos vèrtexs: una font $\ s$ i un pou $\ t$. Una xarxa de flux és una funció $\ f:V \times V \rightarrow \mathbb{R}$ amb les següents tres propietats per tots els nodes $\ u$ i $\ v$:

Restricció de capacitat:	$\ f(u,v) \le c(u,v)$. El flux que travessa una aresta no pot excedir la seva capacitat.
Antisimetria:	$\ f(u,v) = - f(v,u)$. El flux des de $\ u$ fins $\ v$ ha de ser oposat al flux des de $\ v$ fins $\ u$ (veure exemple).
Conservació del flux:	$\ \sum_{w \in V} f(u,w) = 0$, llevat que $\ u=s$ o que $\ w=t$. El flux que travessa un node és zero, a excepció de les fonts, que "produeixen" flux, i els pous, que "consumeixen" flux.

Noteu que $\ f(u,v)$ és el flux des de $\ u$ fins $\ v$. Si el graf representa una xarxa física, i si per aquesta hi circula un flux real de, per exemple, 4 unitats des de $\ u$ fins $\ v$, i un flux real de 3 unitats des de $\ v$ fins $\ u$, tenim $\ f(u,v)=1$ i $\ f(v,u)=-1$.

La capacitat residual d'una aresta és $\ c_f(u,v) = c(u,v) - f(u,v)$. Això defineix tota una nova xarxa residual, denominada $\ G_f(V,E_f)$, que ens dóna els valors de les capacitats disponibles. Considera que hi pot haver una aresta des de $\ u$ fins $\ v$ en la xarxa residual, però no haver-la en la xarxa original. El flux en direccions oposades es cancel·la, doncs "decrementar" el flux des de $\ v$ fins $\ u$ és el mateix que "incrementar" el flux des de $\ u$ fins $\ v$. Un camí no saturat és un camí $\ (u_1,u_2,\dots,u_k)$ dins la xarxa residual, on $\ u_1=s$, $\ u_k=t$, i $\ c_f(u_i, u_{i+1}) > 0$. Una xarxa té el màxim flux si i sols si tots els camins d'u a v estan saturats dins la xarxa residual.

Exemple

Una xarxa de flux amb el seu flux i capacitat

A la dreta es pot veure una xarxa de flux amb una font $s$, un pou $t$, i quatre nodes més. El flux i la capacitat són $f/c$. La xarxa respecta les tres restriccions que havíem definit: la constant de capacitat, la antisimetria i la conservació del flux. La suma total de flux des de $s$ fins $t$ és 5, cosa que es pot veure molt fàcilment, doncs el flux total que surt de $s$ és 5, que també és el flux que entra a $t$. No apareix o desapareix flux en cap dels altres nodes.

Xarxa residual de la xarxa de flux de més amunt

Més avall veiem la xarxa residual per al flux donat. Hi ha arestes on la capacitat residual és positiva, quan en les arestes originals és zero, per exemple en l'aresta $(d,c)$. El flux no és el flux màxim. Hi ha capacitat disponible a través dels camins $(s,a,c,t)$, $(s,a,b,d,t)$ i $(s,a,b,d,c,t)$,, que són, per tant, els camins augmentadors. La capacitat residual del primer camí és $\min(c(s,a)-f(s,a), c(a,c)-f(a,c), c(c,t)-f(c,t))$$= \min(5-3, 3-2, 2-1) = \min(2, 1, 1) = 1$. S'ha de tenir en compte que el camí augmentador $(s,a,b,d,c,t)$ no existeix a la xarxa original, però es pot cancel·lar el flux que ja hi passa en el sentit oposat.

Problemes amb xarxes de flux

El més simple i comú dels problemes de xarxes de flux és trobar l'anomenat flux màxim, que és la quantitat màxima de flux que es pot passar des de la font fins el pou.

Enllaços externs

• Maximum Flow Problem
• Maximum Flow
• Real graph instances
• Software, papers, test graphs, etc.
• Solutions for network flow problems
• Software and papers for network flow problems
• Lemon C++ library with several maximum flow and minimum cost circulation algorithms
• QuickGraph, graph data structures and algorithms for .Net