Strømningsnetværk

I grafteori er et strømningsnetværk (også kendt som et transportnetværk) en rettet graf, hvor hver kant har en kapacitet. Hver kant kan indeholde en strømning, der ikke må overstige kantens kapacitet. I operationsanalyse kaldes en rettet graf ofte et netværk. Ved hver knude skal strømningen opfylde, at mængden af strømning ind i knuden svarer til mængden af strømning ud af knuden, medmindre knuden er en kilde, som kun har udgående strøm, eller dræn, som kun har indgående strømning. Strømningsnetværk bruges til at modellere trafik i et computernetværk, cirkulation med krav, væsker i rør, strømme i et elektrisk kredsløb og mange andre situationer, hvor noget bevæger sig gennem et netværk af knudepunkter.

DefinitionRediger

Et netværk er en graf G = (V, E), hvor V er mængden af knuder, og E er mængden kanter, sammen med en ikke-negativ funktion c: E → ℝ, kaldet kapacitetsfunktionen . Uden tab af generalitet kan vi antage, at hvis (u, v) ∈ E, så tilhører (v, u) også E, idet vi for (v, u) ∉ E kan tilføje (v, u) til E med c(v, u) = 0 .

For et par af knuder s og t kaldes (G, c, s, t) et strømningsnetværk med kilde s og dræn t. [1]

Et strømningsnetværk tillader mange forskellige definitioner af strømningfunktioner. En strømningsfunktion modellerer nettostrømmen af enheder mellem par af knuder og bruges til at modellere spørgsmål som »hvad er det maksimale antal enheder, der kan sendes fra kilden til drænet?« Det enkleste eksempel på en strømningsfunktion kaldes en pseudostrømning.

En pseudostrømning er en funktion f : E → ℝ, der for hvert par u og v of knude opfylder:
  • Skævsymmetri : f (u, v) = −f (v, u) .
  • Kapacitetsbegrænsning : Strømningen på en kant kan ikke ikke overstige dens kapacitet: f (u, v) ≤ c(u, v) .

Givet en pseudostrømning f definerer vi den indgående nettostrømning i en knude v som summen af den strømning, der kommer ind i v . Overerskuddet er en funktion xf : V → ℝ defineret ved xf (u) = ∑vV f (v, u). Knuden u er aktiv, hvis xf (u) > 0, mangelfuld, hvis xf (u) < 0 og strømningsbevarende, hvis xf (u) = 0 .

Disse definitioner leder til to styrkelser af definitionen af pseudostrømning:

En forstrømning er en pseudostrømning, der for alle vV \{s } opfylder:
  • Ikke-mangelfulde strømninger : Nettostrømningen ind i hver knude er ikke-negativ, bortset fra kilden, der »producerer« strømning. Det vil sige: xf (v) ≥ 0 for alle vV \{s }.
En gørlig strømning, eller bare en strømning, er en pseudostrømning, der for alle vV \{s, t } opfylder
  • Strømningsbevaring : Nettostrømningenen ind i hver knude er 0, bortset fra kilden, der »producerer« strømningen, og drænet, der »forbruger« strømningen. Det vil sige: xf (v) = 0 for alle vV \{s, t }.


Værdien af en strømning f, betegnet | f |, er nettostrømmen ind i drænet t. Det vil sige | f | = xf (t) .

Relaterede begreberRediger

ResterRediger

En kants restkapacitet med hensyn til pseudostrømningen f, betegnet cf, er forskellen mellem kantens kapacitet og dens strømning, cf (e) = c(e) - f(e). Herfra defineres restnetværket (også kaldt restgrafen eller residualnetværket), betegnet Gf (V, Ef), som modellerer mængden af tilgængelig kapacitet på kanterne i G = (V, E). Mere formelt, givet et strømningsnetværk G, består restnetværket Gf  af knudemængden V, kantmængden Ef = {eV × V : cf (e) > 0} og kapacitetsfunktion cf .

Dette begreb bruges i Ford-Fulkersons algoritme, der beregner den maksimale strømning.

Læg mærke til, at der kan være en sti fra u til v i restnetværket, selvom der ikke er nogen sti fra u til v i det oprindelige netværk. Da strømme i modsatte retninger annulleres, er mindskning af strømmen fra v til u det samme som at øge strømmen fra u til v .

Forbedrende vejeRediger

En forstærkende vej er en vej (u1, u2, ..., uk) i restnetværket med u1 = s, uk = t og cf (ui, ui + 1) > 0 . En strømning f er en maksimal strømning, hvis og kun hvis der ikke er nogen forbedrende vej i restnetværket Gf .

Flere kilder og drænRediger

For at modellere et netværk med mere end en kilde, introduceres en overkilde til grafen. Hertil tilføjes en ny knude til netværket, som forbindes til hver af de oprindelige kilder med en kant af uendelig kapacitet. En lignende konstruktion til dræn kaldes en overdræn.

EksempelRediger

 
Et strømningsnetværk med strømning og kapaciteter

Til venstre ses et strømnigsnetværk med kilde s, dræn t og fire yderligere knuder. Strømningen og kapaciteten er angivet   . Bemærk, hvordan netværket opfylder skævsymmetri, kapacitetsbegrænsninger og strømningsbevaring. Den samlede strømning fra s til t er 5, hvilket let kan ved at den samlede udgående strømning fra s er 5, hvilket også er den indkommende strøm til t. Ingen strømning dukker op eller forsvinder i nogen af de andre knuder

 
Restnetværket for strømningsnetværket foroven, med de rettede restkapaciter på hver kant.

Nedenfor ses restnetværk for den givne strømning. Bemærk, hvordan der er positiv restkapacitet på nogle kanter, hvor den originale kapacitet er nul, for eksempel for kanten  . Denne strømning er ikke en maksimal strømning. Der er ledig kapacitet langs de forbedrende veje  ,   og  . Den første af disse vejes restkapacitet er   .   Bemærk, at så længe der findes en vej med en positiv restkapacitet, vil strømmen ikke være maksimal. Restkapaciteten for en vej er den mindste restkapacitet af vejens kanter.

ReferencerRediger

  1. ^ A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989

Yderligere læsningRediger