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
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}}
[[Categoria:Teoria de grafs]]
[[Categoria:Investigació operativa]]
|