Xarxa de flux: diferència entre les revisions

Contingut suprimit Contingut afegit
m r2.7.1) (Robot afegeix: hy:Հոսքային ցանց
m neteja, replaced: desde → des de AWB
Línia 14:
|}
 
Noteu que <math>\ f(u,v)</math> és el flux des de <math>\ u</math> fins <math>\ v</math>. Si el graf representa una xarxa física, i si per aquesta hi circula un flux real de, per exemple, 4 unitats des de <math>\ u</math> fins <math>\ v</math>, i un flux real de 3 unitats desdedes de <math>\ v</math> fins <math>\ u</math>, tenim <math>\ f(u,v)=1</math> i <math>\ f(v,u)=-1</math>.
 
La '''capacitat residual''' d'una aresta és <math>\ c_f(u,v) = c(u,v) - f(u,v)</math>. Això defineix tota una nova '''xarxa residual''', denominada <math>\ G_f(V,E_f)</math>, que ens dóna els valors de les capacitats ''disponibles''. Considera que hi pot haver una aresta des de <math>\ u</math> fins <math>\ v</math> 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 <math>\ v</math> fins <math>\ u</math> és el mateix que "incrementar" el flux des de <math>\ u</math> fins <math>\ v</math>. Un '''camí no saturat''' és un camí <math>\ (u_1,u_2,\dots,u_k)</math> dins la xarxa residual, on <math>\ u_1=s</math>, <math>\ u_k=t</math>, i <math>\ c_f(u_i, u_{i+1}) > 0</math>. Una xarxa té el màxim flux si i sols si tots els camins d'''u'' a ''v'' estan saturats dins la xarxa residual.
Línia 40:
* [http://quickgraph.codeplex.com/ QuickGraph], graph data structures and algorithms for .Net
 
<!--ORDENA generat per bot-->
 
{{ORDENA:Xarxa De Flux}} <!--ORDENA generat per bot-->
[[Categoria:Teoria de grafs]]
[[Categoria:Investigació operativa]]