Dopravní síť

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. prosince 2019; kontroly vyžadují 16 úprav .

V teorii grafů je dopravní síť orientovaný graf , ve kterém má každá hrana nezápornou kapacitu a tok . Rozlišují se dva vrcholy: source a sink tak, že jakýkoli jiný vrchol sítě leží na cestě od do , zatímco . Dopravní síť lze využít k modelování např. silniční dopravy. $G=(V,E)$ $(u,v)\v E$ $c(u,v)\geqslant 0$ $f(u,v)$ $s$ $t$ $s$ $t$ $s\neq t$

Celočíselná transportní síť je transportní síť, ve které jsou všechny okrajové kapacity celá čísla.

Definice

Síť toků je orientovaný graf , ve kterém $G(V,E),$

každá hrana má nezápornou kapacitu vyjádřenou funkcí (v některých zdrojích také ), takže pro kteroukoli je hodnota funkce nulová. $\ (u,v)\v E$ ${\displaystyle c\colon V\times V\rightarrow \mathbb {R} _{+))$ ${\displaystyle c\colon E\rightarrow \mathbb {R} _{+))$ $e\not \in E$
jsou vybrány dva vrcholy: source ( source ) a sink ( sink ) , takže jakýkoli jiný vrchol sítě leží na cestě z do , zatímco . $s$ $t$ $s$ $t$ $s\neq t$

Flow (flow) - funkce (v některých zdrojích také ) s následujícími vlastnostmi: ${\displaystyle f\colon V\times V\rightarrow \mathbb {R} _{+))$ ${\displaystyle f\colon E\rightarrow \mathbb {R} _{+))$

Omezení kapacity . Hodnota průtoku pro žádnou hranu nesmí překročit její kapacitu: $e\in E$ $0\leqslant f(e)\leqslant c(e).$
Zkosit symetrii. Tok oddomusí být opakem toku oddo: $\u$ $\proti$ $\proti$ $\u$ $f(u,v)=-f(v,u).$
Ochrana toku : pro všechny . $\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$

Hodnota průtoku je součet průtoků ze zdroje nebo součet průtoků do jímky . $|f|=\součet _{v\in V}f(s,v)=\součet _{v\in V}f(v,t)$

Problém maximálního průtoku je najít takový průtok, aby hodnota průtoku byla maximální, tzn. neexistuje žádný proudtakový, že. $F$ $f^{*}$ $|f^{*}|>|f|$

Řez (st cut) je dvojice disjunktních množin , jako jsou a a . Existuje také definice, kde řez je podmnožina hran , kde je podmnožina vrcholů taková, že a . $(A, B)$ $V=A\ {\tečka {\cup }}\ B$ $s\in A$ $v B$ ${\displaystyle \delta ^{+}(X)=\{(u,v)\in E\mid u\in X,\ v\notin X\))$ $X$ $s\in X$ $t\notin X$

Kapacita st řezu je součtem kapacit všech řezných hran: nebo . $\sum _{e\in \delta ^{+}(X)}c(e)$ $\sum _{(u,v)\in E,u\in A,v\in B}c(u,v))$

Hodnota řezného průtoku je součtem hodnot průtoku všech řezných hran nebo . Nepřekračuje propustnost řezu, protože pro všechny . $\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\ v A,v\in B}f((v,u))$ $f(e)\leqslant c(e)$ $e\in E$

Minimální řez — řez s minimální průchodností.

Zbytková kapacita hrany (zbytková kapacita) - . Kvůli podmínce omezení šířky pásma je vždy nezáporná. $c_{f}((u,v))=c((u,v))-f((u,v))+f((v,u))$

Zbytková síť je graf , kde je množina hran s kladnou zbytkovou kapacitou. Cesta vertex - to-vertex může existovat ve zbytkové síti , i když v původní síti neexistuje. K tomu dochází, když v původní síti existuje zpětná cesta a tok podél ní je kladný. $G_{f}=(V,E_{f})$ ${\displaystyle E_{f))$ $u$ $proti$ $(v,u)$

Rozšiřující (zbytková, doplňující) cesta (rozšiřující cesta) je cesta ve zbytkové síti, kde a Níže je prokázáno, že tok je maximální tehdy a jen tehdy , když ve zbytkové síti neexistuje rozšiřující cesta. $(u_{1},u_{2},\tečky ,u_{k})$ $u_{1}=s,$ $u_{k}=t,$ $c_{f}(u_{i},u_{i+1})>0.$

Vlastnosti

Průtok jakýmkoli řezem se rovná součtu průtoků ze zdroje.
Důkaz : nechť je řez (A,B). Uvažujme součet všech toků ze všech vrcholů patřících do A. Je roven

\součet _{{u\v A}}\součet _{{v\in A}}f(u,v)+\součet _{{u\v A}}\součet _{{v\v B} }f(u,v)

První ze součtů pro libovolnou dvojici vrcholů (u, v) obsahuje dva členy f(u, v) a f(v, u) stejné v absolutní hodnotě a opačné ve znaménku. Proto je tento součet nulový. Druhým součtem je průtok řezem (A,B). Proto je součet všech toků ze všech vrcholů patřících do A roven průtoku řezem. Na druhé straně součet toků z libovolného vrcholu, kromě s a t, je roven nule a . Proto je součet všech toků ze všech vrcholů patřících do A roven součtu toků z s. Proto se průtok řezem (A,B) rovná součtu průtoků z s, který měl být prokázán. $t\notin A$

Součet průtoků ze zdroje se rovná součtu průtoků do jímky.
Důkaz : Zvažte řez . Průtok tímto řezem se rovná součtu průtoků do odpadu. Na druhou stranu, podle toho, co bylo právě dokázáno, je průtok tímto (ale i jakýmkoli jiným) řezem roven součtu průtoků ze zdroje. Věta byla prokázána. $(V\setminus \{t\},\{t\})$

Maximální průtok je kladný tehdy a jen tehdy, když existuje cesta od zdroje k jímce podél okrajů s kladnou kapacitou.
Důkaz : Nechť taková cesta P existuje. Nechť c je minimální kapacita hran patřících k P. Nechť je tok roven c na všech hranách od P a nule na všech ostatních hranách. Potom se celkový průtok ze zdroje rovná c, to znamená, že je kladný. Nyní předpokládejme, že žádná taková cesta neexistuje, to znamená, že t není dosažitelné z s podél hran s kladnou kapacitou. Nechť A je množina vrcholů dosažitelných z s podél takových hran, B je množina nedosažitelných. Potom, protože , , pak (A,B) je řez. Také neexistuje žádná hrana (a, b) s kladnou kapacitou taková, že , , jinak by b bylo dosažitelné z s. Proto je propustnost sekce (A,B) rovna nule, a tudíž průtok skrz ni je vždy roven nule. Proto je součet toků ze zdroje vždy nulový. $v A$ $v B$ $v A$ $b\in B$

Tok je maximální tehdy a jen tehdy, když ve zbytkové síti není žádná rozšiřující cesta. Důkaz : Nechť existuje rozšiřující cesta ve zbytkové síti a je minimem zbytkové kapacity hran patřících do zbytkové sítě. Pro všechny páry zvyšte o a snižte o . Celkový průtok ze zdroje jsme zvýšili o , tudíž to nebylo maximum. Nyní naopak předpokládejme, že žádná taková cesta neexistuje. Dokažme kontradikcí, že tok v původní síti poskytuje maximální celkový tok z . Pokud tomu tak není, pak existuje průtok poskytující větší celkový průtok z . Je snadné vidět, že jde o tok ve zbytkové síti, který poskytuje kladný celkový tok z . Proto ve zbytkové síti existuje cesta od zdroje k jímce, tedy rozšiřující cesta. Máme rozpor. $P$ $C$ $P$ $(u,v)\v P$ $f(u,v)$ $C$ $f(v,u)$ $C$ $C$ $F$ $s$ $F'$ $s$ $f'-f$ $s$

Fordova-Fulkersonova věta . Hodnota maximálního průtoku je rovna kapacitě minimální sekce.
Důkaz : součet průtoků zje roven průtoku jakýmkoli řezem, včetně minimálního, proto nepřesahuje průchodnost minimálního řezu. Proto maximální průtok není větší než průchodnost minimálního řezu. Zbývá dokázat, že není o nic menší než ona. Nechte průtok maximální. Potom ve zbytkové síti není jímka dosažitelná ze zdroje. Nechť je množina vrcholů dosažitelných ze zdroje ve zbytkové síti, které jsou nedosažitelné. Potom, od,, pakje řez. Navíc ve zbytkové síti není žádná hranas kladnou kapacitou taková, že,, jinak bybyla dosažitelná z. Proto v původní síti je tok podél jakékoli takové hrany roven její kapacitě, a tudíž tok skrz zářezse rovná její kapacitě. Ale průtok jakýmkoli řezem se rovná celkovému průtoku ze zdroje, který se v tomto případě rovná maximálnímu průtoku. Maximální průtok je tedy roven průtoku řezu, který není menší než průtok minimálního řezu. Věta byla prokázána. $s$ $A$ $B$ $v A$ $v B$ $(A,B)$ $(a,b)$ $v A$ $b\in B$ $b$ $s$ $(A, B)$ $(A,B)$

Příklad

Zde je zobrazena transportní síť se zdrojem , jímkou a čtyřmi dalšími uzly. Průtok a propustnost jsou označeny . Šířka pásma od zdroje k umyvadlu je 5, což je dobře vidět, protože šířka pásma od je 5, což je také v . $\s$ $\t$ $\f/c$ $\s$ $\t$

Zbytková síť pro výše uvedený průtok je uvedena níže. Všimněte si, že pro některé hrany existuje omezující kapacita, zatímco v původní síti je nulová. Například žebro . Tento průtok není maximální. Existují rostoucí cesty a . Zbytková kapacita první koleje . Rozšiřující cesta ve zdrojové síti neexistuje, ale je možné přes ni předat správný tok. $\(DC)$ $\(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)$

Aplikace

Nejčastějším příkladem použití transportních sítí je nalezení maximálního toku , což znamená maximální celkový tok od do K nalezení maximálního toku v síti lze použít Ford-Fulkersonův algoritmus , Edmonds-Karpův algoritmus a další. $s$ $t.$

V problému toku minimálních nákladů je každé hraně přiřazena cena , cena za odeslání toku přes hranu . Úkolem je odeslat dané množství toku od do s nejnižšími náklady. $(u,v)$ $k(u,v)$ $f(u,v)$ $f(u,v)\cdot k(u,v)$ $s$ $t$

Viz také

Literatura

Thomas H. Kormen aj. Algoritmy: konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Odkazy (anglicky)

Problém s maximálním průtokem
Maximální průtok
Skutečné grafy
Software, papíry, testovací grafy atd.
Řešení problémů s tokem sítě (nedostupný odkaz)
Software a dokumenty pro problémy s tokem sítě
Knihovna Lemon C++ s několika algoritmy cirkulace maximálního toku a minimálních nákladů