2. Toky v sítích (přednášel T. Valla, zapsali K. Vandas a J. Machálek)

Motivační úlohy:

• Mějme orientovaný graf se speciálními vrcholy Želivka a Kanál představující pražské vodovody. V tomto grafu budou vrcholy vodovodními stanicemi a hrany trubkami mezi nimi. Kolik vody proteče ze Želivky do Kanálu?

• Mějme orientovaný graf představující železniční síť; graf má význačné vrcholy Moskva a Fronta, každá hrana grafu má kapacitu, kterou může uvézt. Kolik vojáků je schopna síť převézt z Moskvy a spotřebovat na Frontě?

Definice: Síť je uspořádaná čtveřice (G^{→}, z, s, c), kde G^{→} je orientovaný graf, z a s jsou jeho vrcholy (z(droj) a s(tok)) a c je kapacita sítě, kterou představuje funkce c :

E(G^{→}) → R_{0}^{+} .

Intuice: Toky v sítích představují rozvržení, jakým suroviny sítí potečou...

Příklad sítě. Čísla představují kapacity jednotlivých hran.

Definice: Tok je funkce E(G^{→}) → R taková, že

1. Tok každé hrany je omezen její kapacitou: 0 ≤ f(e) ≤ c(e)

2. ţKirchhoffův zákon� - nikde se neztrácejí suroviny:

∑_{(x,u)∈E} f(x, u) = ∑_{(u,x)∈E} f(u, x) ∀u ∈ V (G^{→}), u ≠ z, u ≠ s

Poznámka: Pokud bychom se chtěli v definici toku u bodu 2 vyhnout podmínkám pro z a s, můžeme zdroj a stok vzájemně propojit (pak jde o tzv. cirkulaci). Poznámka: V angličtině se obvykle zdroj značí ţs� a stok ţt� (zkratky source a sink, ovšem dvě stejná písmena by byla poněkud nepraktická…)

Příklad toku. Čísla představují ohodnocení funkcí toku (v závorkách jsou kapacity hran).

Definice: Velikost toku f je:

w(f) = ∑_{(z,x)∈E} f(z, x) − ∑_{(x,z)∈E} f(x, z)

Věta: Pro každou síť existuje maximální tok (bez důkazu). Idea důkazu: Dokáže se pomocí metod matematické analýzy s tím, že množina toků je kompaktní a funkce toků je spojitá… Intuice. Řez grafu je množina hran oddělující z(droj) a s(tok). Definice: Řez R v síti (G^{→}, z, s, c) je R ⊆ E(G^{→}) taková, že ∄ cesta ze z do s v grafu

(V (G^{→}), E(G^{→}) \ R).

Definice: Kapacita řezu c(R) = ∑_{(u,v∈R)} c(u, v). Věta (Hlavní věta o tocích, Ford-Fulkerson): Mějme S síť.

max_{f tok}w(f) = min_{R řez}c(R)

Intuice: Uvážíme-li množinu kapacit všech řezů, je zdola omezená množinou hodnot toků. Idea důkazu: Důkaz provedeme pomocí dokázání dvou neostrých nerovností. Důkaz: Pomocné značení: Zaveďme konvenci, že existují-li orientované hrany (u,v), u ∈ A, v ∈ B, značíme je S(A,B) (separátor). f(A, B) = ∑_{(u,v)∈E,u∈A,v∈B} f(u, v).

Lemma: A ⊆ V (G^{→}), z ∈ A, s ∉ A, f je tok. Potom platí, že
w(f) = f(A, V \ A) − f(V \ A, A)

Důkaz: Důkaz provedeme pomocí ţKirchhoffova zákonu� a definice velikosti toku:

∑_{(u,x)∈E} f(u, x) − ∑_{(x,u)∈E} f(x, u) = 0 ∀u ∈ A, u ≠ z, u ≠ s

∑_{(z,x)∈E} f(z, x) − ∑_{(x,z)∈E} f(x, z) = w(f)

Rovnice sečteme:

∑_{u∈A} ( ∑_{(u,x)∈E} f(u, x) − ∑_{(x,u)∈E} f(x, u)) = w(f)

Poznámka: Tato rovnice neznamená nic jiného, než že se hrany vedoucí z A do A jednou přičtou a jednou odečtou. Projeví se pouze hrany vedoucí dovnitř a ven z V \ A, takže toky vnitřních hran A se ţpožerou�. Z toho plyne:

f(A, V \ A) − f(V \ A, A) = ∑_{u∈A,v∉A} f(u, v) − ∑_{u∉A,v∈A} f(u, v) = w(f)

♡

Důsledek: Pokud f je tok, R je řez, pak platí: w(f) ≤ c(R). Důkaz: w(f) = f(A, V \A)−f(V \A, A) ≤ f(A, V \A) ≤ c(A, V \A) ≤ c(R)

♡

Redefinice: Cesta je odteď posloupnost navazujících hran, u kterých ignorujeme orientaci. Tyto cesty se obvykle nazývají ţzs-cesty�.

Příklad zs-cesty.

Definice: Cesta P ze z do s je nasycená, pokud

∃ e ∈ P {f(e) = c(e) … orientovaná po směru f(e) = 0 … orientovaná proti směru Jinak je cesta nenasycená. Definice: Tok je nasycený, pokud ∀ cesta P je nasycená. Věta: Tok f je nasycený ⇔ f je maximální. Navíc pro ∀ maximální tok f ∃ řez R, že w(f) = c(R). Důkaz: ţ⇐� sporem: Mějme tok f maximální a nenasycený ⇒ ∃ P nenasycená. Tuto cestu P budeme ţvylepšovat�. Zvolíme:

ε_{1} = min_{e∈P, po směru}{c(e) − f(e)}
ε_{2} = min_{e∈P, proti směru}{f(e)}
ε = min{ε_{1}, ε_{2}} > 0

Poslední ostrá nerovnost vyplývá z definice nenasycené cesty. Nyní vylepšíme tok f o ε: f → f′:

f′(e) = {f(e) + ε … e ∈ P po směru f(e) − ε … e ∈ P proti směru f(e) … e ∉ P

Nyní je potřeba ověřit, že f′ je skutečně tok:

0 ≤ f′(e) ≤ c(e) … platí stále díky volbě ε

Platnost ţKirchhoffova zákonu� ověříme rozborem případů:

Rozbor případů.

f′ je tedy tok, ovšem potom platí:

w(f′) = w(f) + ε ⇒ w(f′) > w(f) ⇒ SPOR

ţ⇒�: Uvážíme A ⊆ V (G^{→}), že ∀ v ∈ A ∃ nenasycená cesta ze z do v. z ∈ A, s ∉ A. S(A, V \ A) je hledaný řez R. Podle lemmatu:

w(f) = f(A, V \ A) − f(V \ A, A) = c(A, V \ A) = c(R)

Víme, že w(f) ≤ c(R). Stačilo uvážit nasycený tok f. Pak jsme sestrojili řez R a výraz přešel v rovnost c(R) = w(f) (a tedy je tok f maximální).

♡

Rozdělení V(G^{→}) na množinu A a V\A v důkazu hlavní věty o tocích.

Algoritmus: (Ford-Fulkerson algoritmus hledání maximálního toku)

1. f(e) := 0 ∀e ∈ E

2. while ∃ zlepšující cesta P, vylepši P jako v důkazu hlavní věty

3. f je maximální

Cvičení:

• Je pro přirozené kapacity F.F. algoritmus konečný? Ano - v každém zlepšujícím kroku algoritmu se celkový tok zvětší aspoň o 1. Protože máme horní odhad na maximální tok (např. součet kapacit všech hran), máme i horní odhad na dobu běhu algoritmu.

• Je F.F. algoritmus konečný pro racionální kapacity hran? Ano - všechny kapacity vynásobíme společným jmenovatelem a převedeme na předchozí případ (pro obecné kapacity ovšem takto definovaný F.F. algoritmus nemusí být konečný).

• Kolik kroků bude muset algoritmus na následující síti maximálně udělat, aby úspěšně doběhl? (2M kroků)

Příklad sítě. Kolik kroků musí maximálně udělat F.F. algoritmus?