# 7. Grafy a grafové algoritmy (95%)
###### tags: `algo`, `IB000`, `IB002`, `IV003`

:::warning

* Reprezentace grafů
* Souvislost grafu, rovinné grafy
* Prohledávání grafu do šířky a do hloubky, nejkratší vzdálenosti, kostry, toky v sítích
* Algoritmy:
* Bellman-Ford
* Dijkstra
* Ford-Fulkerson
* Push-Relabel
* Maximální párování v bipartitních grafech.

:::
---
### Formalizace základných grafových pojmov
:::success
* Graf je usporiadana dvojica množín vrcholov a hrán, značíme $(V,E)$
* $V$ sú vrcholy
* $E$ hrany - $E \subseteq V \times V$
* orientovaný graf
* $E \subseteq \{(u,v)|u,v \in V\}$ - záleží na poradí u,v
* neorientovaný graf
* $E \subseteq \{\{u,v\}|u,v \in V\}$ - nezáleží na poradí u,v
* **Vrchol**
* jeden z prvků množiny určující graf
* mohou z něj vést hrany
* stupeň vrcholu $deg(v)$ je velikost jeho sousedství
* Pokud jsou dva vrcholy spojeny hranou, říká se, že spolu **sousedí**. Všechny vrcholy, se kterými daný vrchol v sousedí, jsou jeho sousedství nebo okolí $N(v)=\{u:\{v,u\}\in E\}$
* V případě orientovaných grafů se rozlišuje vstupní stupeň $deg+(v)$, počet hran, které vcházejí do vrcholu v, a výstupní stupeň $deg−(v)$, počet hran, které vychází z vrcholu v.
* $deg^{+}(v)=|\{u:(u,v)\in E\}|$
* $deg^{-}(v)=|\{u:(v,u)\in E\}|$
* **Hrana**
* dvouprvková podmnožina množiny vrcholů.
* Když $V \in E$, tak $V$ je incidentní s $E$.
* incidence je zobrazení, přiradí hraně neuspořádanou *(neorientovaný g.)* nebo uspořádanou *(orientovaný g.)* dvojici vrcholú
* **řídký graf**
* $|E|$ je mnohem menší než $|V|^2$ (→ preferuje proto seznamy následníků)
* **hustý graf**
* $|E|$ je blízko $|V|^2$ (→ preferuje proto matici sousednosti)
* **smyčka**
* hrana $(a, a)$

:::
**Sled** v grafu je posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana.
:::info

Špeciálne typy grafov $P$ - cesta, $T$ - strom, $F$ - les, $K$ - kompletný, $C$ - cyklus

**$P$ - cesta**
Cesta je sled, ve kterém se **neopakují vrcholy**, tedy každý vrchol se v cestě objevuje **nejvýše jednou**. Existuje-li mezi dvěma vrcholy sled v grafu, existuje mezi nimi i cesta (protože každý úsek mezi dvěma výskyty stejného vrcholu se dá „vystřihnout“).
* cesta z $V_0$ do $V (p(V_0,V))$ je postupnosť $V_1, ... V_n$ takých, že $V_n = V$ a $\forall _{i \in [1,n]} (V_{i-1},V_i) \in E$ (špeciálne, ak sú všetky $V_i$ rôzne, hovoríme o jednoduchej ceste)
---
**$C$ - cyklus** (tiež **kružnica**)
Cyklus, neboli kružnice, je takový graf (podgraf), který se skládá z jediného cyklu – tedy uzavřené posloupnosti propojených vrcholů.
* cesta $p(V_0,V)$ je cyklus ak $V_0 = V$ (zvyšok vlastností rovnaký ako cesta)
---
**$T$ - strom**
Strom je graf, který je souvislý a neobsahuje žádnou kružnici.
Pre neorientovaný strom exxistujú aj dalšie (ekvivalentné) definície:
> Každé dva vrcholy z G jsou spojeny právě jednou cestou (jednoznačnost cesty).
> G je souvislý a po odebrání libovolné hrany se stane nesouvislým (minimální souvislost).
> G neobsahuje kružnici, ale po přidání libovolné hrany vznikne v G kružnice (maximální graf bez kružnic) .
> G je souvislý a $\left|V\right|=\left|E\right|+1$, kde $V$ je množina vrcholů a $E$ množina hran grafu G.
* ak $\forall V_1, V_2 \in E$,
$V_1 \neq V_2 \Rightarrow \exists! p(V_1,V_2)$ - Všetky vrcholy sú spojené práve jednou cestou

Vlastnosti:
* každý strom je bipartitní
* každý strom se spočetně mnoha vrcholy je rovinný
* kostra libovolného grafu je tvořena stromem
---
**K - kompletný** (úplný)
Úplný graf alebo kompletný graf je graf v ktorom je každý vrchol grafu spojený s každým iným vrcholom grafu. Úplný graf s n vrcholmi sa zvykne označovať ${\displaystyle K_{n}\ }$.
* ak $\forall V_1, V_2 \in E$,
$V_1 \neq V_2 \Rightarrow (V_1,V_2) \in E$
**$K_{x,y}$** - bipartitný x na y

graf + cena: cenová funkcia: $w: E(G) \Rightarrow \mathbb R ^+$ (občas len $E \Rightarrow \mathbb R ^+$ )
> Grafy ${\displaystyle K_{1}\ }$ až ${\displaystyle K_{4}\ }$ sú rovinné grafy. Ostatné úplné grafy nie sú rovinné.
:::
---
## Reprezentace grafů

:::success
**Seznamem následníků**

máme pole o $|V|$ prvcích – pro každý vrchol $u ∈ V$ jeden seznam prvků $V(u, v) ∈ E$
paměťová náročnost: $Θ(V + E)$

**Maticí sousednosti**

matice velikosti $|V| × |V|$
prvek matice $a_{ij} = 1$, pokud $(i, j) ∈ E$, jinak $a_{ij} = 0$

**Matice incidence**

$|V| × |V|$ matica
* $a_{ij} = 1$ ak $(i, j) ∈ E$
* $a_{ij} = -1$ ak $(j, i) ∈ E$
* $a_{ij} = 0$ inak

*znie ako blbost, ale lahsie urcime stupne vrcholov napr $\mathcal O (n^2)$*

**Len zoznam hrán**
:::
---
## Souvislost grafu

:::success
Pre neorientovaný graf:
* souvislý graf
* $\forall x,y \in E \exists p(x,y)$
platí, že pro každé dva vrcholy x, y existuje sled z x do y.

Pre orientovaný graf:
* slabá souvislost
* graf je slabě souvislý, pokud jeho symetrizace (= odstranění orientovanosti) je souvislý graf.
* silná souvislost
* graf je silně souvislý, pokud pro každé dva vrcholy x, y existuje cesta z x do y i z y do x.
:::

:::success
**Silně souvislá komponenta** je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů $U,V$ existuje sled.
:::
>* [color=#1167b1] Dvojitý DFS – první mi určí pořadí (na $G^R$) pro volání druhého (na $G$) (sestupné finishing časy), který mi vytiskne jednotlivé komponenty.

**DFS a silne súvislé komponenty**
* Algoritmus nalezení silně souvislé komponenty obsahující $u$:
* najdi množinu $S$ všech vrcholů dosačitelnych z $u$ pomocí DFS
* najdi množinu $T$ všech vrcholů, ze kterych je dosažitelny $u$
* aplikujeme DFS na transponovany graf $G$
* Silně souvislá komponenta obsahující $u$ je průnikem $S$ a $T$
* Složitost je $O(V + E)$
* Algoritmus nalezení všech komponent:
1. run DFS, urči časové značky (nalezení, uzavření)
2. zmeň orientáciu vš. hrán
3. spusti DFS, ale uzly vyberaj v klesajúcom poradí značiek uzavrení dostaneme stromy lesa určujúce silné komponenty grafu

> [color=#449750] **Formálne**
> $uv$ je stromová/dopredná: $(in [v], out[v]) \subseteq (in[u], out[u])$
> zpetná: $(in [u], out[u]) \subseteq (in[v], out[v])$
> priečna: $in [v] < out[v] < in[u] < out[u]$
>
:::success
**Řezy**

* vrcholový řez (= separátor) – taková množina $U ⊆ V$, že graf $G = (V \setminus U, E)$ není souvislý
* hranový řez
* vrcholová (hranová) souvislost – velikost minimálního vrcholového (hranového) řezu
* graf je vrcholově/hranově k-souvislý, pokud jeho vrcholová/hranová je $≥ k$
:::

## Barevnost
Barvení grafu se zabývá přiřazováním barev nejčastěji vrcholům (příp. hranám či stěnám).

:::success
Nechť $G = (V, E)$ je graf, k přirozené číslo. Zobrazení $b: V → {1, …, k}$ nazveme obarvením grafu $G$ pomocí k barev, pokud pro každou hranu ${x, y} ∈ E$ platí $b(x) ≠ b(y)$. Barevnost grafu (také chromatické číslo) $G$ je minimální počet barev potřebný pro obarvení $G$. Značí se $\chi(G)$ (= velké chí).
:::

:::success
Majme $G, k \in N$. Potom obarvenie je zobrazenie $b: V → {1 ... k}$ také, že $\forall (x,y) \in E$ $b(x) ≠ b(y)$. Potom barevnosť grafu (**chromatické číslo**) je min. k → značíme $\chi(G)$ (= velké chí).
:::

> [color=#449750] **Vlastnosti**
>
> $\chi(G) = 1$ → diskrétny graf $\chi(G) = |V|$ pre úplný graf
> $\chi(G) = 3$ → ak má kružnica liché dĺžky => neni bipartitný
> $\chi(G)\leq$ 4 → pre ľubovoľny rovinný graf (problém 4 barev)
---
## Rovinné grafy
**= planární**, teda vieme ho nakresliť bez kríženia hrán.

:::success
* pro rovinný graf existuje takové rovinné nakreslení, kdy se žádné dvě hrany nekříží
* duální graf – (multi)graf, jehož vrcholy tvoří stěny jiného rovinného grafu
* stěna – souvislý kus roviny určený rovinným nakreslením grafu
:::

Pre rovinné grafy platí veta (Eulerova formule): V rovinném grafu $G=(V, E)$ platí:

:::success
1. $|V| − |E| + s = 2$ ($s$ = počet stěn)
2. $|E| ≤ 3|V|−6$
:::

Tieto $G$ ide vždy obarviť 4 barvami (veta o 4 barvách):
:::success
Vrcholy rovinného grafu lze obarvit 4 barvami tak, aby žádná hrana nespojovala dva vrcholy stejné barvy.
:::

---
## Prohledávání grafu
*m = |V| a n = |E|*
|**algoritmus**|**zložitosť**|
| - |:- |
| BFS | $\mathcal{O}(m + n)$ |
| DFS | $\mathcal{O}(m + n)$ |

### BFS = prohledávání do šírky
:::info
**Algoritmus**
* $Q$ – fronta z vrcholů
* $d[u]$ – vzdálenost $u$ od $s$
* $π[u]$ – předchůdce $u$
* $color[u] ∈ {white, gray, black}$ – pomocné
----
* inicializace pro všechny mimo počáteční vrchol $s$: obarvení na bílo, nekonečná vzdálenost, předchůdce $nil$
* inicilalizace $s$: šedý, vzdálenost 0, předchůdce $nil$, zařadí se do $Q$
* dokud se $Q$ nevyprázdní, vezmu z $Q$ $u$, projdu všechny jeho bílé sousedy, ošedím je, nastavím vzdálenost $(d[u] + 1)$ a předchůdce $(u)$, zařadím do $Q$ a $u$ přebarvím na černo

:::

**Složitost**
* incializace: $\mathcal{O}(n)$
* žádný vrchol se pak již nepřebarví na bílo, takže jde do $i$ z $Q$ nejvýše jednou → operace s frontou tedy stojí $\mathcal{O}(n)$
* seznam sousedů vrcholu se prochází, jen když je vrchol odstraňován z fronty, takže dohromady $\mathcal{O}(m)$
* $= \mathcal{O}(m+n)$

**Korektnost**

* BFS objeví každý dosažitelný vrchol z $s$, nedosažitelné nebudou objeveny.
* Po zastavení $d[v] = δ(s, v) ∀v ∈ V$.
* Pro každé $v ∈ V$ dosažitelné z $s$ je lib. nejkratší $s-π[v]$ cesta následovaná hranou $(π[v], v)$ jednou z nejkratších $s-v$ cest.

:::success
Právě vrcholy zařazené do $Q$ mají $d[v] < ∞$. Pokud $v$ je nedosažitelné z $s$, tak $d[v] >= δ(s, v) = ∞$, proto v nebude objeven.

$V_k = {v ∈ V | δ(s, v) = k}, k ∈ N_0$, → indukcí vzhledem ke $k$.
:::

Dôkaz indukciou: Pokud $v$ jde do $Q$, $d[v]$, $π[v]$ se již nikdy nemění. Jsou-li vrcholy zařazovány do $Q$ v pořadí $v_1, …, v_r$, pak $d[v_1] ≤ … ≤ d[v_r]$. Nechť $v ∈ V_k, (k ≥ 1)$, tj. je objeven až po objevení všech z $V_k-1$. Poněvadž $δ(s, v) = k$, ex. cesta $s, …, u (∈ V_k-1), v$ délky $k$. Nechť $u$ je první takový objevený. V jistém okamžiku se u objeví na čele $Q$, v je objeven při prohlídce sousedů $u$. Tedy pro $v ∈ V_k$ je $π[v] ∈ V_k-1$, a proto $d[v] = d[π[v]] + 1$. Nejkratší cestu do v tak získáme tím, že půjdeme po nejkratší cestě do $π[v]$, a pak po hraně $(π[v], v)$.

### DFS = prohledávání do hloubky
* procházení grafu metodou backtrackingu
* vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil
* vrcholy k procházení ukládá do zásobníku (LIFO)
* pokud nenajde v aktuálním vrcholu nenavštívené následníky, vrací se zpět backtrackingem (vyjme další prvek ze zásobníku)

:::info

**Algoritmus**
* incializace vynuluje čas + všechny obarví na bílo a nastaví předchůdce na nil
* hlavní část algoritmu iteruje přes všechny vrcholy grafu a nad bílými spouští podproceduru Visit
* ta: inkrementuje čas, nastaví discovery time, ošedí vrchol; projde všechny sousedy a bílým nastaví předchůdce a spustí nad nimi opět Visit; nakonec uzel očerní, inkrementuje čas a nastaví finishing time
:::

**Složitost**

* inicializace $\mathcal O(n)$, vynulování času $\mathcal O(1)$, iterace nad vrcholy $\mathcal O(n)$
* Visit: nastavení parametrů – pro každý vrchol $\mathcal O(1)$; procházení sousedů $\mathcal O(m)$; nastavení parametrů – pro každý vrchol $\mathcal O(1)$
* $= \mathcal O(m+n)$

**Korektnost**

* věta o závorkách (discovery a finishing časy dvou uzlů jsou buď zcela disjunktní nebo tak či onak zanořené, pokud v DF-tree jde o následníka)
* věta o bílé cestě (pokud v je v DF-forest následníkem u, tak v čase d[u] vede od u k v cesta po čistě bílých vrcholech)
* DF-forest = predecessor subgraph, kde hrany = ${ (π[v], v) | v ∈ V ∧ π[v] ≠ nil } →$ forest, protože DFS může být opakováno z více vrcholů

## Najkratšie cesty
|**algoritmus**|**zložitosť**| **typ**|
| - |:- |:- |
| BFS | $\mathcal{O}(m+n)$ | vzdialenosť = počet hrán |
| **Dijkstra** | $\mathcal{O}(m + n * \log n)$ | "BFS" - nezáporné dĺžky hrán |
| **Bellman-Ford** | $\mathcal{O}(m * n)$ | relaxácia |
| Násobení matic | $\mathcal{O}(n^3 * \log n)$ | |
| **Floyd-Warshall** | $\mathcal{O}(n^3)$ | matice |
| Jhonson | $\mathcal{O}(n^2 * \log n + m * n)$ | |

----
*(Algoritmy zo zadania detailnejšie popísané nižšie)*

**Dijkstra**
* nájde najkratšie cesty z jedného vrcholu do ostatných
* udržuje množinu vrcholů, do kterých už byla vzdálenost spočítána;
* vyžaduje minimovou prioritní frontu – z dosud nezpracovaných vrcholů
* zpracovává postupně vrcholy mající nejnižší cenu (vzdálenost od s) a každou hranu z daného vrcholu relaxuje
* nefunguje pro záporně ohodnocené hrany

**Bellman-Ford**
* $(|V| - 1)$-krát iteruje přes všechny hrany a každou relaxuje
* iteruje přes všechny hrany a kontroluje, jestli graf neobsahuje dosažitelný negativní cyklus (ano → vrátí false)

**Floyd-Warshall**
* nájde všetky najkratšie cesty medzi všetkými vrcholmi
* matica susednosti
* využívá dynamického programování; (bez záporných cyklů – detekce na diagonále); princip: nejkratší cesta z $a$ do $b$ obsahuje nejkratší cesty mezi vrcholy, z nichž se skládá
* 3 zanořené cykly ${1..n}$ a vevnitř relaxace nad množinami: $d_{ij}^k ← min(d_{ij}^{k-1}, d_{ik}^{k-1} + d_{kj}^{k-1})$
* $k = 0$ jsou samotné váhy hran
* společně s délkou nejkratších cest se stejným způsobem počítá i matice předchůdců
* složitost: $\mathcal O(n^3)$

## Kostry

:::info
* $w(G)$ = váha podgrafu, tj. součet vah jednotlivých hran
:::
:::success
* Spanning Tree (kostra) grafu $G=(V,E)$ je podgraf $T \subseteq G$ t.ž. $V(T) = V(G)$ a $T$ je strom.
* Minimum Spanning Tree (MST; minimální kostra) grafu $G$ je kostra $M$ t.ž. $w(M) \leq w(T)$ pro všechny kostry $T$ grafu $G$. tj. kostra s minimální vahou
:::

|**algoritmus**|**zložitosť**|
| - |:- |
| Borůvka| $\mathcal{O}(m * \log n)$|
|Kruskal| $\mathcal{O}(m * \log n)$|
|Jarník *strom+prior. fronta* |$\mathcal{O}(m * \log n)$|
|Jarník *fibonacci*|$\mathcal{O}(m + n\log n)$|

Pravidlá použité pri algoritmoch:
**Blue rule:** Pro daný řez bez modrých hran vybereme minimální neobarvenou hranu a obarvíme ji modře.

**Red rule:** Pro daný cyklus neobsahující žádnou červenou hranu vybereme maximální neobarvenou hranu a obarvíme ji na červeno.

### **Boruvka**
"paralelný" Kruskal - union find
* Budujeme modré stromy ze všech vrcholů na ráz.
* Na začátku vytvoříme ze všech vrcholů modré stromy.
* V každé fázi vybereme pro každý strom nejlevnější odchozí hranu a přidáme ji ke stromu. (Spojíme propojené stromy.)
* Končíme, pokud nám zbyl pouze jeden strom.

**Složitost**

* Počet komponent v prvním tahu: $n$
* každá přidaná hrana spojí nejméně dvě komponenty
⇒ nejvýš $\log n$ fází
* každá fáze zabere $\mathcal{O}(m)$ (musíme projít přes všechny hrany)
* $= \mathcal{O}(m * \log n)$

### **Kruskal**
* Budujeme modrý les.
* umístí každý vrchol do samostatné množiny a utřídí hrany podle váhy do neklesající posloupnosti
* prochází jednu hranu po druhé, pokud její vrcholy patří do různých množin, přidá hranu do kostry a množiny sloučí

> **Alternativní postup:**
> * Opakuj následující kroky, dokud je to možné:
> * Z hran grafu $G$, které dosud nebyly vybrány, vyber nejkratší hranu, která nevytváří žádnou kružnici s hranami již vybranými.

> zosortuj všetky hrany, choď do najlacnejšej a vždy urči, či patrí do kostry (čiže či nepridá do kostry cyklus)

**Složitost**

* použijeme strukturu Union-Find
inicializace $\mathcal O(n)$ a utřídění hran $\mathcal O(m * \log m)$
* pro každou hranu provádíme dvě Find operace, které stojí $\mathcal O(\log n)$, a eventuálně Union, který je rovněž v $\mathcal O(log n)$
* $= \mathcal O(m * \log n)$ [protože $m < n^2$, tedy $\log m = \mathcal O(\log n)$]

### Jarnik
* Budujeme modrý strom.
* Začneme budovat strom z jednoho vrcholu a přidáme vždy nejlehčí odchozí hranu.

> začni niekde a vytváraj strom kostry. Pre tento strom si drž prioritnú kostru (decrease)

> **Algoritmus**
> * při inicializaci nastaví klíče vrcholů na nekonečno a rodiče na $nil$; $r.key = 0$ pro počáteční vrchol; naplní $Q$
> * vybírá z $Q$ vrcholy s minimálním cenou, prochází jejich sousedy a do těch, do kterých se umí dostat z daného vrcholu levněji, nastaví nového rodiče a cenu

**Složitost**

* použijeme binární haldu
* incializace $\mathcal O(n)$, pro všechny vrcholy odstranění z $Q$ $\mathcal O(n * log n)$, procházení všech hran a snižování ceny $\mathcal O(m * log n)$
* $\mathcal = O(m * log n)$
* s fibonacciho haldou by šlo zlepšit na $\mathcal O(m + n * log n)$ díky amortizované $\mathcal O(1)$ složitosti snižování ceny
---
## Toky v síti
**Flow network** („toková síť“) je čtveřice $(G,s,t,c)$:

* $G=(V,E)$: orientovaný graf
* $s \in V$: zdroj (source)
* $t \in V$: stok (cíl); s \neq t
* $c: E \rightarrow R^+$: funkce určující kapacity hran

**Network flow** (tok v síti) je funkce $f:E \rightarrow R^+$ splňující:

* kapacitní podmínku (tok přes hranu je nezáporný a maximálně roven kapacitě hrany)
* podmínku kontinuity (všechny vrchol krom $s$ a $t$ mají součet vstupních kapacit roven součtu výstupních)
* Hodnota toku $f$ je $|f| = \sum_{(s,v) \in E}{f(s,v)} = \sum_{(w,t) \in E}{f(w,t)}$

Problémem je hledání maximálního toku – toku s maximální hodnotou.

|**algoritmus**|**zložitosť**|
| - |:- |
| Ford Fulkerson| $\mathcal{O}(mC)$|
|Edmonds-Karp| $\mathcal{O}(m^2n)$|
|Dinics |$\mathcal{O}(mn^2)$|
|MPM|$\mathcal{O}(n^3)$|
|push-relabel|$\mathcal{O}(mn^2)$|

:::success
**Reziduální síť** (Reziduální graf)
* Podgraf pôvodného grafu
* graf $G_f = (V,E_f)$, kde pro každou hranu $e = (u,v) \in E$ obsahuje $E_f$:
* $e = (u,v)$ pokud $f(e) < c(e)$ (e.g. ak aktuálny tok je menší ako kapacita hrany)
* $e^R = (v,u)$ pokud $f(e) > 0$ (ak aktuálny tok je vačší ako 0, eg. hrana patri reziduálnej sieti)

**Reziduální kapacita**
Reziduálna kapacita hrany $e$ je číslo $c(e) - f(e)$, čiže rozdiel kapacity hrany a aktuálneho toku. Reziduálne kapacity všetkých hrán, tvoria reziduálnu sieť.

$c_f(e)=\begin{cases} c(e)-f(e) \mbox{ pokud } e \in E_f \\
f(e) \mbox{ pokud } e^R \in E_f \end{cases}$

**Augmentující cesta**
Cesta z $s$ do $t$ v reziduálním grafu.

**Augmentace toku**
Upravíme tok na základě bottleneck kapacity augmentující cesty.

* pro $e$ hodnotu přičteme
* pro $e^R$ hodnotu odečteme

:::

**Ford Fulkerson**
Kým existuje cesta v reziduálnom grafe - updatuj

**Edmonds-Karp**
nájdi najkratšiu cestu v reziduálnom grafe a updatuj

**Dinics**
nájdi všetky cesty v level grafe (DFS p = BFS)

**MPM**
v level grafe vyber vrchol s minimalnou kapacitou a saturuj ho (eg. napushuj z $s$ a napulluj z $t$)

---
## Algoritmy

### Bellman Ford
* Hledání cyklu v grafu
* $(|V| - 1)$ -krát iteruje přes všechny hrany a každou relaxuje
* iteruje přes všechny hrany a kontroluje, jestli graf neobsahuje dosažitelný negativní cyklus (ano → vrátí false)
* **Složitost**
* inicializace $\mathcal O(n)$, relaxace hran $\mathcal O(m * n)$, kontrola na negativní cyklus $\mathcal O(m)$, ukončení $\mathcal O(1)$
* $= O(m * n)$
* **Korektnost**
* ukáže se, že po skončení $d[v] = δ(s, v)$ pro všechny $v$ z $V$ [dokazuje se indukcí po nejkratší $s-v$ cestě (vrcholy se na ní neopakují (→ nejvýše $|V|-1$ hran)) – $d[v_i]$ se po $i$-té iteraci relaxaci už nemění (zrelaxuje se tedy celá cesta)]
* ($G_π$ je strom nejkratších cest) #todo jak sa robi
* BF vrátí true, protože platí trojúhelníková nerovnost; (jinak) pokud obsahuje dosažitelný negativní cyklus, vrátí false

### Dijkstra
* Hledání cyklu v grafu
* udržuje množinu vrcholů, do kterých už byla vzdálenost spočítána; vyžaduje minimovou prioritní frontu – z dosud nezpracovaných vrcholů
* zpracovává postupně vrcholy mající nejnižší cenu (vzdálenost od $s$) a každou hranu z daného vrcholu relaxuje
* nefunguje pro záporně ohodnocené hrany
* **Složitost**
* inicializace $\mathcal O(n)$, naplnění $Q \mathcal O(n)$, zpracování všech vrcholů $\mathcal O(n)$, relaxace všech hran $\mathcal O(m)$ + aktualizace hodnot v $Q \mathcal O(log n)$ pro každou hranu
* uvažujeme binární haldu, kde vložení je v průměru v $\mathcal O(1)$, odstranění minima $\mathcal O(log n)$ a aktualizace $\mathcal O(log n)$
* $= \mathcal O(m * log n)$
s využitím fibonacciho haldy: $\mathcal O(m + n * \log n)$
* **Korektnost**
* Ukážeme, že $d[v] = δ(s, v)$ v okamžiku přidání v do $S$; (a že) rovnost je pak zachována. [dokazuje se na $u$ jako prvním vrcholu, pro který to neplatí, na cestě je pak nějaké $y$ z $V\S$ (stejně jako $u$), kde přes $d[y] = δ(s, y) ≤ δ(s, u) ≤ d[u]$, ale pak dostaneme rovnost, protože y není v $S$ v okamžiku, kdy se tam dostává $u$ (tj. spor s volbou $u$)]

### Ford-Fulkerson
* Hledání maximálního toku
* Hledáme augmentujeme tok pomocí augmentujících cest dokud ještě síť nějakou augmentující cestu má.
* **Algoritmus**
* reziduální kapacita – kolik dalšího toku se dá ještě hranou vést
* nemusí skončit, pokud jsou Reálné kapacity; síť s racionálními kapacitami lze převést na síť s celočíselnými
* > [color=#1167b1] inicializuje toky na hranách na 0; dokud existuje zlepšující cesta, tak na ní zvýší tok o minimální společnou reziduální kapacitu (tj. o maximum)
* **Složitost**
* inicializace $\mathcal O(m)$, každá iterace cyklu $\mathcal O(m)$
* zjemňování stupnice $\mathcal O(m^2 * \log_2 C); C=SUMA$ (přes $v$ z $V$) $c(s, v)$
* **Korektnost**
* ukáže se, že kapacitní ohraničení a podmínka kontinuity zůstanou splněny
* na konci maximální tok – v reziduální síti už neexistuje cesta z $s$ do $t$

### Push-Relabel
* Hledání maximálního toku
* pracuje s pseudotokem (nesplňuje podm. kontinuity = aktivní vrchol) a výškami vrcholů – tok se přesouvá od vyšších k nižším
* pokud je možné protlačit nějaký tok od aktivního vrcholu k nižším, tak Push, jinak Relabel tohoto vrcholu
* inicializace: výšky, aktivity, toky
* **Složitost**
* nanejvýš $2n^2$ počet relabel, $2nm$ saturujících push (přetlačování v reziduální síti), $4mn^2$ nesaturujících push; push i relabel lze realizovat v konstatní složitosti
* $= \mathcal O(n^2 * m)$
* **Korektnost**
* V průběhu celého výpočtu platí:
* výška vrcholu nikdy neklesá;
* $f$ je pseudotok a pokud kapacity jsou celočíselné, tak i $f$ je;
* pseudotok a výška jsou kompatibilní (tj. $h(t) = 0, h(s) = n$, pro hrany $(v, w)$ platí $h(v) ⇐ h(w) + 1)$.
* Pokud alg. vrátí pseudotok, tak je to maximální tok.
* Push respektuje kapacitní ohraničení hrany a do reziduálního grafu přidá hranu, která nemusí splňovat výškový rozdíl
* Relabel zvyšuje výšku vrcholu v právě když v reziduální síti nevede z v do žádného vrcholu s menší výškou

## Maximální párování v bipartitných grafoch
Párovaniie v bipartitnom grafe je množina hrán vybraných tak, že žiadne dve hrany nezdieľajú koncový bod. Maximálne párovanie je párovanie maximálnej veľkosti (maximálny počet hrán). Pri maximálnom párovaní, ak sa k nej pridá nejaká hrana, už to nie je párovanie. Pre daný bipartitný graf môže existovať viac ako jedno maximálne párovanie.

**Maximálne bipartitné párovanie a problém s maximálneho toku**
Problém maximálneho bipartitného párovania (MBP) možno vyriešiť jeho prevedením na tokovú sieť.

Postup:

1) Vytvorte sieť toku
V prietokovej sieti musí byť $s$ a $t$. Takže pridávame zdroj a pridávame cesty zo zdroja ku všetkým vrchoľom jednej množiny grafu. Kapacita každej cesty je označená ako 1 jednotka.
2) Nájdite maximálny tok v sieti.
Použijeme Ford-Fulkersonov algoritmus na nájdenie maximálneho toku v sieti vytvorenej v kroku 1. Maximálny tok je v skutočnosti MBP, ktorý hľadáme.