ADS: přednáška: kartičky | algoritmy-datove-struktury1

reprezentace grafu

matice sousednosti – prostor $\Theta(n^2)$
seznamy sousedů – prostor $\Theta(n+m)$ , kde $n$ je počet vrcholů, $m$ je počet hran

Prohledávání do hloubky

DFS(v):

Prohledávání do hloubky

důkaz

pozorování: neviděný → otevřený → zavřený
$v$ $v$ otevřený nebo zavřený $\implies v$ $⟹ v$ dosažitelný
- indukcí podle doby běhu
$v$ $v$ dosažitelný $\implies v$ $⟹ v$ na konci zavřený
- důkaz sporem – minimálním protipříkladem
- kdyby neplatilo, existuje „špatný vrchol“ $x$ , který je dosažitelný, ale nenalezený
- zvolíme $x$ takový, že cesta $u\to x$ má nejméně hran
- určitě $u\neq x$
- na cestě $u\to x$ zvolíme $p$ , což je předposlední vrchol před vrcholem $u$
- $p$ je určitě „dobrý“ (hledali jsme $x$ s nejméně hranami)
- museli jsme vstoupit do $p\implies$ objevit hranu $px$ , což je spor

Prohledávání do hloubky

důkaz

pozorování: do každého vrcholu vstoupíme maximálně jednou
dva přístupy
- $\Theta(\sum_v\Theta(1+\text{deg}^{\text{out}}(v)))=\Theta(n+m)$
- účtujeme vrcholům a hranám

Prohledávání do hloubky

opakované DFS

Prohledávání do hloubky

DFS strom

tvoří ho stromové hrany
zpětné hrany – vede do otevřeného vrcholu (do předka)
dopředné hrany – vede do zavřeného vrcholu, který je potomkem
příčné hrany – vede do zavřeného vrcholu, který není potomkem; vždy zprava doleva

Prohledávání do hloubky

klasifikace hran

pro hranu xy může průchod vrcholy vypadat takto
- $(_x\quad)_x\quad(_y\quad)_y$ – nenastane
- $(_y\quad)_y\quad(_x\quad)_x$ – příčná
- $(_x\quad(_y\quad)_y\quad)_x$ – stromová nebo dopředná
- $(_y\quad(_x\quad)_x\quad)_y$ – zpětná

Prohledávání do hloubky

hrana v neorientovaném grafu

Prohledávání do hloubky

hledání mostů v neorientovaných grafech

df: $e$ je most $\equiv (G-e)$ má více komponent souvislosti než $G$
pozorování: $e$ není most $\iff e$ leží na kružnici
pozorování: zpětná hrana nemůže být most
stromová hrana xy není most $\iff\exists$ zpětná hrana ab, kde a leží ve stromu pod y, b leží ostře nad y
df: low(v) := min { in(b) } (???)
low(v) = min { low(s1), …, low(sk), in(b) | vb zpětné hrany } (???)
DFS algoritmus umí o každé hraně v neorientovaném grafu rozhodnout, jestli je to most