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.

Definition

Et netværk er en graf Skabelon:Math, hvor Skabelon:Math er mængden af knuder, og Skabelon:Math er mængden kanter, sammen med en ikke-negativ funktion Skabelon:Math, kaldet kapacitetsfunktionen . Uden tab af generalitet kan vi antage, at hvis Skabelon:Math, så tilhører Skabelon:Math også Skabelon:Mvar, idet vi for Skabelon:Math kan tilføje Skabelon:Math til E med Skabelon:Math .

For et par af knuder Skabelon:Mvar og Skabelon:Mvar kaldes Skabelon:Math et strømningsnetværk med kilde s og dræn t.

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 Skabelon:Math, der for hvert par Skabelon:Mvar og Skabelon:Mvar of knude opfylder:

• Skævsymmetri : Skabelon:Math .
• Kapacitetsbegrænsning : Strømningen på en kant kan ikke ikke overstige dens kapacitet: Skabelon:Math .

Givet en pseudostrømning Skabelon:Mvar definerer vi den indgående nettostrømning i en knude Skabelon:Mvar som summen af den strømning, der kommer ind i Skabelon:Mvar . Overerskuddet er en funktion Skabelon:Math defineret ved Skabelon:Math. Knuden Skabelon:Mvar er aktiv, hvis Skabelon:Math, mangelfuld, hvis Skabelon:Math og strømningsbevarende, hvis Skabelon:Math .

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

En forstrømning er en pseudostrømning, der for alle Skabelon:Math } opfylder:

• Ikke-mangelfulde strømninger : Nettostrømningen ind i hver knude er ikke-negativ, bortset fra kilden, der »producerer« strømning. Det vil sige: Skabelon:Math for alle Skabelon:Math }.

En gørlig strømning, eller bare en strømning, er en pseudostrømning, der for alle Skabelon:Math } 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: Skabelon:Math for alle Skabelon:Math }.

Værdien af en strømning Skabelon:Mvar, betegnet Skabelon:Math, er nettostrømmen ind i drænet Skabelon:Mvar. Det vil sige Skabelon:Math .

Relaterede begreber

Rester

En kants restkapacitet med hensyn til pseudostrømningen Skabelon:Mvar, betegnet Skabelon:Math, er forskellen mellem kantens kapacitet og dens strømning, Skabelon:Math. Herfra defineres restnetværket (også kaldt restgrafen eller residualnetværket), betegnet Skabelon:Math, som modellerer mængden af tilgængelig kapacitet på kanterne i Skabelon:Math. Mere formelt, givet et strømningsnetværk Skabelon:Mvar, består restnetværket Skabelon:Math  af knudemængden Skabelon:Mvar, kantmængden Skabelon:Math og kapacitetsfunktion Skabelon:Math .

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 Skabelon:Mvar til Skabelon:Mvar i restnetværket, selvom der ikke er nogen sti fra Skabelon:Mvar til Skabelon:Mvar i det oprindelige netværk. Da strømme i modsatte retninger annulleres, er mindskning af strømmen fra Skabelon:Mvar til Skabelon:Mvar det samme som at øge strømmen fra Skabelon:Mvar til Skabelon:Mvar .

Forbedrende veje

En forstærkende vej er en vej Skabelon:Math i restnetværket med Skabelon:Math, Skabelon:Math og Skabelon:Math . En strømning Skabelon:Math er en maksimal strømning, hvis og kun hvis der ikke er nogen forbedrende vej i restnetværket Skabelon:Math .

Flere kilder og dræn

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.

Eksempel

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

Til venstre ses et strømnigsnetværk med kilde Skabelon:Mvar, dræn Skabelon:Mvar og fire yderligere knuder. Strømningen og kapaciteten er angivet $f/c$ . Bemærk, hvordan netværket opfylder skævsymmetri, kapacitetsbegrænsninger og strømningsbevaring. Den samlede strømning fra Skabelon:Mvar til Skabelon:Mvar er 5, hvilket let kan ved at den samlede udgående strømning fra Skabelon:Mvar er 5, hvilket også er den indkommende strøm til Skabelon:Mvar. 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 $(d,c)$. Denne strømning er ikke en maksimal strømning. Der er ledig kapacitet langs de forbedrende veje $(s,a,c,t)$, $(s,a,b,d,t)$ og $(s,a,b,d,c,t)$. Den første af disse vejes restkapacitet er $\min (c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))$$=\min (5-3,3-2,2-1)=\min (2,1,1)=1$.   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.

Yderligere læsning

• Skabelon:Kilde bog
• Skabelon:Kilde bog
• Skabelon:Kilde bog
• Skabelon:Kilde bog
• Skabelon:Kilde bog
• Skabelon:Kilde bog
• Skabelon:Kilde bog