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

<math>G = (V, E), E \subseteq V \times V</math>

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

<box round|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 <math>G = (V, F, \varepsilon), V \cap F = \emptyset</math>. <math>F</math> představuje indexovou množinu, <math>\varepsilon</math> je funkce z <math>F</math> do množiny vrcholů, která mapuje indexy z <math>F</math> na (multi)hrany: <math>\varepsilon: F \rightarrow {V \choose 2} \cup V \cup (V \times V)</math>.
V této definici:
  * <math>{V \choose 2}</math> představuje neorientované hrany
  * <math>V</math> představuje neorientované smyčky
  * <math>V \times V</math> představuje orientované hrany a smyčky
</box>

===== Vzdálenost v grafu =====

Pro graf <math>G = (V, E)</math> je <math>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)</math> procházka grafem <math>G</math> délky <math>n</math>. Cesta <math>p</math> v grafu <math>G</math> je procházka <math>w</math> grafem <math>G</math> taková, že se v ní každý vrchol procházky <math>w</math> vyskytuje právě jednou.

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

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

===== 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 <math>c</math> je cenová funkce hrany <math>c: E \rightarrow \mathbb{N}</math>:

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

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

<math>return\ d(u, x)</math>

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

===== Stromy =====

Strom je acyklický spojitý jednoduchý graf. Uzly stupně 1 jsou označovány jako listy. Každý strom o <math>n</math> uzlech má právě <math>n - 1</math> 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 <math>G = (V, E)</math> má kostru <math>T = (V, F), F \subseteq E</math>, přičemž <math>T</math> je strom. <math>T</math> je minimální kostra grafu <math>G = (V, E, c), c: E \rightarrow \mathbb{N}</math>, pokud <math>\sum_{e \in F} c(e)</math> je nejmenší ze všech koster grafu <math>G</math>.

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

Hladový algoritmus:

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

Jarníkův algoritmus:

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

====== Předměty ======
  * [[https://is.muni.cz/auth/predmety/predmet.pl?id=519186|FI:MA010]] Graph Theory (podzim 2009), doc. RNDr. Petr Hliněný, Ph.D.

====== Použitá literatura ======

-

====== Vypracoval ======

DevelX - Martin Jurča
stav - 100 %