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 , hvor  er mængden af knuder, og  er mængden kanter, sammen med en ikke-negativ funktion , kaldet kapacitetsfunktionen . Uden tab af generalitet kan vi antage, at hvis , så tilhører  også , idet vi for  kan tilføje  til E med  . 

For et par af knuder  og  kaldes  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 , der for hvert par  og  of knude opfylder: 
 Skævsymmetri :  . 
 Kapacitetsbegrænsning : Strømningen på en kant kan ikke  ikke overstige dens kapacitet:  .  

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

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

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

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

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

Relaterede begreber

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

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

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

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 

Til venstre ses et strømnigsnetværk med kilde , dræn  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  til  er 5, hvilket let kan ved at den samlede udgående strømning fra  er 5, hvilket også er den indkommende strøm til . Ingen strømning dukker op eller forsvinder i nogen af de andre knuder 

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.

Referencer

Yderligere læsning 

 
 
 
 
 
 
 

Grafteori