Grafové algoritmy

Prohledávání do šířky BFS

$$\begin{array}{rl}& \text{BFS}\\ & \text{Vstup: Graf }G=(V,E)\text{ a pocˇaˊtecˇnıˊ vrchol }{v}_0\\ & \text{1. Pro vsˇechny vrcholy }v\in V:\\ & \text{2. }stav(v)\leftarrow nenalezen\acute{y}\\ & \text{3. }D(v)=\varnothing ,P(v)=\varnothing \\ & \text{4. }stav(v_0)\leftarrow otev\check{r}en\acute{y}\\ & \text{5. }\text{Zalozˇıˊme frontu }Q\text{ s vrcholem }{v}_0\\ & \text{6. Dokud nenıˊ fronta }Q\text{ praˊzdnaˊ}:\\ & \text{7. }\text{Odebereme vrchol z }Q\text{ a oznacˇıˊme ho }v:\\ & \text{8. }\forall w,\text{ naˊslednıˊky v}:\\ & \text{9. }\text{Je-li }stav(w)=nenalezen\acute{y}:\\ & \text{10. }stav(w)\leftarrow oteve\check{r}en\acute{y}\\ & \text{11. }D(w)\leftarrow D(v)+1,P(w)\leftarrow v\\ & \text{12. }\text{Prˇidaˊme }w\text{ do fronty }Q\text{.}\\ & \text{13. }stav(v)\leftarrow uzav\check{r}en\acute{y}\end{array}$$

Složitost: BFS doběhne v čase $O(m+n)$ a spotřebuje $\Theta (n+m)$ paměti.

Prohledávání hloubky DFS

$$\begin{array}{rl}& \text{DFS}\\ & \text{Vstup: Graf }G=(V,E)\text{ a pocˇaˊtecˇnıˊ vrchol }{v}_0\\ & \text{1. Pro vsˇechny vrcholy }v\in V:\\ & \text{2. }stav(v)\leftarrow nenalezen\acute{y}\\ & \text{3. }D(v)=\varnothing ,P(v)=\varnothing \\ & \text{4. }stav(v_0)\leftarrow otev\check{r}en\acute{y}\\ & \text{5. }\text{Zalozˇıˊme zaˊsobnıˊk }S\text{ s vrcholem }{v}_0\\ & \text{6. Dokud nenıˊ zaˊsobnıˊk }S\text{ praˊzdnyˊ}:\\ & \text{7. }\text{Odebereme vrchol z }S\text{ a oznacˇıˊme ho }v:\\ & \text{8. }\forall w,\text{ naˊslednıˊky v}:\\ & \text{9. }\text{Je-li }stav(w)=nenalezen\acute{y}:\\ & \text{10. }stav(w)\leftarrow oteve\check{r}en\acute{y}\\ & \text{11. }D(w)\leftarrow D(v)+1,P(w)\leftarrow v\\ & \text{12. }\text{Prˇidaˊme }w\text{ do zaˊsobnıˊku }S\text{.}\\ & \text{13. }stav(v)\leftarrow uzav\check{r}en\acute{y}\end{array}$$

Složitost: BFS doběhne v čase $O(m+n)$ a spotřebuje $\Theta (n+m)$ paměti.

---

Topologické třídění orientovaných grafů

Definice: Mějme orientovaný graf $G=(V,E)$. Řekneme, že topologické uspořádání grafu je lineární uspořádání $\le$ na množině $V$ takové, že:

$$\forall (u,v)\in E:u\le v$$

Tzn. každý vrchol musí být ve výstupním pořadí dříve než jeho následníci.

Poznámky:

• Takové uspořádání existuje právě tehdy, když graf neobsahuje orientovaný cyklus, tj. je acyklický (DAG).
• Topologické uspořádání obecně není jediné a může jich být více.

Konstrukce topologického uspořádání

1. Odtrhávání zdrojů

Zdrojem nazveme vrchol, jehož vstupní stupeň (počet hran do něj) je $0$.

$$\begin{array}{rl}& \text{TopSortRemoveSources}\\ & \text{Vstup: Orientovanyˊ graf }G=(V,E)\\ & \text{Vyˊstup: Topologickeˊ usporˇaˊdaˊnıˊ vrcholu˚ }\\ & \text{1. }\text{Inicializujeme frontu }Q\text{ zdrojovyˊmi vrcholy (stupenˇ 0)}\\ & \text{2. }T\leftarrow []\text{ (vyˊstupnıˊ seznam)}\\ & \text{3. }\text{Dokud }Q\text{ nenıˊ praˊzdnaˊ:}\\ & \text{4. }u\leftarrow Q.\text{pop()}\\ & \text{5. }T.\text{append}(u)\\ & \text{6. }\text{Pro kazˇdeˊho souseda }v\text{ vrcholu }u:\\ & \text{7. }\text{Odebereme hranu }(u,v)\text{ z }G\\ & \text{8. }\text{Pokud stupenˇ }v\text{ klesne na 0: prˇidaˊme }v\text{ do }Q\\ & \text{9. }\text{Pokud }|T|<|V|\text{ ⇒ graf maˊ cyklus ⇒ zˇaˊdneˊ topologickeˊ usporˇaˊdaˊnıˊ}\\ & \text{10.}\text{Jinak vraˊtıˊme }T\end{array}$$

2. Pomocí hloubkového prohledávání (DFS)

Při zpětném návratu z DFS (post-order) přidáme vrcholy do zásobníku. Výstupem je zásobník v opačném pořadí, tedy topologické uspořádání.

$$\begin{array}{rl}& \text{TopSortDFS}\\ & \text{Vstup: Orientovanyˊ graf }G=(V,E)\\ & \text{Vyˊstup: Topologickeˊ usporˇaˊdaˊnıˊ vrcholu˚ }\\ & \text{1. }\text{Navsˇtıˊveno }\leftarrow \varnothing ,S\leftarrow []\\ & \text{2. }\text{Pro kazˇdeˊ }v\in V:\\ & \text{3. }\text{Pokud }v\notin \text{Navsˇtıˊveno: DFS(v)}\\ & \text{4. }\text{Funkce DFS(u):}\\ & \text{5. }\text{Oznacˇıˊme }u\text{ jako navsˇtıˊvenyˊ}\\ & \text{6. }\text{Pro kazˇdeˊho souseda }v\text{ z }u:\\ & \text{7. }\text{Pokud }v\notin \text{Navsˇtıˊveno: DFS(v)}\\ & \text{8. }\text{Po dokoncˇenıˊ rekurze prˇidaˊme }u\text{ do zaˊsobnıˊku }S\\ & \text{9. }\text{Vyˊstup: Reverznıˊ obsah zaˊsobnıˊku }S\end{array}$$

Příklad

Mějme graf s vrcholy a hranami:

• Vrcholy: $V=\{A,B,C,D\}$
• Hrany: $E=\{(A,B),(A,C),(C,D),(B,D)\}$ Topologická uspořádání mohou být:
• $A,B,C,D$
• $A,C,B,D$

Využití

• Plánování úloh (např. s předchůdci)
• Sestavování rozvrhů a kompilace programů (závislosti mezi jednotkami)
• Detekce cyklů v orientovaných grafech Poznámka: Oba algoritmy mají časovou složitost $\mathcal{O}(|V|+|E|)$.

---

Hledání cest v ohodnocených grafech

Definujeme funkcí $l:E\to \mathbb{R}$ pro každou hranu a tomu řekneme délka.

Dijkstrův algoritmus

$$\begin{array}{rl}& \text{Dijkstra}\\ & \text{Vstup: Orientovanyˊ graf }G=(V,E)\\ & \text{Vyˊstup: Pole vzdaˊlenostıˊ vrcholu˚ h,pole prˇedchu˚dcu˚ }P\\ & \text{1. Pro vsˇechny vrcholy }v\in V:\\ & \text{2. }stav(v)\leftarrow nenalezen\acute{y}\\ & \text{3. }h(v)=+\infty \\ & \text{4. }P(v)=nedefinov\acute{a}no\\ & \text{5. }stav(v_0)\leftarrow otev\check{r}en\acute{y}\\ & \text{6. }h(v_0)\leftarrow 0\\ & \text{7. Dokud existujıˊ otevrˇeneˊ vrcholy}:\\ & \text{8. }\text{Vybereme otevrˇenyˊ vrchol }v:\\ & \text{9. }\forall w,\text{ naˊslednıˊky v}:\\ & \text{10. }\text{Pokud }h(w)>h(v)+l(v,w):\\ & \text{11. }stav(w)\leftarrow oteve\check{r}en\acute{y}\\ & \text{12. }h(w)\leftarrow h(v)+l(v,w)\\ & \text{13. }P(w)\leftarrow v\\ & \text{14. }stav(v)\leftarrow uzav\check{r}en\acute{y}\end{array}$$

Pro kladné délky hran dává algoritmus dobré výsledky a udělá to v čase $O(n^2)$, avšak na-implementujeme-li algoritmus s haldou, tak můžeme časovou složitost zlepšit na $O(n\cdot T_{Insert}+n\cdot T_{ExtractMin}+m\cdot T_{Decrease})$ a s binární haldou to vychází $O((n+m)\log n)$.

Bellman-Fordův algoritmus

Relaxační algoritmy jsou obecnou třídou algoritmů pro hledání nejkratších cest. Dijkstrův algoritmus je speciálním případem relaxačního algoritmu, který funguje pro nezáporné hrany. Chceme-li pracovat i se zápornými hranami (ale bez záporných cyklů), použijeme Bellman-Fordův algoritmus.

Přiřadíme každému vrcholu ohodnocení $h(v)$ – odhad vzdálenosti z počátečního vrcholu $v_0$. Na začátku:

• $h(v_0)=0$
• $h(v)=+\infty$ pro všechna ostatní $v$
• $P(v)=\text{nedefinovaˊno}$ (předchůdci) Poté relaxujeme hrany – hledáme, zda by přes nějakou hranu nevedla kratší cesta do cílového vrcholu.

$$\begin{array}{rl}& \text{BellmanFord}\\ & \text{Vstup: Orientovanyˊ graf }G=(V,E),\text{ ohodnocenıˊ hran }\ell (e),\text{ startovnıˊ vrchol }{v}_0\\ & \text{Vyˊstup: Nejkratsˇıˊ vzdaˊlenosti }h(v)\text{ z }{v}_0\text{ a pole prˇedchu˚dcu˚ }P(v)\\ & 1.\text{Pro kazˇdyˊ }v\in V:h(v)\leftarrow +\infty ,P(v)\leftarrow \text{nedef}\\ & 2.h(v_0)\leftarrow 0\\ & 3.\text{Opakuj }|V|-1\text{ kraˊt:}\\ & 4.\text{Pro kazˇdou hranu }(u,v)\in E:\\ & 5.\text{Pokud }h(v)>h(u)+\ell (u,v):\\ & 6.h(v)\leftarrow h(u)+\ell (u,v)\\ & 7.P(v)\leftarrow u\\ & 8.\text{// Detekce zaˊporneˊho cyklu}\\ & 9.\text{Pro kazˇdou hranu }(u,v)\in E:\\ & 10.\text{Pokud }h(v)>h(u)+\ell (u,v):\\ & 11.\text{Graf obsahuje zaˊpornyˊ cyklus – chyba}\end{array}$$

Správnost a analýza

• Fáze výpočtu: Fáze $F_0$ otevře pouze $v_0$, každá další fáze $F_i$ relaxuje vrcholy otevřené během $F_{i-1}$.
• Invariant F (fáze): Po $i$-té fázi platí: $h(v)\le$ délka nejkratší cesty z $v_0$ do $v$ s nejvýše $i$ hranami.
• Zastavení: Pokud graf neobsahuje záporné cykly, algoritmus se zastaví po $|V|$ fázích.
• Složitost: Každou hranu relaxujeme nejvýše $|V|-1$ krát → časová složitost $O(nm)$, kde $n=|V|,m=|E|$.

Výhody a použití

• Funguje i pro záporné hrany.
• Detekuje záporné cykly.

Porovnání s Dijkstrovým algoritmem

Vlastnost	Dijkstra	Bellman-Ford
Záporné hrany	❌	✅
Detekce záp. cyklu	❌	✅
Složitost	$O(n\log n+m)$ (s fib. haldou)	$O(nm)$
Strategická volba vrcholu	min. $h(v)$ (pomocí haldy)	FIFO fronta

---

Minimální kostry grafu

Jako vážené grafu bereme takové, které mají nějakou funkci, která umí ohodnotit jejich hrany.

Jarníkův algoritmus

$$\begin{array}{rl}& \text{Jarnıˊk}\\ & \text{Vstup: Souvislyˊ graf }G=(V,E)\\ & \text{Vyˊstup: Minimaˊlnıˊ kostra }T\\ & 1.v_0\leftarrow \text{libovolnyˊ vrchol grafu}\\ & 2.T\leftarrow \text{strom obsahujıˊcıˊ }{v}_0\text{ a zˇaˊdneˊ hrany}\\ & 3.\text{Dokud existuje hrana }uv\text{ takovaˊ, zˇe }u\in V(T),v\notin V(T):\\ & 4.\text{Nejlehcˇıˊ takovou hranu prˇidaˊme do }T\text{.}\end{array}$$

Takže vlastně je typický hladový algoritmus. Jarníkův algoritmus se po nejvýše $n$ iteracích zastaví a vydá nějakou kostru zadaného grafu a taková kostra je z výběru vrcholů minimální. Časová složitost je $O(nm)$ protože $n$-krát musíme překontrolovat $m$ hran.

Borůvkův algoritmus

Jedná se o “paralelní verzi Jarníkova algoritmu”, kdy pěstujeme minimální kostřičky a ty spojujeme dohromady.

$$\begin{array}{rl}& \text{Boru˚vka}\\ & \text{Vstup: Souvislyˊ graf }G=(V,E)\text{ s unikaˊtnıˊmi vaˊhami}\\ & \text{Vyˊstup: Minimaˊlnıˊ kostra }T\\ & 1.T\leftarrow (V,\varnothing )\\ & 2.\text{Dokud T nenıˊ souvislyˊ}:\\ & 3.\text{Rozlozˇıˊme T na komponenty souvislosti }{T}_1,\dots ,T_k\text{.}\\ & 4.\text{Pro kazˇdyˊ strom }T\text{ najdeme nejlehcˇıˊ z hran mezi }{T}_i\text{ a zbytkem grafu a oznacˇıˊme ji ei.}\\ & 5.\text{Prˇidaˊme do }T\text{ hrany }\{e_1,\dots ,e_n\}\text{.}\end{array}$$

Tvrzení: Borůvkův algoritmus skončí po nejvýše $\lfloor \log n\rfloor$ iteracích a najde minimální kostru. Minimální kostra to jistě je, protože máme-li nějaký řez $R$ s nejlehčí hranou $e$, tak pak $e$ je součástí minimální kostry a taková $e$ my vlastně vždy vybíráme. Borůvka tedy běží v čase $O(n\cdot \log n)$

---

Toky v sítích a Ford-Fulkerson algoritmus

Toky v sítích Chceme najít maximální tok ze zdroje $z$ do stoku $s$ v orientované síti s kapacitami na hranách. Začneme nulovým tokem a postupně ho zlepšujeme, dokud už dál zlepšit nejde. Každý takový “zlepšovák” využívá tzv. zlepšující (augmentační) cestu, po které lze tok ještě zvětšit.

Klíčový nápad: povolíme tok nejen po směru hrany, ale i proti jejímu směru — v tom případě tok odčítáme.

Pro každou hranu $uv$ definujeme rezervu jako:

• $r(uv):=c(uv)-f(uv)+f(vu)$

To odpovídá:

• kolik můžeme přidat po směru $uv$: $c(uv)-f(uv)$
• kolik můžeme ubrat proti směru $vu$: $f(vu)$ Hrana s $r(uv)>0$ je nenasycená, jinak nasycená.

$$\begin{array}{rl}& \text{FordFulkerson}\\ & \text{Vstup: Sıˊtˇ }(V,E),\text{ kapacitnıˊ funkce }c(e),\text{ zdroj }z,\text{ stok }s\\ & \text{Vyˊstup: Maximaˊlnıˊ tok }f\\ & 1.\text{Pro kazˇdou hranu }e\in E:f(e)\leftarrow 0\\ & 2.\text{Dokud existuje nenasycenaˊ cesta }P\text{ z }z\text{ do }s:\\ & 3.\epsilon \leftarrow \min \{r(e)\mid e\in P\}\text{// rezerva cesty}\\ & 4.\text{Pro kazˇdou hranu }uv\in P:\\ & 5.\delta \leftarrow \min \{f(vu),\epsilon \}\text{// kolik lze odecˇıˊst proti smeˇru}\\ & 6.f(vu)\leftarrow f(vu)-\delta \\ & 7.f(uv)\leftarrow f(uv)+(\epsilon -\delta )\\ & 8.\text{Vraˊtıˊme tok }f\end{array}$$

Po každém kroku se velikost toku zvětší o ε – tedy o kladnou hodnotu. Pokud jsou kapacity celočíselné, tok poroste alespoň o 1, takže algoritmus musí skončit (nejvýše tolik kroků, kolik je součet kapacit všech hran do stoku).

Po zastavení víme:

• žádná nenasycená cesta neexistuje $⟹$ nelze dál zlepšovat
• definujeme množiny:
  • $A:=$ vrcholy dosažitelné ze zdroje přes nenasycené cesty
  • $B:=V\setminus A$

Pak množina hran z $A$ do $B$ tvoří řez, který je:

• minimální, protože žádná hrana nemá rezervu (všechny nasycené)
• odpovídá toku – po řezu proudí tok rovný jeho kapacitě

Z toho plyne:

• žádný jiný tok nemůže být větší
• náš tok je maximální

Správnost a zastavení

• Pro celočíselné kapacity: algoritmus se jistě zastaví a tok je celočíselný.
• Pro racionální kapacity: přeškálujeme kapacity na celá čísla a aplikujeme algoritmus stejně.
• Pro iracionální kapacity: algoritmus nemusí skončit ani konvergovat. Poznámka:
• Pokud vybíráme vždy nejkratší nenasycenou cestu, získáme tzv. Edmonds-Karpův algoritmus, který je efektivnější: $O(n{m}^2)$.

---

Komponenty silné souvislosti v orientovaných grafech

Definice: Silně souvislá komponenta (SSC) je maximální množina vrcholů, ve které existuje cesta mezi každou dvojicí vrcholů v obou směrech.

$$\begin{array}{rl}& \text{KompSilneˊSouvislosti}\\ & \text{Vstup: Orientovanyˊ graf }G=(V,E)\\ & 1.\text{Sestrojıˊme graf }{G}^T\text{ s obraˊcenyˊmi hranami.}\\ & 2.Z\leftarrow \text{praˊzdnyˊ zaˊsobnıˊk}\\ & 3.\forall v\in V:\text{komp}(v)\leftarrow \text{nedefinovaˊno}\\ & 4.\text{Spousˇtıˊme DFS v }{G}^T\text{ opakovaneˇ, dokud neprozkoumaˊme vsˇechny vrcholy.}\\ & 5.\text{Prˇi opusˇteˇnıˊ vrcholu }v\text{ ho vlozˇıˊme do zaˊsobnıˊku }Z\\ & 6.\text{Zaˊsobnıˊk Z obsahuje vrcholy setrˇıˊdeˇneˊ podle }\text{out}(v)\\ & 7.\text{Dokud }Z\text{ nenıˊ praˊzdnyˊ:}\\ & 8.v\leftarrow Z.\text{pop}()\\ & 9.\text{Pokud }\text{komp}(v)=\text{nedefinovaˊno:}\\ & 10.\text{Spustıˊme DFS ve }G\text{ z vrcholu }v\text{, prˇicˇemzˇ vstupujeme jen do vrcholu˚ }\\ & \text{s }\text{komp}(u)=\text{nedefinovaˊno a nastavujeme }\text{komp}(u)\leftarrow v\end{array}$$

Složitost: $O(n+m)$ – dvě DFS a přetočení hran.

---

Dinicův algoritmus pro maximální tok

Síť je orientovaný graf s kapacitami a určeným zdrojem a stokem:

• $G=(V,E)$ je orientovaný graf.
• $z\in V$ je zdroj.
• $s\in V$ je stok.
• $c:E\to {\mathbb{R}}_{\ge 0}$ je funkce udávající kapacitu každé hrany.
• $f:E\to {\mathbb{R}}_{\ge 0}$ je tok, pokud:
  • $\forall e\in E:0\le f(e)\le c(e)\text{(omezujeme tok kapacitami)}$
  • $\forall v\in V\setminus \{z,s\}:{\sum }_{u:(u,v)\in E}f(uv)={\sum }_{w:(v,w)\in E}f(vw)\text{(Kirchhoffu˚v zaˊkon)}$ Velikost toku je definována jako:

$$|f|:=\sum _{v:(z,v)\in E}f(zv)-\sum _{u:(u,z)\in E}f(uz)$$

Rezerva udává, o kolik lze zvýšit tok přes hranu (nebo snížit v protisměru):

$$r(uv):=c(uv)-f(uv)+f(vu)$$

• Hrana je nasycená, pokud $r(uv)=0$.
• Cesta je nenasycená, pokud má všechny rezervy kladné.

Intuice Dinicova algoritmu

• Vylepšujeme tok, dokud existují nenasycené cesty.
• Místo náhodných cest používáme jen nejkratší cesty — to omezuje počet fází.
• V každé fázi hledáme blokující tok: tok, který „zasytí“ alespoň jednu hranu každé cesty.
• Postupně tak zvyšujeme minimální délku zlepšujících cest → algoritmus skončí.

$$\begin{array}{rl}& \text{Dinic}\\ & \text{Vstup: Sıˊtˇ }(V,E,z,s,c)\\ & \text{Vyˊstup: Maximaˊlnıˊ tok }f\\ & 1.f\leftarrow 0\\ & 2.\text{Opakujeme:}\\ & 3.\text{Sestrojıˊme sıˊtˇ rezerv }R\text{ a odstranıˊme hrany s nulovou rezervou}\\ & 4.\ell \leftarrow \text{deˊlka nejkratsˇıˊ cesty ze }z\text{ do }s\text{ v }R\\ & 5.\text{Pokud takovaˊ cesta neexistuje: }\text{vraˊtıˊme }f\\ & 6.\text{Procˇistıˊme sıˊtˇ (ponechaˊme jen nejkratsˇıˊ cesty)}\\ & 7.g\leftarrow \text{Blokujıˊcıˊ tok v procˇisˇteˇneˊ sıˊti }R\\ & 8.f\leftarrow f+g\end{array}$$

---

$$\begin{array}{rl}& \text{CˇisˇteˇnıˊSıˊteˇ}\\ & 1.\text{Rozdeˇlıˊme vrcholy do vrstev podle vzdaˊlenosti od }z\\ & 2.\text{Odstranıˊme vrcholy za vrstvou }\ell \text{ (tj. vzdaˊlenost > }\ell )\\ & 3.\text{Odstranıˊme hrany vedoucıˊ do stejneˊ nebo prˇedchozıˊ vrstvy}\\ & 4.\text{Fronta }F\leftarrow \{v\ne z,s\mid {\mathrm{deg}}^{+}(v)=0\}\\ & 5.\text{Dokud }F\ne \varnothing :\\ & 6.v\leftarrow F.\text{pop()}\\ & 7.\text{Odstranˇ }v\text{ a vsˇechny hrany incidentnıˊ do }v\\ & 8.\text{Pokud }{\mathrm{deg}}^{+}(u)=0\Rightarrow F.\text{push}(u)\end{array}$$

---

Hledání blokujícího toku

$$\begin{array}{rl}& \text{BlokujıˊcıˊTok}\\ & \text{Vstup: Procˇisˇteˇnaˊ sıˊtˇ rezerv }R\\ & \text{Vyˊstup: Blokujıˊcıˊ tok }g\\ & 1.g\leftarrow 0\\ & 2.\text{Dokud existuje orientovanaˊ cesta }P\text{ z }z\text{ do }s:\\ & 3.\epsilon \leftarrow \underset{e\in P}{\min }(r(e)-g(e))\\ & 4.\forall e\in P:g(e)\leftarrow g(e)+\epsilon \\ & 5.\text{Pokud }g(e)=r(e)\Rightarrow \text{odstranˇ hranu }e\\ & 6.\text{Docˇisti sıˊtˇ (jako vyˊsˇe)}\\ & 7.\text{return }g\end{array}$$

---

Intuice a důkazy korektnosti

Lemma K: Korektnost

Pokud algoritmus skončí, neexistuje cesta ze $z$ do $s$ v síti rezerv $⟹$ žádné další zlepšení toku není možné $⟹$ výstupní tok je maximální.

Lemma C: Délka se prodlužuje

Po každé fázi se nejkratší cesta prodlouží alespoň o 1 (protože jsme nasytili všechny dosavadní nejkratší).

Lemma S: Čas jedné fáze

Každá fáze trvá $O(nm)$, protože konstrukce vrstvené sítě a blokujícího toku lze provést v lineárním čase vzhledem k počtu hran a vrcholů.

---

Věta: Složitost Dinicova algoritmu

• Nejvýše $n$ fází (protože délka nejkratší cesty se nejvýše $n$-krát prodlouží)
• Každá fáze trvá $O(mn)$
• $\Rightarrow O(n^{2}m)$

---

Goldbergův algoritmus pro hledání maximálního toku

Definice

Síť: Orientovaný graf $G=(V,E)$ s kapacitní funkcí $c:E\to {\mathbb{R}}_0^{+}$, zdrojovým vrcholem $z\in V$ a stokem $s\in V$.

Vlna: Funkce $f:E\to {\mathbb{R}}_0^{+}$ je vlna, pokud platí:

• $\forall e\in E:f(e)\le c(e)$ (nepřekračuje kapacitu hran),
• $\forall v\in V\setminus \{z,s\}:f^{\Delta }(v)\ge 0$, kde $f^{\Delta }(v)$ je přebytek toku ve vrcholu $v$.

Každý tok je vlnou, ale ne každá vlna je tok – přebytky mohou být nenulové.

Rezerva: Pro hranu $e=uv$ je:

$$r(uv)=c(uv)-f(uv)$$

Převedení přebytku: Můžeme převést přebytek po hraně $uv$, pokud:

• $f^{\Delta }(u)>0$
• $r(uv)>0$

Pak pošleme tok ve výši:

$$\delta =\min (f^{\Delta }(u),r(uv))$$

a aktualizujeme:

$$\begin{array}{rl}{f}^{\Delta }(u)& \leftarrow f^{\Delta }(u)-\delta \\ f^{\Delta }(v)& \leftarrow f^{\Delta }(v)+\delta \\ r(uv)& \leftarrow r(uv)-\delta \\ r(vu)& \leftarrow r(vu)+\delta \end{array}$$

Intuice

Místo hledání cest postupně přesouváme přebytky ze zdroje k stoku nebo zpět. Abychom zabránili “cestování v kruhu”, zavádíme výšky $h(v)$ a dovolujeme přesun pouze dolů (tj. $h(u)>h(v)$).

Když přebytek uvízne (není kam přelévat dolů), zvedneme výšku vrcholu.

$$\begin{array}{rl}& \text{Goldberg}\\ & \text{Vstup: Sıˊtˇ }(V,E,z,s,c)\\ & \text{Vyˊstup: Maximaˊlnıˊ tok }f\\ & 1.\text{Pro kazˇdyˊ vrchol }v\in V:f^{\Delta }(v)\leftarrow 0,f\leftarrow 0\\ & 2.\text{Inicializace vyˊsˇek: }h(z)\leftarrow |V|,h(v)\leftarrow 0\text{ pro }v\ne z\\ & 3.\text{Nastavıˊme }f(zv)\leftarrow c(zv),\forall zv\in E\\ & 4.\text{Pro kazˇdeˊ takoveˊ }v:f^{\Delta }(v)\leftarrow c(zv)\\ & 5.\text{Dokud existuje }u\in V\setminus \{z,s\}\text{ s }{f}^{\Delta }(u)>0:\\ & 6.\text{Pokud existuje }uv\in E\text{ s }r(uv)>0\text{ a }h(u)>h(v):\\ & 7.\delta \leftarrow \min (f^{\Delta }(u),r(uv))\\ & 8.f(uv)\leftarrow f(uv)+\delta \\ & 9.f^{\Delta }(u)\leftarrow f^{\Delta }(u)-\delta \\ & 10.f^{\Delta }(v)\leftarrow f^{\Delta }(v)+\delta \\ & 11.\text{Jinak: }h(u)\leftarrow h(u)+1\end{array}$$

---

Invariant A (základní):

• $f$ je vždy vlna.
• Výšky $h(v)$ nikdy neklesají.
• $h(z)=n$, $h(s)=0$.
• $f^{\Delta }(v)\ge 0$ pro $v\ne z$.

Invariant S (spád):

Neexistuje hrana $uv$ s kladnou rezervou a spádem $h(u)-h(v)>1$.

Invariant C (cesta do zdroje):

Z každého vrcholu s $f^{\Delta }(v)>0$ existuje nenasycená cesta do $z$.

Invariant V (výšky):

$$\forall v\in V:h(v)\le 2n$$

---

Důkaz korektnosti (Lemma K)

Když algoritmus skončí:

• Přebytek zůstává jen ve $z$ a $s$.
• Tedy Kirchhoffovy zákony platí → $f$ je tok.
• Pokud by nebyl maximální, existuje nenasycená cesta z $z$ do $s$.
  • Ta by překonávala výšku $n$, ale měla by nejvýš $n-1$ hran.
  • Musela by mít hranu se spádem alespoň $2$ → spor s invariantem S.

---

Lemma Z (počet zvednutí):

$$\text{Kazˇdyˊ vrchol }v\text{ mu˚zˇe byˊt zvednut nejvyˊsˇe }2n\text{ kraˊt}.$$

Idea důkazu:

• Zvedáme výšku pouze tehdy, když je přebytek a nelze ho odvést žádnou hranou “dolů”.
• Díky invariantu C víme, že když je přebytek, existuje cesta do zdroje.
• Tato cesta překonává výšku nejvýše $n$, takže pokud by výška překročila $2n$, musela by obsahovat hranu se spádem $\ge 2$ – to odporuje invariantu S.

Lemma S (nasycená převedení):

$$\text{Kazˇdou hranu lze nasyceneˇ pouzˇıˊt nejvyˊsˇe }n\text{ kraˊt }\Rightarrow \text{ celkem }nm\text{ nasycenyˊch prˇevedenıˊ}.$$

Idea důkazu:

• Mezi dvěma nasycenými převedeními po hraně $uv$ musí být vrchol $u$ zvednut o alespoň 2 (kvůli spádu).
• Výška $u$ je omezena lemmatem Z ($\le 2n$), takže mezi každými dvěma nasycenými převedeními je minimálně 2 zvednutí.
• Tedy pro každou hranu $uv$ maximálně $n$ takových akcí.

Lemma N (nenasycená převedení):

$$\text{Pocˇet vsˇech nenasycenyˊch prˇevedenıˊ je }\mathcal{O}(n^{2}m).$$

Idea důkazu – potenciálová metoda: Zavádíme potenciál:

$$\Phi :=\sum _{v\ne z,s,f^{\Delta }(v)>0}h(v)$$

Pozorování:

• Potenciál se nikdy nezvýší příliš:
  • Zvednutí: $+1$ (max $2n^2$ ×)
  • Nasycené převedení: maximálně $+2n$ (celkem max $2n^{2}m$)
• Ale každé nenasycené převedení ho sníží minimálně o 1 (odebereme $h(u)$ a přidáme max $h(v)=h(u)-1$). Z toho plyne, že nenasycených převedení nemůže být více než celkové zvýšení potenciálu, tedy $\mathcal{O}(n^{2}m)$.

Věta (složitost Goldbergova algoritmu):

$$\text{Goldbergu˚v algoritmus beˇzˇıˊ v cˇase }\mathcal{O}(n^{2}m)$$

Idea důkazu:

• Sečteme počet jednotlivých operací a jejich čas:
  • Zvednutí: $\le 2n^2$ × (každé v čase $O(n)$) → $O(n^3)$
  • Nasycené převedení: $\le nm$ × (každé v čase $O(1)$) → $O(nm)$
  • Nenasycené převedení: $O(n^{2}m)$ × (každé v čase $O(1)$) → $O(n^{2}m)$
• Největší složitost dominuje, tedy výsledná složitost je:

$$\boxed{\mathcal{O}(n^{2}m)}$$

---

Změny v analýze algoritmů pro toky

1. Pokud jsou všechny kapacity hran celočíselné:

Pokud jsou všechny kapacity hran kladná celá čísla, pak Ford-Fulkersonův algoritmus skončí po konečném počtu kroků. Důkaz (intuice): Každá augmentační cesta zvýší tok o alespoň 1 jednotku (protože nejmenší nenulová rezerva je alespoň 1). Maximální možný tok je nejvýše součet kapacit hran ze zdroje — tj. nějaké konečné číslo $C$.

• Po každé augmentaci se hodnota toku zvětší alespoň o 1.
• Proto algoritmus skončí nejvýše po $C$ krocích.
• Pokud je maximální tok $F$, pak složitost je $O(m\cdot F)$, kde $m$ je počet hran a $F$ celkový maximální tok.

Slabina: $F$ může být exponenciálně velké vzhledem k velikosti vstupu (např. pokud kapacity jsou velká čísla), proto algoritmus není polynomiální.

---

2. Pokud se Ford-Fulkerson používá s BFS (Edmonds-Karp algoritmus):

Ford-Fulkerson s výběrem augmentační cesty přes BFS (Edmonds-Karp) má časovou složitost:

$$O(n\cdot m^2)$$

Každá augmentační cesta je nejkratší (v počtu hran). Po každé augmentaci se délka nejkratší augmentační cesty nikdy nezmenší. Navíc:

• Délka augmentační cesty se může zvýšit nejvýše $n$-krát.
• Každá hrana může být “kritická” (tj. její kapacita se stane nulovou na augmentační cestě) nejvýše $O(n)$-krát.
• Jelikož je hran $m$, vznikne nejvýše $O(n\cdot m)$ augmentačních kroků. A každý BFS běží v $O(m)$, takže složitost je $O(n\cdot m^2)$.

---

Párování v bipartitních grafech jako problém maximálního toku

Definice párování

• Párování je množina hran $F\subseteq E$, kde žádné dvě hrany nesdílejí vrchol.
• Velikost párování je $|F|$.

Převod bipartitního grafu na síť

Z bipartitního grafu $G=(V,E)$ vytvoříme síť $(V^{\prime },E^{\prime },z,s,c)$:

• Najdeme levou partitu $X$ a pravou partitu $Y$.
• Hrany orientujeme z $X$ do $Y$.
• Přidáme:
  • zdroj $z$ a hrany $z\to x$ pro každé $x\in X$,
  • stok $s$ a hrany $y\to s$ pro každé $y\in Y$.
• Všechny hrany mají kapacitu 1: $c(e)=1$ pro každé $e\in E^{\prime }$.

---

Korektnost: párování odpovídá toku

Tvrdíme: Po výpočtu maximálního toku odpovídá každá hrana s tokem 1 hraně v párování. Důkaz:

• Každý vrchol $x\in X$ má z $z$ maximálně jeden tok → může být spojen s nejvýše jedním $y$.
• Každý vrchol $y\in Y$ má do $s$ maximálně jeden tok → může být spojen s nejvýše jedním $x$.
• Proto žádné dvě hrany netvoří konflikt na vrcholu: opravdu jde o párování.

---

Úplnost: každé párování je tok

Tvrdíme: Každému párování $F$ odpovídá celočíselný tok. Důkaz:

• Hranu $(x,y)\in F$ nahradíme třemi hranami: $z\to x$, $x\to y$, $y\to s$, každou s tokem 1.
• Celkový tok odpovídá velikosti párování.

Tím vzniká bijekce mezi množinou párování a množinou celočíselných toků velikosti $k$.

---

Časová složitost

Věta: Ford-Fulkerson na síti s jednotkovými kapacitami najde maximální tok v čase $O(nm)$. Důkaz:

• BFS najde augmentační cestu v $O(m)$.
• V každém kroku se tok zvětší o 1.
• Maximální tok je nejvýše $n$ (víc než $|X|$ hrany nemůžeme vybrat).
• Celkem tedy $O(n)$ kroků $\Rightarrow$ celkem $O(nm)$.

---

Důsledek: Algoritmus pro párování

Tvrzení: Největší párování v bipartitním grafu lze najít v čase $O(nm)$. Důkaz:

• Převod na síť: $O(n+m)$.
• Maximální tok: $O(nm)$.
• Převod zpět na párování: $O(m)$.
• Celkově tedy $O(nm)$.