Nechť $G = (V, E)$ je graf, uvažujme vrcholy $V = {v_0, v_1, v_2, … , v_n}$ a hrany $E =(e_1, e_2, … , e_m)$. $n,m ∈ ℕ$
Sled (Walk)
Sledem nazýváme takovou posloupnost vrcholů, které spojují vrcholy v0 a vk
$$P=(v_{0},e_{1},v_{1},\ldots ,e_{n},v_{n}).$$
Platí, že (vi−1, vi) ∈ ei pro 1 ≤ i ≤ l.
O sledu říkáme, že spojuje vrcholy v0, vk.
V prostém grafu můžeme sled popsat jen pomocí vrcholů. Délkou je počet hran.
Pokud jsou uzly v0 = vn, pak sled nazýváme uzavřeným. V opačném případě jde o sled otevřený.
Tah (Trail)
Mějme $T=(v_{0},v_{1},\ldots,v_{1},v_{n})$, tedy pro každé i, j = {1, … , n} platí, že když ei = ej , tak už i = j.
Tah je sled, ve kterém se neopakují žádné hrany.
Cesta (Path)
Je to tah a žádné vrcholy se neopakují, tedy pro každé i, j = {0, … , n} platí, že jestliže vi = vj, pak už nutně i = j nebo {i, j} = {0, n}.
U orientovaného grafu musí každá cesta postupovat pouze ve směru orientace hran.
Cesta je sled, ve kterém se neopakují vrcholy.
Vzdálenosti mezi vrcholy
d(u, v) Vzdálenost dvou vrcholů u a v v (orientovaném) grafu G je
délka nejkratší (orientované) cesty v G z vrcholu u do vrcholu v.
Pokud neexistuje cesta mezi dvěma vrcholy, pak je podle konvence hodnota ∞.
dG = min{ h | u → v }
Graf je souvislý, pokud pro každou vzdálenost u a v platí d(u, v) < ∞
Lemma (o zjednodušování sledů): Pro každý uv-sled existuje uv-cesta stejné nebo menší délky.
Důkaz: Pokud sled není cestou, znamená to, že se v něm opakují vrcholy. Část sledu mezi prvním a posledním výskytem tohoto vrcholu můžeme „vystřihnout“, čímž získáme uv-sled stejné nebo menší délky. Jelikož ubyla alespoň jedna hrana, opakováním tohoto postupu časem získáme cestu.
Důsledek: Nejkratší sled existuje a má stejnou délku jako nejkratší cesta.
Důkaz: Nejkratší cesta je jedním ze sledů. Pokud by tvrzení neplatilo, musel by existovat nějaký kratší sled. Ten by ovšem šlo zjednodušit na ještě kratší cestu.
Důsledek: Pro vzdálenosti platí trojúhelníková nerovnost: d(u, v) ≤ d(u, w) + d(w, v).
Ohodnocený graf
V ohodnoceném grafu je každé hraně přiřazeno tzv. ohodnocení, což může být například celé číslo, nebo reálné číslo. E(G) -> R
dG(u, v) = min{ delta(P)| P: u → v }