Közlekedési hálózat

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. december 24-én felülvizsgált verziótól ; az ellenőrzések 16 szerkesztést igényelnek .

A gráfelméletben a szállítási hálózat olyan irányított gráf , amelyben minden élnek nemnegatív kapacitása és áramlása van . Két csúcsot különböztetünk meg: a forrást és a nyelőt úgy, hogy a hálózat bármely más csúcsa a -tól -ig tartó úton fekszik , míg . A közlekedési hálózat felhasználható például a közúti forgalom modellezésére. $G=(V,E)$ $(u,v)\in E$ $c(u,v)\geqslant 0$ $f(u,v)$ $s$ $t$ $s$ $t$ $s\neq t$

Az egész számok szállítási hálózata olyan szállítási hálózat, amelyben az összes élkapacitás egész szám.

Definíciók

Az áramlási hálózat egy irányított gráf , amelyben $G(V,E),$

minden élnek van egy nem-negatív kapacitása, amelyet egy függvény fejez ki (egyes forrásokban is ), úgy, hogy bármelyik esetén a függvény értéke nulla. $\ (u,v)\in E$ ${\displaystyle c\colon V\times V\rightarrow \mathbb {R} _{+))$ ${\displaystyle c\colon E\rightarrow \mathbb {R} _{+))$ $e\not \in E$
két csúcs van kiválasztva: forrás ( forrás ) és sink ( sink ) úgy, hogy a hálózat bármely más csúcsa a -tól -ig tartó úton van , míg a . $s$ $t$ $s$ $t$ $s\neq t$

Flow (flow) - egy függvény (egyes forrásokban is ), a következő tulajdonságokkal: ${\displaystyle f\colon V\times V\rightarrow \mathbb {R} _{+))$ ${\displaystyle f\colon E\rightarrow \mathbb {R} _{+))$

Kapacitási korlátok. Egyetlen él áramlási értéke sem haladhatja meg a kapacitását: $e\in E$ $0\leqslant f(e)\leqslant c(e).$
Ferde szimmetria. Az innen irányú áramlásnakellentétesnekkell lennie a innen irányúáramlással: $\u$ $\v$ $\v$ $\u$ $f(u,v)=-f(v,u).$
Áramlás megőrzése: mindenkinek . $\sum _{v\in V}f((u,v))-\sum _{w\in V}f((w,u))={\begin{cases}|f|&, v=s\\-|f|&,v=t\\0&,v\neq s\land v\neq t\\\end{cases}}$ $\u\in V$

Az áramlás értéke a forrásból származó áramlások összege vagy a nyelőhöz vezető áramlások összege . $|f|=\sum _{v\in V}f(s,v)=\sum _{v\in V}f(v,t)$

A maximális áramlási probléma az, hogy olyan áramlást találjunk, amelynek az áramlás értéke maximális, azaz. nincs olyan patak, hogy. $f$ $f^{*}$ $|f^{*}|>|f|$

A vágás (st cut) olyan diszjunkt halmazpár , amelyből és és . Létezik olyan definíció is, ahol a vágás az élek részhalmaza , ahol a csúcsok egy részhalmaza úgy, hogy és . $(A, B)$ $V=A\ {\pont {\cup }}\ B$ $s\in A$ $t\ in B$ ${\displaystyle \delta ^{+}(X)=\{(u,v)\in E\mid u\in X,\ v\notin X\))$ $x$ $s\in X$ $t\notin X$

Egy st vágás kapacitása az összes vágott él kapacitásának összege: vagy . $\sum _{e\in \delta ^{+}(X)}c(e)$ $\sum _{(u,v)\in E,u\in A,v\in B}c((u,v))$

A vágott áramlási érték az összes vágott él áramlási értékeinek összege vagy . Nem haladja meg a vágás áteresztőképességét, mert minden . $\sum _{e\in \delta ^{+}(X)}f(e)$ $\sum _{(u,v)\in E,u\in A,v\in B}f((u,v))-\sum _{(u,v)\in E,u\ A,v\in B}f((v,u))$ $f(e)\leqslant c(e)$ $e\in E$

Minimális vágás – minimális áteresztőképességű vágás.

Az él maradék kapacitása (maradék kapacitás) - . A sávszélesség korlátozási feltétel miatt mindig nem negatív. $c_{f}((u,v))=c((u,v))-f((u,v))+f((v,u))$

A maradék hálózat egy gráf , ahol pozitív maradék kapacitású élek halmaza. Egy csúcspontok közötti útvonal létezhet a maradék hálózatban , még akkor is, ha az eredeti hálózatban nem létezik. Ez akkor fordul elő, ha az eredeti hálózatban van visszaút, és az áramlás pozitív. $G_{f}=(V,E_{f})$ ${\displaystyle E_{f))$ $u$ $v$ $(v,u)$

A kiegészítõ (maradék, kiegészítõ) út (augmenting path) egy olyan út a maradék hálózatban, ahol és Az alábbiakban bebizonyosodik, hogy az áramlás akkor és csak akkor maximális, ha a maradék hálózatban nincs kiegészítõ út. $(u_{1},u_{2},\dots ,u_{k})$ $u_{1}=s,$ $u_{k}=t,$ $c_{f}(u_{i},u_{i+1})>0.$

Tulajdonságok

Az áramlás bármely vágáson egyenlő a forrásból érkező áramlások összegével.
Bizonyítás : legyen vágás (A,B). Tekintsük az A-hoz tartozó összes csúcsból származó áramlások összegét. Egyenlő

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

Bármely csúcspár (u, v) összege közül az első két olyan f(u, v) és f(v, u) tagot tartalmaz, amelyek abszolút értékűek, és ellentétes előjelűek. Ezért ez az összeg nulla. A második összeg az áramlás a vágáson (A,B). Ezért az A-hoz tartozó összes csúcsból származó összes áramlás összege egyenlő a vágáson áthaladó áramlással. Másrészt az s és t kivételével bármely csúcsból származó áramlások összege egyenlő nullával és . Ezért az A-hoz tartozó összes csúcsból származó összes áramlás összege egyenlő az s-ből származó áramlások összegével. Ezért az (A,B) vágáson áthaladó áramlás egyenlő az s-ből származó áramlások összegével, amit igazolni kellett. $t\nem A$

A forrásból származó áramlások összege megegyezik a nyelőhöz vezető áramlások összegével.
Bizonyíték : Vegyünk egy vágást . Az ezen a vágáson áthaladó áramlás egyenlő a mosogatóba irányuló áramlások összegével. Másrészt az imént bebizonyítottak szerint ezen (és bármely más) vágáson átmenő áramlás egyenlő a forrásból érkező áramlások összegével. A tétel bizonyítást nyert. $(V\setminus \{t\},\{t\})$

A maximális áramlás akkor és csak akkor pozitív, ha a forrástól a nyelőig pozitív kapacitású élek mentén van út.
Bizonyítás : Legyen egy ilyen P út. Legyen c a P-hez tartozó élek minimális kapacitása. Legyen az áramlás egyenlő c-vel P-ből minden élen, és nulla az összes többi élen. Ekkor a forrásból származó teljes áramlás egyenlő c-vel, azaz pozitív. Most tegyük fel, hogy nincs ilyen út, vagyis t nem érhető el s-ből pozitív kapacitású élek mentén. Legyen A az s-ből elérhető csúcsok halmaza az ilyen élek mentén, B pedig az elérhetetlenek halmaza. Ekkor, mivel , , akkor (A,B) egy vágás. Ezenkívül nincs olyan pozitív kapacitású él (a, b), amelyre , , ellenkező esetben b elérhető lenne s-ből. Ezért az (A,B) szakasz áteresztőképessége nulla, így a rajta átfolyó áramlás mindig egyenlő nullával. Ezért a forrásból származó áramlások összege mindig nulla. $s\in A$ $t\ in B$ $a\in A$ $b\in B$

Az áramlás akkor és csak akkor maximális, ha nincs bővítő út a maradék hálózatban. Bizonyítás : Legyen a maradék hálózatban egy növelő út , és legyen a maradék hálózatban a -hoz tartozó élek maradék kapacitásának minimuma . Minden pár esetén növelje és csökkentse -kal . A forrásból származó teljes áramlást -val növeltük , ezért nem volt a maximum. Éppen ellenkezőleg, tegyük fel, hogy nincs ilyen út. Bizonyítsuk be ellentmondással, hogy az eredeti hálózat áramlása adja a maximális teljes áramlást -ból . Ha nem ez a helyzet, akkor van egy áramlás , amely nagyobb teljes áramlást biztosít innen . Könnyen belátható, hogy ez egy olyan áramlás a maradék hálózatban, amely pozitív teljes áramlást biztosít -ból . Ezért a maradék hálózatban van egy út a forrástól a nyelőig, vagyis egy bővítő út. Van egy ellentmondásunk. $P$ $c$ $P$ $(u,v)\in P$ $f(u,v)$ $c$ $f(v,u)$ $c$ $c$ $f$ $s$ $f'$ $s$ $f'-f$ $s$

A Ford-Fulkerson tétel . A maximális térfogatáram értéke megegyezik a minimális szakasz kapacitásával.
Bizonyítás : az innen érkező áramlások összegemegegyezik bármely vágáson keresztüli áramlással, beleértve a minimálisat is, ezért nem haladja meg a minimális vágás áteresztőképességét. Ezért a maximális áramlás nem nagyobb, mint a minimális vágás áteresztőképessége. Be kell bizonyítani, hogy nem kevesebb, mint ő. Legyen maximális az áramlás. Ekkor a maradék hálózatban a nyelő nem érhető el a forrásból. Legyen a maradék hálózatban a forrásból elérhető csúcsok halmaza, amelyek elérhetetlenek. Akkor, mivel,, akkoregy vágás. Ráadásul a maradék hálózatban nincs olyanpozitív kapacitású él, amely,, ellenkezőesetben elérhető. Ezért az eredeti hálózatban bármely ilyen él mentén az áramlás megegyezik a kapacitásával, és így a vágáson áthaladó áramlásegyenlő a kapacitásával. De az áramlás bármely vágáson megegyezik a forrás teljes áramlásával, amely ebben az esetben egyenlő a maximális áramlással. Ez azt jelenti, hogy a maximális áramlás egyenlő a vágás áteresztőképességével, amely nem kisebb, mint a minimális vágás áteresztőképessége. A tétel bizonyítást nyert. $s$ $A$ $B$ $s\in A$ $t\ in B$ ${\megjelenítési stílus (A,B)}$ $(a,b)$ $a\in A$ $b\in B$ $b$ $s$ $(A, B)$ ${\megjelenítési stílus (A,B)}$

Példa

Itt látható egy szállítási hálózat egy forrással , egy nyelővel és négy további csomóponttal. Az áramlás és az áteresztőképesség rendre meg van jelölve . A sávszélesség a forrástól a nyelőig 5, ami jól látható, mivel a sávszélesség 5, ami szintén benne van . $\s$ $\t$ $\f/c$ $\s$ $\t$

A fenti áramlás maradék hálózata az alábbiakban látható. Ne feledje, hogy bizonyos éleknél korlátozott a kapacitás, míg az eredeti hálózatban ez nulla. Például borda . Ez az áramlás nem maximális. Vannak növekvő útvonalak , és . Az első vágány maradék kapacitása . A kibővítő útvonal nem létezik a forráshálózatban, de a megfelelő áramlást át lehet vezetni rajta. $\(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)$

Alkalmazás

A közlekedési hálózatok használatának legáltalánosabb példája a maximális áramlás megkeresése , ami a maximális teljes áramlást jelenti től ig A maximális áramlás meghatározásához a hálózatban a Ford-Fulkerson algoritmus , az Edmonds-Karp algoritmus és mások használhatók. $s$ $t.$

A minimális költségű áramlási probléma esetén minden élhez hozzá van rendelve egy költség , az áramlás a szélen keresztül történő elküldésének költsége . A feladat az, hogy a legalacsonyabb költséggel egy adott mennyiségű áramlást küldjön től ig . $(u,v)$ $k(u,v)$ $f(u,v)$ $f(u,v)\cdot k(u,v)$ $s$ $t$

Lásd még

Irodalom

Thomas H. Kormen et al. Algoritmusok: konstrukció és elemzés = BEVEZETÉS AZ ALGORITMUSOKBA. - 2. kiadás - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Linkek (angol)

Maximális áramlási probléma
Maximális áramlás
Valós gráfpéldányok
Szoftver, papírok, tesztgrafikonok stb.
Megoldások a hálózati áramlási problémákra (nem elérhető hivatkozás)
Szoftverek és papírok a hálózati áramlási problémákhoz
Lemon C++ könyvtár számos maximális áramlási és minimális költségű cirkulációs algoritmussal