Petr Hliněný, FI MU Brno 1 FI: MA010: Toky v sítích
6 Toky v sítích
Nyní se podíváme ještě na jednu oblast úloh, kde našla teorie grafů bohaté uplatnění (konkrétně
orientované grafy). Jde o oblast tzv. ,,síťových úloh:
Jedná se třeba o potrubní sítě přepravující vodu nebo plyn, o dopravní síť silnic s přepravou
zboží, nebo třeba o internet přenášející data. Obvykle nás zajímá problém přenést z daného
zdroje do daného cíle čili stoku co nejvíce této substance, za omezujících podmínek kapacit
jednotlivých přepravních cest
2
z
5
1
3
4
5
2
1 s
4
2
3
2
Stručný přehled lekce
* Definice sítě (ohodnoceného orientovaného grafu) a toku v ní.
* Algoritmus nenasycených cest.
* Důsledky pro souvislost, párování a výběr reprezentantů.
Petr Hliněný, FI MU Brno 2 FI: MA010: Toky v sítích
6.1 Definice sítě
Základní strukturou pro reprezentaci sítí je orientovaný graf. Vrcholy grafu modelují
jednotlivé uzly sítě a hrany jejich spojnice.
Definice 6.1. Síť je čtveřice S = (G, z, s, w), kde
­ G je orientovaný graf,
­ vrcholy z  V (G), s  V (G) jsou zdroj a stok,
­ w : E(G)  R+
je kladné ohodnocení hran, zvané kapacita hran.
2
z
5
1
3
4
5
2
1 s
4
2
3
2
Poznámka: V praxi může být zdrojů a stoků více, ale v definici stačí pouze jeden zdroj a
stok, z něhož / do nějž vedou hrany do ostatních zdrojů / stoků. (Dokonce pak různé zdroje
a stoky mohou mít své kapacity.)
Petr Hliněný, FI MU Brno 3 FI: MA010: Toky v sítích
Značení: Pro jednoduchost píšeme ve výrazech znak e  v pro hranu e přicházející
do vrcholu v a e  v pro hranu e vycházející z v. 2
Definice 6.2. Tok v síti S = (G, z, s, w)
je funkce f : E(G)  R+
0 splňující
­ e  E(G) : 0  f(e)  w(e),
­ v  V (G), v = z, s :
ev
f(e) =
ev
f(e). 2
Velikost toku f je dána výrazem f =
ez
f(e) -
ez
f(e). 2
Značení: Tok a kapacitu hran v obrázku sítě budeme zjednodušeně zapisovat ve formátu
F/C, kde F je hodnota toku na hraně a C je její kapacita.
Petr Hliněný, FI MU Brno 4 FI: MA010: Toky v sítích
Neformálně tok znamená, kolik substance je každou hranou zrovna přenášeno (ve směru této
hrany, proto hrany musí být orientované). Tok je pochopitelně nezáporný a dosahuje nejvýše
dané kapacity hrany.
z 0/1
2/5
0/2
0/1
s
3/4
2/22/4
3/3
0/2
3/5
0/3
2
Ve vyobrazeném příkladě vede ze zdroje vlevo do stoku vpravo tok o celkové velikosti 5. 2
Poznámka: Obdobně se dá velikost toku definovat u stoku, neboť
0 =
e
(f(e) - f(e)) =
v ev
f(e) v
ev
f(e) =
v=z,s ev
f(e) -
ev
f(e) .
(Dvojité sumy uprostřed předchozího vztahu nabývají stejných hodnot pro všechny vrcholy
kromě z a s dle definice toku.) Proto velikost toku počítaná u zdroje je rovna opačné velikosti
toku počítaného u stoku.
Petr Hliněný, FI MU Brno 5 FI: MA010: Toky v sítích
6.2 Hledání maximálního toku
Naším úkolem je najít co největší tok v dané síti. Pro jeho nalezení existují jednoduché
a velmi rychlé algoritmy.
Problém 6.3. Maximálního toku v síti
Je dána síť S = (G, z, s, w) a našim úkolem je pro ni najít co největší tok ze zdroje z
do stoku s vzhledem k ohodnocení w. 2
z 0/1
2/5
0/2
0/1
s
3/4
2/22/4
3/3
0/2
3/5
0/3
Tok velikosti 5 uvedený v ukázce v předchozí části nebyl optimální, neboť v této síti najdeme
i tok velikosti 6:
Petr Hliněný, FI MU Brno 6 FI: MA010: Toky v sítích
z 0/1
2/5
0/2
0/1
s
4/4
2/23/4
3/3
0/2
4/5
1/3
Jak však poznáme, že větší tok již v dané síti neexistuje? V této konkrétní ukázce to není
obtížné, vidíme totiž, že obě dvě hrany přicházející do stoku mají součet kapacit 2 + 4 + 6,
takže více než 6 do stoku ani přitéct nemůže. 2
V obecnosti lze použít obdobnou úvahu, kdy najdeme podmnožinu hran, které nelze tokem
,,obejít a které v součtu kapacit dají velikost našeho toku. Existuje však taková množina hran
vždy? Odpověď nám dá následující definice a věta.
Petr Hliněný, FI MU Brno 7 FI: MA010: Toky v sítích
Definice 6.4. Řez v síti S = (G, z, s, w)
je podmnožina hran C  E(G) taková, že v podgrafu G - C (tj. po odebrání hran C
z G) nezbude žádná orientovaná cesta ze z do s.
Velikostí řezu C rozumíme součet kapacit hran z C, tj. C = eC w(e). 2
Věta 6.5. Maximální velikost toku v síti je rovna minimální velikosti řezu.
Na následujícím obrázku vidíme trochu jinou síť s ukázkou netriviálního minimálního řezu
velikosti 5, naznačeného svislou čárkovanou čarou. Všimněte si dobře, že definice řezu mluví o
přerušení všech orientovaných cest ze z do s, takže do řezu stačí započítat hrany jdoucí přes
svislou čáru od z do s, ale ne hranu jdoucí zpět. Proto je velikost vyznačeného řezu 1+ 4 = 5.
z s
3
4
1
1
4
1
2
4
1
2
Poznámka: Tato věta poskytuje tzv. dobrou charakterizaci problému maximálního toku: Když
už nalezneme maximální tok, tak je pro nás vždy snadné dokázat, že lepší tok není, nalezením
příslušného řezu o stejné velikosti. Přitom toto zdůvodnění řezem můžeme směle ukázat i
někomu, kdo se vůbec nevyzná v matematice.
Petr Hliněný, FI MU Brno 8 FI: MA010: Toky v sítích
Definice: Mějme síť S a v ní tok f. Nenasycená cesta (v S vzhledem k f) je neorientovaná
cesta v G z vrcholu u do vrcholu v (obvykle ze z do s), tj. posloupnost navazujících
hran e1, e2, . . . , em, kde f(ei) < w(ei) pro ei ve směru z u do v a f(ei) > 0 pro ei v
opačném směru. 2
Hodnotě w(ei) - f(ei) pro hrany ei ve směru z u do v a hodnotě f(ei) pro hrany ei
v opačném směru říkáme rezerva kapacity hran ei. Nenasycená cesta je tudíž cesta s
kladnými rezervami kapacit všech hran. 2
Zde vidíme příklad nenasycené cesty ze zdroje do stoku s minimální rezervou kapacity +1.
sz
3/4 1/2 1/1 2/3 2/4
+1 +1 +2 +2+1rezerva kapacity:
Všimněte si dobře, že cesta není orientovaná, takže hrany na ní jsou v obou směrech.
Petr Hliněný, FI MU Brno 9 FI: MA010: Toky v sítích
z s
3
4
1
1
4
1
2
4
1
Algoritmus 6.6. Ford­Fulkersonův pro tok v síti.
vstup síť S = (G, z, s, w);
tok f  0;
repeat {
Prohledáváním grafu najdeme množinu U vrcholů G,
do kterých se dostaneme ze z po nenasycených cestách;
if ( s  U ) {
P = (výše nalezená) nenasycená cesta v S ze z do s;
Zvětšíme tok f o minimální rezervu kapacity hran v P;
}
until ( s  U );
výstup vypíšeme maximální tok f;
výstup vypíšeme min. řez jako množinu hran vedoucích z U do V (G) - U.
Petr Hliněný, FI MU Brno 10 FI: MA010: Toky v sítích
Důkaz správnosti Algoritmu 6.6:
Pro každý tok f a každý řez C v síti S platí f  C . Jestliže po zastavení algoritmu
s tokem f nalezneme v síti S řez o stejné velikosti C = f , je jasné, že jsme našli
maximální možný tok v síti S. (Pozor, zastavení algoritmu jsme zatím nezdůvodnili.) 2
Takže dokažme, že po zastavení algoritmu nastane rovnost f = C , kde C je
vypsaný řez mezi U a zbytkem grafu G. Vezměme tok f v S bez nenasycené cesty ze
z do s. Pak množina U z algoritmu neobsahuje s. Schematicky vypadá situace takto:
z s
f(e) = 0
f(e) = w(e)
U
2
Jelikož z U žádné nenasycené cesty dále nevedou, má každá hrana e  U (odch. z U)
plný tok f(e) = w(e) a každá hrana e  U (přich. do U) tok f(e) = 0, takže
eU
f(e) -
eU
f(e) =
eU
f(e) =
eC
w(e) = C .
To je přesně, co jsme chtěli dokázat o výsledném toku. Zbývá ,,selským rozumem
nahlédnout, že eU f(e) - eU f(e) = f , a důkaz je hotov. 2
Petr Hliněný, FI MU Brno 11 FI: MA010: Toky v sítích
Z důkazu Algoritmu 6.6 odvodíme několik zajímavých faktů:
Fakt: Pokud zajistíme, že Algoritmus 6.6 vždy skončí, dokážeme i platnost Věty 6.5. 2
Fakt: Pro celočíselné kapacity hran sítě S Algoritmus 6.6 vždy skončí.
Důsledek 6.7. Pokud jsou kapacity hran celočíselné, opt. tok také vyjde celočíselně.2
Bohužel pro reálná čísla kapacit hran není skončení Algoritmu 6.6 vůbec zaručeno,
dokonce se dají najít extrémní případy, které nepovedou k řešení ani v limitě. Proto je
potřebné základní algoritmus (i pro potřeby teorie) poněkud vylepšit. 2
Algoritmus 6.8. Edmonds­Karpův pro tok v síti
V Algoritmu 6.6 vždy sytíme nejkratší nenasycenou cestu, neboli prohl. naši síť do šířky.
Tato implementace zaručeně skončí po O(|V (G)|  |E(G)|) iteracích cyklu. 2
Algoritmus 6.9. ,,Tří Indů pro tok v síti (náznak)
V intencích Algoritmu 6.6 provádíme následující iterace:
* Prohledáváním sítě do šířky nalezneme všechny nenasycené cesty nejkratší délky.
* Nalezené nenasycené cesty pak souběžně nasytíme ,,dynamickým algoritmem.
Tato implementace zaručeně skončí už po O(|V (G)|) iteracích cyklu, ale jednotlivé
iterace jsou poněkud náročnější.
Petr Hliněný, FI MU Brno 12 FI: MA010: Toky v sítích
6.3 Zobecnění sítí a další aplikace
Pojmy sítě a toků v ní lze zobecnit v několika směrech. My si zde stručně uvedeme tři
možnosti:
1. U sítě můžeme zadat i kapacity vrcholů.
To znamená, že žádným vrcholem nemůže celkem protéct více než povolené
množství substance. Takovou síť ,,zdvojením vrcholů snadno převedeme na běžnou
síť, ve které kapacity původních vrcholů budou uvedeny u nových hran spojujících
zdvojené vrcholy. Viz neformální schéma:
s
z
3
4
5
42
5
3
z
s3
3 5
4
2
4
Petr Hliněný, FI MU Brno 13 FI: MA010: Toky v sítích
2. Pro hrany sítě lze zadat také minimální kapacity, tedy dolní meze toku.
(Například u potrubní sítě mohou minimální vyžadované průtoky vody garantovat,
že nedojde k zanesení potrubí.) V této modifikaci úlohy již přípustný tok
nemusí vůbec existovat. Takto zobecněná úloha je také snadno řešitelná, ale my
se jí nebudeme dále zabývat. 2
3. V síti lze najednou přepravovat více substancí. To vede na problém tzv. vícekomoditních
toků v síti. Tento problém je složitější, už není v obecnosti snadno
řešitelný a přesahuje rámec našeho textu, takže se jím také nebudeme zabývat.
2
Kromě uvedených (a podobných) zobecnění toků v sítích jsou velmi zajímavé i některé
speciální formulace problému toků, které se vyskytují v možná i nečekaných oblastech.
Více o tom napíšeme v dalších částech tohoto oddílu.
Petr Hliněný, FI MU Brno 14 FI: MA010: Toky v sítích
Bipartitní párování
Definice: Párování v (biparitním) grafu G je podmnožina hran M  E(G) taková, že
žádné dvě hrany z M nesdílejí koncový vrchol.
Pojem (bipartitního) párování má přirozenou motivaci v mezilidských vztazích. 2
Algoritmus 6.10. Nalezení bipartitního párování
Pro daný bipartitní graf G s vrcholy rozdělenými do množin A, B sestrojíme síť S
následovně:
s s
s s
s s
s s
s s
A B
z s
1 1
1 1
Všechny hrany sítě S orientujeme od zdroje do stoku a přiřadíme jim kapacity 1. Nyní
najdeme (celočíselný) maximální tok v S Algoritmem 6.6. Do párování vložíme ty hrany
grafu G, které mají nenulový tok. 2
Důkaz správnosti Algoritmu 6.10: Podle Důsledku 6.7 bude maximální tok celočíselný,
a proto každou hranou poteče buď 0 nebo 1. Tím budou vybrány hrany párování a
podle zadaných kapacit nebudou sdílet koncové vrcholy. 2
Petr Hliněný, FI MU Brno 15 FI: MA010: Toky v sítích
Vyšší grafová souvislost
Představme si, že na libovolném grafu G definujeme zobecněnou síť tak, že kapacity
všech hran a všech vrcholů položíme rovny 1 v obou směrech. Pak máme:
Důsledek 6.11. Nechť u, v jsou dva vrcholy grafu G a k > 0 je přirozené číslo. Pak
mezi vrcholy u a v existuje v G aspoň k disjunktních cest, právě když po odebrání
libovolných k - 1 vrcholů různých od u, v z G zůstanou u a v ve stejné komponentě
souvislosti zbylého grafu. 2
Použitím tohoto tvrzení pro všechny dvojice vrcholů grafu snadno dokážeme dříve uvedenou
důležitou Větu 2.8 (Mengerovu).
Petr Hliněný, FI MU Brno 16 FI: MA010: Toky v sítích
Různí reprezentanti
Definice: Nechť M1, M2, . . . , Mk jsou neprázdné množiny. Systémem různých reprezentantů
množin M1, M2, . . . , Mk nazýváme takovou posloupnost různých prvků
(x1, x2, . . . , xk), že xi  Mi pro i = 1, 2, . . ., k. 2
Věta 6.12. (Hall) Nechť M1, M2, . . . , Mk jsou neprázdné množiny. Pro tyto množiny
existuje systém různých reprezentantů, právě když platí
J  {1, 2, . . ., k} :
jJ
Mj  |J| ,
neboli pokud sjednocení libovolné skupiny z těchto množin má alespoň tolik prvků,
kolik množin je sjednoceno.
Důkaz: Označme x1, x2, . . . , xm po řadě všechny prvky ve sjednocení M1  M2 
. . .  Mk. Definujeme si bipartitní graf G na množině vrcholů {1, 2, . . ., k} 
{x1, x2, . . . , xm}{u, v}, ve kterém jsou hrany {u, i} pro i = 1, 2, . . ., k, hrany {v, xj}
pro j = 1, 2, . . ., m a hrany {i, xj} pro všechny dvojice i, j, pro které xj  Mi.
Petr Hliněný, FI MU Brno 17 FI: MA010: Toky v sítích
Cesta mezi u a v má tvar u, i, xj, v, a tudíž ukazuje na reprezentanta xj  Mi. Systém
různých reprezentantů tak odpovídá k disjunktním cestám mezi u a v. Nechť X je
nyní libovolná minimální množina vrcholů v G, neobsahující samotné u a v, po jejímž
odebrání z grafu nezbude žádná cesta mezi u a v. Podle Lematu 6.11 a této úvahy
mají naše množiny systém různých reprezentantů, právě když každá taková oddělující
množina X má aspoň k prvků.
Položme J = {1, 2, . . ., k} \ X. Pak každá hrana z J (mimo u) vede do vrcholů z
X  {x1, . . . , xm} (aby nevznikla cesta mezi u, v), a proto
jJ
Mj = |X  {x1, . . . , xm}| = |X| - |X  {1, . . . , k}| = |X| - k + |J| .
Vidíme tedy, že |X|  k pro všechny (minimální) volby oddělující X, právě když
jJ Mj  |J| pro všechny volby J, což je dokazovaná podmínka naší věty. 2
Poznámka: Předchozí důkaz nám také dává návod, jak systém různých reprezentantů pro
dané množiny nalézt ­ stačí použít Algoritmus 6.6 na vhodně odvozenou síť.