1.1 Základní pojmy

Definice 1.1 (Neorientovaný Graf)

Neorientovaný graf je uspořádaná dvojice \(( V , E )\), kde:

\(V\) je neprázdná konečná množina vrcholů
\(E\) je množina hran
- Hrana je dvouprvková podmnožina \(V\) (čili neuspořádaná dvojice vrcholů)
- Značíme {\(u\) , \(v\)}

Definice 1.2 (Sousedi a incidence)

Nechť \(e\) = {\(u\), \(v\)} je hrana v grafu \(G\). Pak řekneme, že:

Množinu všech dvouprvkových podmnožin množiny \(V\) (tedy všech možných hran) budeme označovat \(\binom{V}{2}\).
Obvykle budeme říkat jen graf, tj. neříkáme neorientovaný.
Nechť \(G\) je graf, pak:
- jeho množinu vrcholů a hran budeme značit \(V(G)\) a \(E(G)\),
- počet jeho vrcholů a hran budeme obvykle značit \(n = |V (G)|\) a \(m = |E(G)|\).

Definice 1.3 (Sled a Cesta)

Sled délky \(k\) v grafu \(G\) je sekvence \(v_{0}\), \(e_{1}\), \(v_{1}\), \(e_{2}\), ... , \(e_{k}\), \(v_{k}\) taková, že \(e_{i}\) = {\(v_{i−1}, v_{i}\)} a \(e_{i}\) ∈ \(E(G)\) pro všechna \(i\) = 1, ... , \(k\).
Cesta v grafu \(G\) je sled, ve kterém se neopakují vrcholy (a tedy ani hrany).
Má-li cesta P v grafu \(G\) koncové vrcholy \(s = v_{0}\) a \(t = v_{k}\), mluvíme o cestě z \(s\) do \(t\), nebo o s-t-cestě. (Připouštíme \(s = t\), cesta tedy může mít nulovou délku).
Délka s-t-cesty je počet hran v této cestě (v grafu \(G\)).
Vzdálenost \(s\) a \(t\) \(d(s, t)\) je délka nejkratší \(s\)-\(t\)-cesty