2 Toky v sítích
Nyní se podíváme na jinou 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
Stručný přehled lekce
ˇ Definice sítě (ohodnoceného orientovaného grafu) a toku v ní.
ˇ Algoritmus nenasycených cest (Ford-Fulkersonův).
ˇ Důsledky pro souvislost, párování a výběr reprezentantů.
ˇ Princip dobré charakterizace úloh.
Petr Hliněný, FI MU 1 IA102 "OU": Toky v sítích
2.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 2.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
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 2 IA102 "OU": 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.
Definice 2.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).
Velikost toku f je dána výrazem f =
ez
f(e) -
ez
f(e).
Značení: Tok a kapacitu hran v obrázku sítě budeme zjednodušeně zapisovat ve for-
mátu F/C, kde F je hodnota toku na hraně a C je její kapacita.
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
Ve vyobrazeném příkladě vede ze zdroje vlevo do stoku vpravo tok o celkové velikosti 5.
Petr Hliněný, FI MU 3 IA102 "OU": Toky v sítích
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 4 IA102 "OU": Toky v sítích
2.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.
Úloha 2.3. O maximálním 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.
Tok velikosti 5 uvedený v ukázce v předchozí části nebyl optimální, neboť v té síti najdeme i
tok velikosti 6:
z 0/1
2/5
0/2
0/1
s
3/4
2/22/4
3/3
0/2
3/5
0/3
Petr Hliněný, FI MU 5 IA102 "OU": 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.
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 6 IA102 "OU": Toky v sítích
Definice 2.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).
Věta 2.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
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 7 IA102 "OU": Toky v sítích
Definice: Mějme síť S a v ní tok f. Nenasycená cesta (v S vzhledem k f) je neoriento-
vaná 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.
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.
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 8 IA102 "OU": Toky v sítích
Algoritmus 2.6. Ford­Fulkersonův pro tok v síti
vstup síť S = (G, z, s, w);
tok f  0;
do {
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;
}
while ( 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.
z s
3
4
1
1
4
1
2
4
1
Petr Hliněný, FI MU 9 IA102 "OU": Toky v sítích
Důkaz správnosti Algoritmu 2.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. Zároveň tím dokážeme i platnost Věty 2.5.
Takže stačí dokázat, ž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
Jelikož z U žádné nenasycené cesty dále nevedou, má každá hrana e  U (odcházející
z U) plný tok f(e) = w(e) a každá hrana e  U (přicházející do U) tok f(e) = 0.
Velikost toku f ze z do s se také dá psát jako
f =
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. 2
Petr Hliněný, FI MU 10 IA102 "OU": Toky v sítích
Důsledek 2.7. Pokud jsou kapacity hran sítě S celočíselné, optimální tok také vyjde
celočíselně.
Poznámka: Algoritmus pro celá čísla kapacit vždy skončí. Pro reálná čísla se ale dají najít
extrémní případy, které nepovedou k řešení ani v limitě.
Pro rychlý běh algoritmu je vhodné hledat nejkratší nenasycenou cestu, tj. prohledáváním sítě
do šířky. V takové implementaci algoritmus dobře a rychle funguje i s reálnými kapacitami
hran.
Petr Hliněný, FI MU 11 IA102 "OU": Toky v sítích
2.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 spo-
jujících zdvojené vrcholy. Viz neformální schéma:
s
z
3
4
5
42
5
3
z
5
s3
3 5
4
2
4
Petr Hliněný, FI MU 12 IA102 "OU": 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 garanto-
vat, ž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 zabývat.
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ší a už není v obecnosti
snadno řešitelný, a proto se jím nebudeme zabývat.
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 13 IA102 "OU": 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.
Algoritmus 2.8. 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 2.6. Do párování vložíme ty hrany
grafu G, které mají nenulový tok.
Důkaz správnosti Algoritmu 2.8: Podle Důsledku 2.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 14 IA102 "OU": 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:
Lema 2.9. 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.
To přímo ukazuje cestu k důkazu Mengerovy věty o násobné souvislosti grafu.
Různí reprezentanti
Definice: Nechť M1, M2, . . . , Mk jsou neprázdné množiny. Systémem různých re-
prezentantů 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.
Věta 2.10. (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.
Petr Hliněný, FI MU 15 IA102 "OU": Toky v sítích
2.4 Dobrá charakterizace
V návaznosti na Definici 1.13, bod 5, se podíváme na tuto situaci: Dokazujeme optimalitu
nalezeného řešení, tj. že lepší řešení našeho problému neexistuje, tím, že (názorně) ukážeme
nějakou vhodnou "vylučovací" vlastnost. Tzn. něco, co jasně vylučuje existenci lepšího řešení
způsobem pochopitelným i pro laika neobeznámeného hlouběji s problémem a naším řešením.
(Poznamenáváme, že ne vždy je něco takového možné.)
Přesněji řečeno, v Úloze 1.1 o přidělování pracovních úkolů platí, že existence přípust-
ného přidělení k pracovníků na dané úkoly je ekvivalentní neexistenci okamžiku s více
než k překrývajícími se úkoly. V přirozenějším jazyce totéž řekneme takto:
k pracovníků na úkoly stačí, právě když nikdy není více než k současných úkolů.
Fakt: Nechť I označuje průnikový graf intervalů daných pracovních úkolů. Pak přípust-
ného přidělení k pracovníků na tyto úkoly je modelováno jako grafový homomorfismus
p : I  Kk.
Naopak  překrývajících se úkolů je v grafu I ukázáno jako grafový homomorfismus
q : K  I. Takže ve shrnutí můžeme naši úvahu formálně zapsat
 p : I  Kk   q : Kk+1  I .
Petr Hliněný, FI MU 16 IA102 "OU": Toky v sítích
V případě toků v sítích platí, že tok velikosti t existuje, právě když není v síti žádný řez
menší než t.
V obecnosti můžeme podat následující hrubý popis, kterému říkáme princip dobré cha-
rakterizace:
Konvence 2.11. Říkáme, že optimalizační problém má dobrou charakterizaci, pokud
optimalitu nalezeného řešení můžeme vždy prokázat nalezením řešení jiné ("duální")
úlohy, jehož ověření je "výrazně snažší" (či názornější) než bylo samotné vyřešení úlohy.
Poznámka: V obecnosti se princip dobré charakterizace neomezuje jen na optimalizační úlohy
(kde je výrazně spojen s pracemi Edmondse), ale je to důležitý tzv. kategoriální pojem v
matematice: Existence jednoho "morfismu" je dána neexistencí jiného "morfismu". Například
v kombinatorice najdeme mnoho důležitých příkladů takových strukturálních charakterizací.
To je však daleko za obsahem našeho předmětu.
Petr Hliněný, FI MU 17 IA102 "OU": Toky v sítích