9   Orientované grafy, Toky v sítích
Nyní se budeme zabývat typem síťových úloh, ve kterých není podstatná délka hran a spojení, nýbž jejich propustnost (jako potrubní nebo počítačové sítě).
Základní úlohou v této oblasti je problém nalezení maximálního toku v síti za podmínky respektování daných kapacit hran.
Stručný přehled lekce
* Definice a některé základní vlastnosti orientovaných grafů, souvislost.
* Sítě s kapacitami hran, hledání maximálního toku a dualita.
* Důsledky duality toku; vyšší souvislost, bipartitní párování, SRR.
Petr Hliněný, Fl MU Brno, 2014
1/19
Fl: IB000: Toky v sítích
9.1   Základní pojmy orientovaných grafů
Požadavek explicitně vyjádřit směr hrany přirozeně vede na následující definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů.
Definice 9.1. Orientovaný graf je uspoř, dvojice D = (V, E), kde E C V x V.
Pojmy podgrafu a isomorfismu se přirozeně přenášejí na orientované grafy.
Značení: Hrana (u,v) (zvaná také šipka) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří do) vrcholu v. Opačná hrana (v, u) je různá od (u, v).
Speciálně hrana tvaru (u,u) se nazývá orientovaná smyčka, c Orientované grafy odpovídají relacím, které nemusí být symetrické.
c
Petr Hliněný, Fl MU Brno, 2014
2/19
Fl: IB000: Toky v sítích
• Orientovaná cesta délky n > O je následujícím grafem na n + 1 vrcholech
6       ... n
Definice: Počet hran začínajících ve vrcholu u orientovaného grafu D nazveme výstupním stupněm (^{u) a počet hran končících v u nazveme vstupním stupněm dp(u).
Součet všech výstupních stupňů je přirozeně roven součtu všech vstupních stupňů.
Petr Hliněný, Fl MU Brno, 2014
3/19
Fl: IB000: Toky v sítích
Souvislost na orientovaných grafech
Uvedeme si odstupňovaně tři základní pohledy:
• Slabá souvislost. Jedná se o tradiční souvislost na symetrizaci grafu D (tj. po „zapomenutí" směru šipek).
®-2> •-2> • <S-• <<:-•-
c
• Dosažitelnost (směrem „ven"). Orientovaný graf D je dosažitelný směrem ven, pokud v něm existuje vrchol v G V (D) takový, že každý vrchol x G V (D) je dosažitelný orientovaným sledem z v.
v ®-
Petr Hliněný, Fl MU Brno, 2014
4/19
Fl: IB000: Toky v sítích
Podrobným zkoumáním následujícího obrázku zjistíme, že jeho graf není dosažitelný směrem ven, neboť chybí možnost dosáhnout vrchol b úplně vpravo. Na druhou stranu po vypuštění b je zbylý graf dosažitelný ven z vrcholu a vlevo.
Petr Hliněný, Fl MU Brno, 2014
5/19
Fl: IB000: Toky v sítích
Souvislost na orientovaných grafech, silná
• Silná souvislost.   Nechť     je binární relace na vrcholové množině V(D) orientovaného grafu D taková, že
* u    v právě když existuje dvojice orientovaných cest - jedna z u do v
a druhá z v do u v grafu D. c Pak    je relace ekvivalence.
c
Definice 9.2. Silné komponenty orientovaného grafu D jsou třídy ekvivalence relace    uvedené v předchozím.
Orientovaný graf Ľ je silně souvislý pokud má nejvýše jednu silnou komponentu.
Petr Hliněný, Fl MU Brno, 2014
6/19
Fl: IB000: Toky v sítích
Pro ilustraci si mírně upravíme dříve prezentovaný orientovaný graf tak, že bude dosažitelný z nejlevějšího vrcholu. Je výsledek silně souvislý?
Ne, na obrázku jsou vyznačené jeho 4 silné komponenty.
Zároveň uvádíme pro ilustraci obrázek kondenzace silných komponent tohoto grafu, což je acyklický orientovaný graf s vrcholy reprezentujícími zmíněné silné komponenty a směry hran mezi nimi.
Petr Hliněný, Fl MU Brno, 2014
7/19
Fl: IB000: Toky v sítích
9.2   Definice sítě a toku
Základní strukturou pro reprezentaci sítí je va'žený orientovaný graf (přičemž implicitní směr hran je v tomto kontextu nezbytný), c
Definice 9.3. Síť je čtveřice S = (D,z,s,w), kde
* D je orientovaný graf,
* vrcholy z G V (D), s G V (D) jsou zdroj a stok,
* w : E(D) —> R+ je kladné ohodnocení hran, zvané kapacita hran.
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ý, Fl MU Brno, 2014
8/19
Fl: IB000: Toky v sítích
Velikost toku v síti
Značení: Pro jednoduchost píšeme ve výrazech značku e —> v pro hranu e končící ve vrcholu v a e -í— v pro hranu e začínající z v. c
Definice 9.4. Tok v síti 5 = (D, z, s, w) je funkce / : E(D) —> Hq splňující
* Ve G E (D) : 0 < f (e) < w(e), (respektování kapacity)
* Vti £ V(D),í; ^ z,s :   Yl f(e) = S í\e)-       (zachovaní substance)
e—>u e-ť— t)
C
Velikost toku / je dána výrazem ||/|| = Y f(e) ~ Yl f(e)- c
e<— z e—>z
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.
9.3   Nalezení maximálního toku
Naším úkolem je najít co největší přípustný tok v dané síti. Pro jeho nalezení existují jednoduché a velmi rychlé algoritmy.
Definice 9.5. Úloha hledání maximálního toku v síti S = (D,z,s,w).
Úkolem je v síti S najít tok / ze zdroje z do stoku s podle Definice 9.4 takový, který maximalizuje velikost ||/||. c
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:
Jak však poznáme, že větší tok již v dané síti neexistuje?
Petr Hliněný,  Fl MU Brno, 2014
10/19
Fl: IB000: Toky v sítích
Pojem řezu v síti
Definice 9.6. Řez v síti   S = (D,z,s,w) je podmnožina hran X C E (D) taková, že v podgrafu D — X (tj. po odebrání hran X z D) nezbude žádná orientovaná cesta ze z do s. c
Velikostí řezu X rozumíme součet kapacit hran z X, tj. ||X|| = J2eex
w[e)
Věta 9.7. Maximální velikost toku v síti je rovna minimální velikosti řezu.c V uvedeném obrázku nalezneme tok velikosti 5. Vyznačený řez má také velikost 5.
Petr Hliněný,  Fl MU Brno, 2014
11/19
Fl: IB000: Toky v sítích
Nenasycené cesty v síti
Definice: Mějme síť S a v ní tok /. Nenasycená cesta P (v S vzhledem k /)
* je neorientovaná cesta v D mezi určenými vrcholy (obvykle ze z do s), tj. posloupnost navazujících libovolně orientovaných hran ei, e2,..., em,
* kde f(e,i) < w(ei) pro e^ ve směru ze z do s a /(e,) > 0 pro ej jinak. 3/4       1/2       1/1       2/3 2/4
rezerva kapacity: W _|_]_       _|_]_       _|_]_       _|_2       _)_2 ^-^   > 0
c
* Hodnotě io(ej) — /(ej) > 0 pro hrany e^ ve směru z u do v a hodnotě /(ej) > 0 pro hrany ej v opačném směru říkáme rezerva kapacity hran.
Nenasycená cesta je tudíž cesta s kladnými rezervami kapacit všech hran.
Petr Hliněný,  Fl MU Brno, 2014
12/19
Fl: IB000: Toky v sítích
Metoda 9.8. Maximální tok vylepšováním nenasycených cest.
Základní myšlenkou této jednoduché metody hledání maximálního toku v dané síti je prostě opakovaně vylepšovat tok podél nalezených nenasycených cest.
3/4       1/2       1/1       2/3 2/4
rezerva kapacity:   — _|_2       +2 ^-^   > 0
min. rezerva r = +1 4-
P ^ 4/4      2/2      0/1       1/3 3/4
K3
Pro rekapitulaci, náš tok se „vylepší" následovně;
* pro hrany    G E(P) ve směru ze z do s zvýšíme tok na /'(e^) = /(ej) + r,
* pro hrany e, G -E(-P) ve směru ze s do z snížíme tok na f'(ej) = f(ej) —r.
Výsledný tok /' pak bude opět přípustný.
■/4
■A
■/3
■/4
Algoritmus 9.9. Ford-Fulkersonův pro tok v síti.
• Vstup: Síť S = (D,z,s,w) podle Definice 9.3.
• Tok /<- (0,0, ...0).
• Dále opakujeme následující:
* Prohledáváním grafu najdeme množinu U vrcholů D, do kterých se dostaneme ze z po nenasycených cestách.
* Pokud s G U, nechť P značí nalezenou nenasycenou cestu v S ze z do s. - Zvětšíme tok / o minimální rezervu kapacity hran v P.
• Opakujeme kroky výše, dokud nenastane s 0 U. c
• Výstup:  Vypíšeme maximální tok / a také minimální řez jako množinu všech hran vedoucích z U do V(D) — U.
Petr Hliněný,  Fl MU Brno, 2014
14/19
Fl: IB000: Toky v sítích
Důkaz správnosti Algoritmu 9.9:
Pro každý tok / a každý řez X v síti S platí ||/|| < ||X||. Jestliže po zastavení algoritmu s tokem / nalezneme v síti S řez o stejné velikosti ||X|| = ||/||, je jasné, že jsme našli maximální možný tok v síti S.
(Pozor, zastavení algoritmu jsme zatím nezdůvodnili.) c
Takže dokažme, že po zastavení algoritmu nastane rovnost ||/|| = ||X||, kde X je vypsaný řez mezi U a zbytkem grafu D. Vezměme tok / v S bez nenasycené cesty ze z do s. Pak množina U z algoritmu neobsahuje s.
/(e) = w{e)
©
U
0
f(e)
0
Nyní má každá hrana e <— U (odch. z U) plný tok /(e) = w(e) a každá hrana e^U (přich. do U) tok f(e) = 0, takže
= E /(e) " E /(e) = E /(e) = E        = .
e-f-t/ e-^U e^-V eeX
Petr Hliněný,  Fl MU Brno, 2014
15/19
Fl: IB000: Toky v sítích
Důsledky Ford-Fulkersonova algoritmu
Z důkazu Algoritmu 9.9 pak odvodíme několik zajímavých faktů:
• Pokud Algoritmus 9.9 vždy skončí, dokážeme tím i platnost Věty 9.7. c
• Pro celočíselné kapacity hran sítě S Algoritmus 9.9 vždy skončí.
3/4       1/2       1/1       2/3 2/4
rezerva kapacity: ^-^ _|_2       +2 > 0
» Pokud jsou kapacity hran sítě S celočíselné, opt. tok také vyjde celočíselně.
Petr Hliněný,  Fl MU Brno, 2014
16/19
Fl: IB000: Toky v sítích
9.4   Zobecněné použití sítí
• Sítě s kapacitami vrcholů:
U sítě můžeme zadat kapacity vrcholů, neboli kapacitní váhová funkce je dána jako w : E(D) U V (D) ->• R+.
a
• Sítě s dolními kapacitami:
Pro hrany sítě lze zadat také jejich minimální kapacity, tedy dolní meze
přípustného toku, jako váhovou funkci i : E(D)
£(e) < f(e) < w(e)
Petr Hliněný,  Fl MU Brno, 2014
17/19
Fl: IB000: Toky v sítích
Bipartitní párování
Definice: Párování v (nyní bipartitním) grafu G je podmnožina hran M c E (G) taková, že žádné dvě hrany z M nesdílejí koncový vrchol.
Metoda 9.11. Nalezení bipartitního párování
Pro daný bipartitní graf G s vrcholy rozdělenými do množin A, B sestrojíme sít S následovně:
1
• Hrany sítě S orientujeme od zdroje do stoku a přiřadíme jim kapacity 1. c
• Nyní najdeme (celočíselný) maximální tok v S Algoritmem 9.9. Do párování vložíme ty hrany grafu G, které mají nenulový tok.
Petr Hliněný,  Fl MU Brno, 2014
18/19
Fl: IB000: Toky v sítích
Výběr různých reprezentantů
Definice: Nechť Mi, M2,..., M& jsou neprázdné množiny. Systémem různých reprezentantů množin Mi, M2,..., M& nazýváme takovou posloupnost různých prvků (xi,X2, ■ ■ ■,Xk), že Xj £ Mj pro i = 1,2,... ,k. c
Věta 9.12. (Ha11) Nechť M\, M2,..., M& _/sou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, právě když platí
VJC {1,2,...,A:} : M ,MJ
> IJI
'je J
neboli pokud sjednocení libovolné skupiny z těchto množin má alespoň tolik prvků, kolik množin je sjednoceno.
Důkaz lze podat konstrukcí vhodné sítě podobné té v Metodě 9.11:
• Použijí se speciální vrcholy u a v odpovídající zdroji a stoku;
• další vrcholy reprezentují (zleva) množiny a (vpravo) prvky naší úlohy ac
• ostatní hrany mimo zdrojové a stokové (kapacity 1) vždy spojují množinu Mj se všemi jejími prvky x\. □
Petr Hliněný,  Fl MU Brno, 2014
19/19
Fl: IB000: Toky v sítích