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. A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989

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 left|thumb|332x332px| Et strømningsnetværk med strømning og kapaciteter 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 left|thumb|332x332px| 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.

Referencer

Yderligere læsning

Kategori:Grafteori