Obsah

Zadání
Vypracování
Předměty
Použitá literatura
Vypracoval

Zadání

1. Grafy: Pojem grafu, vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Stromy a jejich charakterizace, nejkratší cesty v orientovaných stromech. Kostra grafu, problém minimální kostry.

Vypracování

Graf

Graf je uspořádaná dvojice množiny vrcholů a množiny hran. Množina hran je množina neuspořádaných dvojich vrcholů.

$G = (V, E), E \subseteq V \times V$

Graf je z pohledu algebry symetrická nereflexivní binární relace.

Varianty grafů

Pokud jsou dvojice vrcholů reprezentující hrany uspořádané, mluvíme o orientovaném grafu (hrany mají směr).

Pro některé účely je vhodné uvažovat ohodnocené grafy - vrcholy nebo hrany mají nějakou hodnotu (cenu). To má využití například na modelování toků nebo pro navigaci.

Nejobecnějí variantou je multigraf. Multigraf je uspořádaná trojice $G = (V, F, \varepsilon), V \cap F = \emptyset$ . $F$ představuje indexovou množinu, $\varepsilon$ je funkce z $F$ do množiny vrcholů, která mapuje indexy z $F$ na (multi)hrany: $\varepsilon: F \rightarrow {V \choose 2} \cup V \cup (V \times V)$ .
V této definici:

${V \choose 2}$ představuje neorientované hrany
$V$ představuje neorientované smyčky
$V \times V$ představuje orientované hrany a smyčky

Vzdálenost v grafu

Pro graf $G = (V, E)$ je $w = (v_0, e_1, v_1, e_2, v_2, e_3, ..., e_n, v_n), n \geq 1, e_{1...n} \in E, e_i = (v_{i - 1}, v_i)$ procházka grafem $G$ délky $n$ . Cesta $p$ v grafu $G$ je procházka $w$ grafem $G$ taková, že se v ní každý vrchol procházky $w$ vyskytuje právě jednou.

Vzdálenost mezi vrcholy $u, v \in V$ grafu $G$ je definovaná jako délka nejkratší cesty $p$ v grafu $G$ , kde $u$ a $v$ jsou koncové vrcholy cesty. Vzdálenost je označována jako $d_G(u, v)$ , případně $d(u, v)$ . Speciální případ: $d(v, v) = 0$ .

Pokud neexistuje prochádzka (cesta) grafem $G$ mezi vrcholy $u$ a $v$ , značíme $d(u, v) = \infty$ .

Dijkstrův algoritmus

Dijkstrův algoritmus spočítá vzdálenost, resp. nejkratší cesty, mezi jedním vrcholem grafu a ostatními vrcholy, resp. mezi dvěma zvolenými vrcholy.

Algoritmus je reprezentován následovným psedokódem, kde $c$ je cenová funkce hrany $c: E \rightarrow \mathbb{N}$ :

$G = (V, E, c)$ $u \leftarrow$ starting vertex
$x \leftarrow$ ending vertex
$\forall v \in V: d(u, v) = \infty$ $P = \emptyset$ $d(u, u) = 0$

$while\ d(u, x) = \infty$ $\ \ \ \ w \leftarrow any\ vertex \in V \setminus P$ $\ \ \ \ \forall v \in V \setminus P$ $\ \ \ \ \ \ \ \ if\ d(u, v) < d(u, w) \Rightarrow w \leftarrow v$ $\ \ \ \ if\ d(u, w) = \infty)\ return\ false$ $\ \ \ \ P = P \cup w$ $\ \ \ \ \forall e = (w, v) \in E$ $\ \ \ \ \ \ \ \ if\ d(u, w) + c(e) < d(u, v) \Rightarrow d(u, v) \leftarrow d(u, w) + c(e)$

$return\ d(u, x)$

Pozn.: Algortimus do $P$ ukládá spracované uzly, $w$ je nejbližší nespracovaný uzel.

Stromy

Strom je acyklický spojitý jednoduchý graf. Uzly stupně 1 jsou označovány jako listy. Každý strom o $n$ uzlech má právě $n - 1$ hran. Mezi každým párem uzlů vede ve stromě právě jedna cesta.

Přidáním jedné hrany do stromu vznikne právě jeden cyklus. Strom je minimální spojitý graf (je svojí kostrou a minimální kostrou).

Orientovaný strom je strom, jehož hrany jsou orientované. Vrchol, ze kterého existuje v orientovaném stromě cesta do každého vrcholu, se nazývá kořen. Pokud existuje cesta medzi dvěma vrcholy orientovaného stromu, je zároveň nejkratší (vlastnost každého stromu).

Kostra grafu

Graf $G = (V, E)$ má kostru $T = (V, F), F \subseteq E$ , přičemž $T$ je strom. $T$ je minimální kostra grafu $G = (V, E, c), c: E \rightarrow \mathbb{N}$ , pokud $\sum_{e \in F} c(e)$ je nejmenší ze všech koster grafu $G$ .

Problém minimální kostry je problémem nalezení kostry $T$ grafu $G$ , jejíž suma cen všech hran bude nejmenší možná.

Hladový algoritmus:

$G = (V, E, c)$ $sort\ E\ by\ c(e)$ $S = \emptyset$ $\forall e \in E$ $\ \ \ \ if\ G' = (V, S \cup \{e\}, c)\ does\ not\ have\ cycle \Rightarrow S \leftarrow S \cup \{e\}$ $return\ G' = (V, S)$

Jarníkův algoritmus:

$G = (V, E, c)$ $P = \emptyset$ $S = \emptyset$ $P \leftarrow P \cup \{ any\ single\ v \in V \}$ $while\ P \neq V$ $\ \ \ \ L \leftarrow \{ v \in P | d(v) = 1 \}$ $\ \ \ \ E' \leftarrow \{ e = (v, w) | v \in L \land w \notin L \}$ $\ \ \ \ e \leftarrow e \in E' \land c(e) = min \{ c(f) \}, f \in E'$ $\ \ \ \ P \leftarrow P \cup \{ v, w | e = (v, w) \}$ $\ \ \ \ S \leftarrow S \cup \{ e \}$ $return\ G' = (V, S)$