Xarxa de flux: diferència entre les revisions
Contingut suprimit Contingut afegit
m Canvi de camins augmentadors a camins augmentatius. |
m robot estandarditzant mida de les imatges, localitzant i simplificant codi |
||
Línia 20:
==Exemple==
[[Fitxer:network flow.png
A la dreta es pot veure una xarxa de flux amb una font <math>s</math>, un pou <math>t</math>, i quatre nodes més. El flux i la capacitat són <math>f/c</math>. 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 <math>s</math> fins <math>t</math> és 5, cosa que es pot veure molt fàcilment, ja que el flux total que surt de <math>s</math> és 5, que també és el flux que entra a <math>t</math>. No apareix o desapareix flux en cap dels altres nodes.
[[Fitxer:network flow residual.png
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 <math>(d,c)</math>. El flux no és el [[flux màxim]]. Hi ha capacitat disponible a través dels camins <math>(s,a,c,t)</math>, <math>(s,a,b,d,t)</math> i <math>(s,a,b,d,c,t)</math>,, que són, per tant, els camins augmentatius. La capacitat residual del primer camí és <math>\min(c(s,a)-f(s,a), c(a,c)-f(a,c), c(c,t)-f(c,t))</math><math>= \min(5-3, 3-2, 2-1) = \min(2, 1, 1) = 1</math>. S'ha de tenir en compte que el camí augmentatiu <math>(s,a,b,d,c,t)</math> no existeix a la xarxa original, però es pot cancel·lar el flux que ja hi passa en el sentit oposat.
|