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[redigér | rediger kildetekst]

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 \to ℝ \infty$ , kaldet kapacitetsfunktionen . Uden tab af generalitet kan vi antage, at hvis $(u, v) \in E$ , så tilhører $(v, u)$ også $E$ , idet vi for $(v, u) \notin 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 \to ℝ

, 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) \leq 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 $x f : V \to ℝ$ defineret ved $x f (u) = \sum v \in V f (v, u)$ . Knuden $u$ er aktiv, hvis $x f (u) > 0$ , mangelfuld, hvis $x f (u) < 0$ og strømningsbevarende, hvis $x f (u) = 0$ .

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

En forstrømning er en pseudostrømning, der for alle

v ∈ V \{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: $x f (v) \geq 0$ for alle $v ∈ V \{s$ }.

En gørlig strømning, eller bare en strømning, er en pseudostrømning, der for alle

v ∈ V \{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: $x f (v) = 0$ for alle $v ∈ V \{s, t$ }.

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

Relaterede begreber[redigér | rediger kildetekst]

Rester[redigér | rediger kildetekst]

En kants restkapacitet med hensyn til pseudostrømningen $f$ , betegnet $c f$ , er forskellen mellem kantens kapacitet og dens strømning, $c f (e) = c (e) - f (e)$ . Herfra defineres restnetværket (også kaldt restgrafen eller residualnetværket), betegnet $G f (V, E f)$ , 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 $G f$ af knudemængden $V$ , kantmængden $E f = {e \in V \times V : c f (e) > 0}$ og kapacitetsfunktion $c f$ .

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 veje[redigér | rediger kildetekst]

En forstærkende vej er en vej $(u 1, u 2, ..., u k)$ i restnetværket med $u 1 = s$ , $u k = t$ og $c f (u i, u i + 1) > 0$ . En strømning $f$ er en maksimal strømning, hvis og kun hvis der ikke er nogen forbedrende vej i restnetværket $G f$ .

Flere kilder og dræn[redigér | rediger kildetekst]

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[redigér | rediger kildetekst]

Til venstre ses et strømnigsnetværk med kilde $s$ , dræn $t$ 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 $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

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.

Referencer[redigér | rediger kildetekst]

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

Yderligere læsning[redigér | rediger kildetekst]

George T. Heineman; Gary Pollice (2008). "Chapter 8:Network Flow Algorithms". Algorithms in a Nutshell. Oreilly Media. s. 226-250. ISBN 978-0-596-51624-6.
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X.{{cite book}}: CS1-vedligeholdelse: Flere navne: authors list (link)
Bollobás, Béla (1979). Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag. ISBN 3-540-90399-2.
Chartrand, Gary & Oellermann, Ortrud R. (1993). Applied and Algorithmic Graph Theory. New York: McGraw-Hill. ISBN 0-07-557101-3.{{cite book}}: CS1-vedligeholdelse: Flere navne: authors list (link)
Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. ISBN 0-914894-21-8.
Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge: Cambridge University Press. ISBN 0-521-28881-9.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). "26". Introduction to Algorithms (2nd udgave). MIT Press and McGraw-Hill. s. 696-697. ISBN 0-262-03293-7.{{cite book}}: CS1-vedligeholdelse: Flere navne: authors list (link)

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

[1]