7. Grafy a grafové algoritmy (95%)

tags: `algo`, `IB000`, `IB002`, `IV003`

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

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.

Š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ů

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

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.

Silně souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů \(U,V\) existuje sled.

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

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]\)

Ř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).

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í).

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í).

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.

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í:

\(|V| − |E| + s = 2\) (\(s\) = počet stěn)
\(|E| ≤ 3|V|−6\)

Tieto \(G\) ide vždy obarviť 4 barvami (veta o 4 barvách):

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

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.

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)

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

\(w(G)\) = váha podgrafu, tj. součet vah jednotlivých hran

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)\)

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
- 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:

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.
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.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

7. Grafy a grafové algoritmy (95%)

tags: algo, IB000, IB002, IV003

Formalizace základných grafových pojmov

Reprezentace grafů

Souvislost grafu

Barevnost

Rovinné grafy

Prohledávání grafu

BFS = prohledávání do šírky

DFS = prohledávání do hloubky

Najkratšie cesty

Kostry

Boruvka

Kruskal

Jarnik

Toky v síti

Algoritmy

Bellman Ford

Dijkstra

Ford-Fulkerson

Push-Relabel

Maximální párování v bipartitných grafoch

tags: `algo`, `IB000`, `IB002`, `IV003`