Obre el menú principal

Xarxa de flux

graf dirigit en què cada aresta està ponderada amb un flux i una capacitat

En teoria de grafs, una xarxa de flux és un graf dirigit en què 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.

Contingut

Descripció matemàticaModifica

  és un graf dirigit finit on cada aresta   té una capacitat real i no negativa  . Si  , assumim que  . Distingim dos vèrtexs: una font   i un pou  . Una xarxa de flux és una funció   amb les següents tres propietats per tots els nodes   i  :

Restricció de capacitat:  . El flux que travessa una aresta no pot excedir la seva capacitat.
Antisimetria:  . El flux des de   fins   ha de ser oposat al flux des de   fins   (vegeu exemple).
Conservació del flux:  , llevat que   o que  . El flux que travessa un node és zero, a excepció de les fonts, que "produeixen" flux, i els pous, que "consumeixen" flux.

Noteu que   és el flux des de   fins  . Si el graf representa una xarxa física, i si per aquesta hi circula un flux real de, per exemple, 4 unitats des de   fins  , i un flux real de 3 unitats des de   fins  , tenim   i  .

La capacitat residual d'una aresta és  . Això defineix tota una nova xarxa residual, denominada  , que ens dóna els valors de les capacitats disponibles. Considera que hi pot haver una aresta des de   fins   en la xarxa residual, però no haver-la en la xarxa original. El flux en direccions oposades es cancel·la, ja que "decrementar" el flux des de   fins   és el mateix que "incrementar" el flux des de   fins  . Un camí no saturat és un camí   dins la xarxa residual, on  ,  , i  . Una xarxa té el màxim flux si i sols si tots els camins d'u a v estan saturats dins la xarxa residual.

ExempleModifica

 
Una xarxa de flux amb el seu flux i capacitat

A la dreta es pot veure una xarxa de flux amb una font  , un pou  , i quatre nodes més. El flux i la capacitat són  . 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   fins   és 5, cosa que es pot veure molt fàcilment, ja que el flux total que surt de   és 5, que també és el flux que entra a  . 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  . El flux no és el flux màxim. Hi ha capacitat disponible a través dels camins  ,   i  ,, que són, per tant, els camins augmentatius. La capacitat residual del primer camí és   . S'ha de tenir en compte que el camí augmentatiu   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 fluxModifica

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 al pou.

Enllaços externsModifica