Xarxa de flux: diferència entre les revisions

Contingut suprimit Contingut afegit
m Robot: Reemplaçament automàtic de text (-[[File: +[[Fitxer:)
Línia 20:
==Exemple==
 
[[FileFitxer:network flow.png|right|frame|100px|Una xarxa de flux amb el seu flux i capacitat]]
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, doncs 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.
 
[[FileFitxer:network flow residual.png|right|frame|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 <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 augmentadors. 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í augmentador <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.