- graf
- orientovaný / neorientovaný
- ohodnocené hrany / vrcholy
- jednoduché / násobné hrany
- reprezentace grafu
- seznam následníků
- matice sousednosti
- Složitost grafových algoritmů je funkcí počtu vrcholů a hran
- používáme zjednodušenou nota, např. $\mathcal{O}(V + E)$ resp. $\mathcal{O}(n + m)$
- $V$ ($E$) je množina vrcholů (hran) grafu, $n = |V|, m = |E|$
- graf $G = (V,E)$ je reprezentovaný maticí $A = (a_{ij})$ rozměrů $|V| \times |V|$ kde
$$a_{ij} = $$
- prostorová složitost“ $\Theta(V^2)$
- vhodné pro husté grafy
- časová složitost výpisu všech sousedů je $u$ je $\Theta(V)$
- seznam vrcholů
- každý vrchol obsahuje linked list sousedů
- průzkum grafů do hloubky
- barva:
v.color
- bílá: nebyl objeven
- šedá: byl objeven, průzkum pobíhá
- černá: průzkum ukončen
- předchůdce
v.pi
- vrchol, ze kterého byl vrchol
v objeven
- časové značky
v.d discovery - časové značky objevenív.f finish time - časová značka ukončení průzkumu
- preorder - podle
v.d (časových značek objevení)
- postorder - podle
v.f (časových značek ukončení)
- reversed post order
- vrchol $v$ je dosažitelný z vrcholu $u$ v DFS stromu grafu $G$ právě když $u.d < v.d < v.f < u.f$
- v DFS stromu grafu $G$ je vrchol $v$ je dosažitelné z $u$ právě když v čase $u.d$ existuje cesta z $u$ do $v$ obsahující jenom bílé vrcholy
- stromová hrana (tree edge)
- zpětná hrana (back edge)
- dopředná hrana (forward edge)
- příčné hrany (cross edge)
- v neorientovaném pouze:
- Orientovaný graf $G$ je acyklický právě když DFS průzkum grafu neoznačí žádnou hranu jako zpětnou.
- Topologické uspořádání vrcholů orientovaného grafu očíslovaní vrcholů $1$ až $n$ ($n$ je počet vrcholů grafu), že každá hrana grafu vede z vrcholu s nižším číslem do vrcholu s vyšším číslem.
- Orientovaný graf má topologické uspořádání právě když je acyklický.
- DFS průzkum
- Bereme vrcholy, v jakém pořadí skončily
- cesta (vs sled; path vs walk) - posloupnost vrcholů, takových, že mezi 2 je hrana
- jednoduchá cesta (vs cesta; simple path vs path) - cesta, která neobsahuje dva stejné vrcholy
- délka cesty - $w(p)$, součet délek hran pro hodnocené grafy (pro nehodnocené, počet hran)
- délka cesty jen s jedním bodem je
= 0
- Cesta $p = \langle v_0, v_1, …, v_k \rangle$ z vrcholu $v_0$ do vrcholu $v_k$ právě když pro každou cestu $\overline{p}$ z vrcholu $v_0$ do vrcholu $v_k$ platí $w(\overline{p}) \ge w(p)$
- funkce $\delta$, kde $\delta(u,v)$ je délka nejkratší cesty z $u$ do $v$ v $G$.
- $\delta(u,v) = \infty$ - cesta z $u$ do $v$ neexistuje
- $\delta(u,v) = -\infty$ - cesta z $u$ do $v$ obsahuje cyklus záporné délky (neexistuje nejkratší cesta)
- z daného vrcholu do všech vrcholů- single source shortest path, SSSP
- ve všech vrcholů do daného vrcholu - pro neorientované stejné jako SSSP, pro orientované otočíme hrany
- mezi danou dvojicí vrcholů - speciální případ SSSP (není znám asymptoticky rychlejší než pro SSSP)
- mezi všemi dvojicemi vrcholů - řešení opakovanou aplikací pro SSSP
- obecný graf - Algoritmus Bellmana a Forda
- nehodnocený graf - průzkum do šířky, BFS
- acyklický graf - relaxace hran respektující topologické uspořádání
- graf s nezáporným ohodnocením hran- Dijkstrův algoritmus
- nehodnocený graf - BFS - průzkum do šířky
- graf s nezáporným ohodnocením hran - každou neorientovanou hranu nahradíme dvojicí orientovaných hran a převedeme na úlohu v orientovaném grafu
- obecný graf
- hrany záporné délky, ale žádné cykly záporné délky → hledání nejlevnějšího párování
- když obsahuje cyklus záporné délky, algoritmicky pouze exponenciální složitost
- Jestliže mezi dvojicí vrcholů grafu existuje nejkratší cesta, tak mezi nimi existuje taková nejkratší cesta, která je jednoduchá. (→ můžeme se omezit pouze na jednoduché cesty)
- Každá podcesta nejkratší cesty je nejkratší cestou.
- $v.\pi$ - rodič ve stromě nejkratší cestě
- atribut předchůdce, $v.\pi$, parent
- iniciální nastavení $v.\pi = None$
- pokud $v.\pi \ne None$ pak je to předchůdce na nejkratší cestě
- atribut vzdálenost, $v.d$, distance
- iniciální nastavení $s.d = 0$ a $v.d = \infty$ pro $v \in V \setminus {s}$
- hodnota $v.d$ je horní odhad $\delta(u,v)$
- relaxace hrany $(u,v)$ je test, zda je možné zkonstruovat kratší cestu z $s$ do $v$ tak, že projedeme přes vrchol $u$
- Jestliže je hrana napjatá $u.d + w(u,v) < v.d$ (z $u$ vede do $v$ kratší cesta) tak $v.d = u.d + w(u,v)$ a $v.\pi = u$.
- algoritmus pro hledání nejkratších cest z daného vrcholu $s$ do všech vrcholů grafu
- může obsahovat záporné délky
- pokud obsahuje záporný cyklus dosažitelný z vrcholu $s$ vrátí $False$
- jinak $True$ a vypočítá nejkratší cesty
- algoritmus je založený na relaxaci hran
- vždy když vrcholu $u$ zlepšíme hodnoty $u.d$, tak relaxujeme všechny hrany vycházející z vrcholu $u$
- pro přehlednost rozdělujeme do iterací; v jedné iteraci se relaxují všechny hrany grafu
function Bellman_ford((V,E),w,s)
InitSssp((V,E),s)
for i = 1 to |V| - 1 do
foreach (u,v) \in E do
if v.d > u.d + w(u,v) then Relax(u,v,w)
foreach (u,v) \in E do
if v.d > u.d + w(u,v) then return False
return True
- optimalizace
- jestliže v iteraci prvního
foreach cyklu nebyla nalezena žádná napjatá hrana, výpočet můžeme ukončit s návratovou hodnotou True
- hranu $(u,v)$ relaxujeme v iteraci $i + 1$ pouze pokud v iteraci $i$ byla změněna hodnota $u.d$
- celková složitost složitost je $\mathcal{O}(VE)$
- optimální řešení relaxace hran v Bellmanově-Fordově algoritmu je takové, že vždy relaxujeme hranu $(u,v)$ pro kterou $u.d = \delta(s,u)$
- pro obecné grafy tak náročná jako vypočítání nejkratší cesty
- pro acyklické grafy je pořadí jednoduché: topologické uspořádání vrcholů grafu
- časová složitost $\mathcal{O}(V+E)$
- topologické uspořádání garantuje, že hrany každé cesty jsou relaxované v pořadí, v jakém jsou v cestě
- vstupní podmínka: graf s nezáporným ohodnocením hran
- algoritmus řeší SSSP
- pro reprezentaci množiny vrcholů určených k prozkoumání využívá prioritní frontu, kde priorita vrcholu $v$ je určena hodnotou $v.d$
- → efektivnější jak metoda Bellmana a Forda
- Cíl: relaxovat hrany z vrcholu $v$ až v okamžiku, kde $v.d = \delta(s,v)$
- hledáme nejkratší cestu mezi $s$ a $t$
- výpočet ukončíme okamžitě po odebrání vrcholu $t$
- dvousměrné hledání
- heuristika A*
- současně dopředný výpočet z vrcholu $s$
- a zároveň zpětný výpočet na transponovaném grafu
rev(G) z $t$
- vždy jednu iteraci každého výpočtu
- každý má vlastní frontu
- dopředný má $Q_f$ a přiřazuje $.d_f$ a $.\pi_f$
- zpětný má $Q_b$ a přiřazuje $.d_b$ a $.\pi_b$
- výpočet skončí když nějaký vrchol $w$ je odstraněn z obou front $Q_f$ a $Q_b$
- pokud bychom dovedli spolehlivě zjistit, že nejkratší cesta z $s$ do $t$ nepovede přes vrchol $v$, mohli bychom zpracování vrcholu $v$ a hran s ním incidentních → pracovali byhcom z menším grafem
- jestliže dva vrcholy jsou stejně daleko od $s$, chceme při průzkumu preferovat ten, který je blíže cílovému vrcholu $t$
- pro odhad preferencí používáme ohodnocené vrcholů - potenciál $h: V \rightarrow \mathbb{R}$
- Dijkstrův algoritmus s heuristikou se od klasického liší v tom, že při výběru vrcholu z prioritní fronty vybíráme vrchol s nejnižší hodnotou $v.d + h(v)$
- Potenciál závisí od grafu
- Potenciál je přípustný právě když pro každou hranu $(u,v) \in E$ splňuje podmínku $h(u) \le w(u,v) + h(v)$ a pro vrchol $t$ platí $h(t) = 0$
- ohodnocení pomocí potenciálu: $w’(u,v) = w(u,v) - h(u) + h(v)$
- modifikace: jestliže se vrcholu $u$, který již byl odebrán z prioritní fronty, změní hodnota $u.d$, tak vrchol $u$ znovu vložíme do prioritní fronty
- pro graf se zápornou délku
- jestliže z počátečního vrcholu není dosažitelný cyklus se zápornou délkou, najde korektní řešení, nejhorší až exponenciální složitost vůči velikosti grafu
- jestliže z počátečního vrcholu je dosažitelný cyklus záporné délky, tak výpočet modifikovaného Dijkstrova algoritmu je nekonečný
- je dána množina nerovnic ve tvaru $x - y \le b$, kde $x, y$ jsou proměnné a $b$ je konstanta
- úkolem je najít takové hodnoty proměnných, které splňují všechny nerovnice (tzv. přípustné řešení); v případě, že neexistuje žádné přípustné řešení, tak výstupem je
False
- graf lineárních nerovnic:
- pro danou množinu $M$ lineárních nerovnic nad proměnnými $x_1, …, x_n$ definujeme orientovaný graf $G = (V,E)$
- $V = {v_0, v_1, …, v_n}$ (bude mít $n + 1$ vrcholů)
- $E = {(v_i,v_j) | x_j - x_i \le b \in M} \cup {(v_0,v_1), (v_0,v_2), …, (v_0, v_n)}
- hrany grafu ohodnotíme:
- $w(v_0,v_i) = 0$, pro $1 \le i \le n$
- $w(v_i,v_j) = b$ právě když $x_j - x_i \le b \in M$
- Pro daný systém lineárních nerovnic a k němu odpovídající graf lineárních nerovnic $G = (V,E)$ platí:
- když $G$ nemá cyklus záporné délky, tak přístupným řešením systému nerovnic je $x = (\delta(v_0,v_1), \delta(v_0,v_2), …, \delta(v_0,v_n))$
- když $G$ má cyklus záporné délky, tak systém nemá přístupné řešení.