Transportnät

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 december 2019; kontroller kräver 16 redigeringar .

I grafteorin är ett transportnätverk en riktad graf där varje kant har en icke-negativ kapacitet och flöde . Två hörn särskiljs: källa och sjunka så att alla andra hörn i nätverket ligger på vägen från till , medan . Transportnätet kan användas för att modellera till exempel vägtrafik. $G=(V,E)$ $(u,v)\i E$ $c(u,v)\geqslant 0$ $f(u,v)$ $s$ $t$ $s$ $t$ $s\neq t$

Ett heltalstransportnät är ett transportnät där alla kantkapaciteter är heltal.

Definitioner

Ett flödesnätverk är en riktad graf där $G(V,E),$

varje kant har en icke-negativ kapacitet uttryckt av en funktion (i vissa källor även ), så att värdet på funktionen för alla är noll. $\ (u,v)\i E$ ${\displaystyle c\colon V\times V\rightarrow \mathbb {R} _{+))$ ${\displaystyle c\colon E\rightarrow \mathbb {R} _{+))$ $e\not \in E$
två hörn väljs: källa ( källa ) och sjunka ( sänka ) , så att alla andra hörn i nätverket ligger på vägen från till , medan . $s$ $t$ $s$ $t$ $s\neq t$

Flöde (flöde) - en funktion (i vissa källor även ) med följande egenskaper: ${\displaystyle f\colon V\times V\rightarrow \mathbb {R} _{+))$ ${\displaystyle f\colon E\rightarrow \mathbb {R} _{+))$

Kapacitetsbegränsningar . Flödesvärdet för någon kant får inte överskrida dess kapacitet: $e\in E$ $0\leqslant f(e)\leqslant c(e).$
Skev symmetri. Flödet fråntillmåste vara motsatsen till flödet fråntill: $\u$ $\v$ $\v$ $\u$ $f(u,v)=-f(v,u).$
Flödesbevarande : för alla . $\sum _{v\in V}f((u,v))-\summa _{w\in V}f((w,u))={\begin{cases}|f|&, v=s\\-|f|&,v=t\\0&,v\neq s\land v\neq t\\\end{fall}}$ $\u\i V$

Värdet på flödet är summan av flödena från källan eller summan av flödena till diskbänken . $|f|=\summa _{v\in V}f(s,v)=\summa _{v\in V}f(v,t)$

Maxflödesproblemet är att hitta ett flödeså att flödets värde är maximalt, d.v.s. det finns ingen strömsådan att. $f$ $f^{*}$ $|f^{*}|>|f|$

Ett snitt (st cut) är ett par disjunkta uppsättningar så att och och . Det finns också en definition där ett snitt är en delmängd av kanter , där är en delmängd av hörn så att och . $(A, B)$ $V=A\ {\dot {\cup }}\ B$ $s\in A$ $t\i B$ ${\displaystyle \delta ^{+}(X)=\{(u,v)\i E\mid u\in X,\ v\notin X\))$ $X$ $s\in X$ $t\notin X$

Kapaciteten för en st cut är summan av kapaciteten för alla skärkanter: eller . $\sum _{e\in \delta ^{+}(X)}c(e)$ $\sum _{(u,v)\in E,u\in A,v\in B}c((u,v))$

Skärflödesvärdet är summan av flödesvärdena för alla skärkanter eller . Det överstiger inte genomströmningen av snittet, eftersom för alla . $\sum _{e\in \delta ^{+}(X)}f(e)$ $\sum _{(u,v)\in E,u\in A,v\in B}f((u,v))-\summa _{(u,v)\in E,u\ i A,v\in B}f((v,u))$ $f(e)\leqslant c(e)$ $e\in E$

Minsta snitt — ett snitt med minimal genomströmning.

Kantens restkapacitet (restkapacitet) - . Det är alltid icke-negativt på grund av bandbreddsbegränsningsvillkoret. $c_{f}((u,v))=c((u,v))-f((u,v))+f((v,u))$

Restnätverk är en graf , där är en uppsättning kanter med positiv restkapacitet. En vertex -till-vertex- väg kan finnas i det återstående nätverket , även om det inte finns i det ursprungliga nätverket. Detta händer när det finns en returväg i det ursprungliga nätet och flödet längs det är positivt. $G_{f}=(V,E_{f})$ ${\displaystyle E_{f))$ $u$ $v$ $(v,u)$

En förstärkande (resterande, kompletterande) väg (förstärkningsväg) är en väg i restnätet, där och Nedan bevisas att flödet är maximalt om och endast om det inte finns någon förstärkningsväg i restnätet. $(u_{1},u_{2},\dots ,u_{k})$ $u_{1}=s,$ $u_{k}=t,$ $c_{f}(u_{i},u_{i+1})>0.$

Egenskaper

Flödet genom varje skär är lika med summan av flödena från källan.
Bevis : låt det bli ett snitt (A,B). Betrakta summan av alla flöden från alla hörn som hör till A. Det är lika med

\summa _{{u\i A}}\summa _{{v\i A}}f(u,v)+\summa _{{u\i A}}\summa _{{v\in B} }f(u,v)

Den första av summorna för alla hörnpar (u, v) innehåller två termer f(u, v) och f(v, u) lika i absoluta värden och motsatta i tecken. Därför är denna summa noll. Den andra summan är flödet genom skärningen (A,B). Därför är summan av alla flöden från alla hörn som hör till A lika med flödet genom skärningen. Å andra sidan är summan av flöden från alla hörn, förutom s och t, lika med noll och . Därför är summan av alla flöden från alla hörn som hör till A lika med summan av flöden från s. Därför är flödet genom skärningen (A,B) lika med summan av flödena från s, vilket skulle bevisas. $t\notin A$

Summan av flödena från källan är lika med summan av flödena till diskbänken.
Bevis : Överväg ett snitt . Flödet genom detta snitt är lika med summan av flöden in i diskhon. Å andra sidan, enligt vad som just har bevisats, är flödet genom denna (liksom alla andra) skär lika med summan av flödena från källan. Teoremet har bevisats. $(V\setminus \{t\},\{t\})$

Maximalt flöde är positivt om och endast om det finns en väg från källan till sänkan längs kanter med positiv kapacitet.
Bevis : Låt en sådan väg P existera. Låt c vara minimikapaciteten för kanterna som hör till P. Låt flödet vara lika med c på alla kanter från P, och noll på alla andra kanter. Då är det totala flödet från källan lika med c, det vill säga det är positivt. Antag nu att det inte finns någon sådan väg, det vill säga att t inte kan nås från s längs kanter med positiv kapacitet. Låt A vara uppsättningen av hörn som kan nås från s längs sådana kanter, B vara uppsättningen av oåtkomliga. Sedan, eftersom , , då (A,B) är ett snitt. Dessutom finns det ingen kant (a, b) med positiv kapacitet så att , , annars skulle b vara nåbar från s. Därför är genomströmningen av sektionen (A,B) lika med noll, och följaktligen är flödet genom det alltid lika med noll. Därför är summan av flödena från källan alltid noll. $s\i A$ $t\i B$ $a\i A$ $b\i B$

Flödet är maximalt om och endast om det inte finns någon förstärkningsväg i restnätet. Bevis : Låt det finnas en förstärkningsväg i det resterande nätverket , och var minimum av restkapaciteten för kanterna som hör till , i det resterande nätverket. För alla par, öka med och minska med . Vi ökade det totala flödet från källan med , därför var det inte det maximala. Anta nu tvärtom att det inte finns någon sådan väg. Låt oss motsägelsefullt bevisa att flödet i det ursprungliga nätverket ger det maximala totala flödet från . Om så inte är fallet finns det ett flöde som ger ett större totalflöde från . Det är lätt att se att det är ett flöde i restnätet som ger ett positivt totalflöde från . Därför finns det i restnätverket en väg från källan till sänkan, det vill säga en förstärkande väg. Vi har en motsägelse. $P$ $c$ $P$ $(u,v)\i P$ $f(u,v)$ $c$ $f(v,u)$ $c$ $c$ $f$ $s$ $f'$ $s$ $f'-f$ $s$

Ford-Fulkerson-satsen . Värdet på det maximala flödet är lika med kapaciteten för den minsta sektionen.
Bevis : summan av flöden frånär lika med flödet genom varje snitt, inklusive det minsta, överstiger därför inte genomströmningen av det minsta snittet. Därför är det maximala flödet inte större än genomströmningen av minimisnittet. Det återstår att bevisa att han inte är mindre än henne. Låt flödet vara maximalt. Sedan, i restnätet, är diskbänken inte nåbar från källan. Låt vara uppsättningen av hörn som kan nås från källan i det återstående nätverket, som nå. Sedan, eftersom,, dåär ett snitt. Dessutom finns det i restnätet ingen kantmed positiv kapacitet så att,, annars skulle denkunna nås från. Därför, i det ursprungliga nätverket, är flödet längs en sådan kant lika med dess kapacitet, och följaktligen är flödet genom snittetlika med dess kapacitet. Men flödet genom varje skär är lika med det totala flödet från källan, vilket i detta fall är lika med det maximala flödet. Detta innebär att det maximala flödet är lika med snittets genomströmning, vilket inte är mindre än flödet för det minsta snittet. Teoremet har bevisats. $s$ $A$ $B$ $s\i A$ $t\i B$ $(A,B)$ $(a,b)$ $a\i A$ $b\i B$ $b$ $s$ $(A, B)$ $(A,B)$

Exempel

Här visas ett transportnätverk med en källa , en sänka och ytterligare fyra noder. Flöde och genomströmning är märkta respektive . Bandbredden från källan till diskbänken är 5, vilket är lätt att se, eftersom bandbredden från är 5, vilket också är i . $\s$ $\t$ $\f/c$ $\s$ $\t$

Restnätet för ovanstående flöde visas nedan. Observera att det finns en begränsande kapacitet för vissa kanter, medan den i det ursprungliga nätverket är noll. Till exempel revben . Detta flöde är inte maximalt. Det finns stigande vägar och . Resterande kapacitet för det första spåret . Förstärkningsvägen finns inte i källnätverket, men det är möjligt att skicka rätt flöde genom det. $\(d,c)$ $\(s,a,c,t)$ $\(s,a,b,d,t)$ $\(s,a,b,d,c,t)$ $\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$ $\(s,a,b,d,c,t)$

Applikation

Det vanligaste exemplet på att använda transportnät är att hitta det maximala flödet , vilket betyder det maximala totala flödet från till För att hitta det maximala flödet i nätet kan Ford-Fulkerson-algoritmen , Edmonds-Karp- algoritmen och andra användas. $s$ $t.$

I minimikostnadsflödesproblemet tilldelas varje kant en kostnad , kostnaden för att skicka flödet genom kanten . Uppgiften är att skicka en given mängd flöde från till med lägsta kostnad. $(u,v)$ $k(u,v)$ $f(u,v)$ $f(u,v)\cdot k(u,v)$ $s$ $t$

Se även

Litteratur

Thomas H. Kormen et al Algoritmer: konstruktion och analys = INTRODUKTION TILL ALGORITHMER. - 2:a uppl. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Länkar (engelska)

Problem med maximalt flöde
Maximalt flöde
Verkliga grafinstanser
Programvara, papper, testgrafer m.m.
Lösningar för nätverksflödesproblem (inte tillgänglig länk)
Programvara och papper för nätverksflödesproblem
Lemon C++-bibliotek med flera algoritmer för maximalt flöde och lägsta kostnadscirkulation