Cestování grafem

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 $v_0$ a $v_k$ $P=(v_{0},e_{1},v_{1},\ldots ,e_{n},v_{n}).$

Platí, že $(v_{i−1}, v_i) ∈ e_i$ pro $1 ≤ i ≤ l$. O sledu říkáme, že spojuje vrcholy v₀, v_k.

V prostém grafu můžeme sled popsat jen pomocí vrcholů. Délkou je počet hran.

Pokud jsou uzly $v_0 = v_n$, 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ž $e_i = e_j$ , 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 $v_i = v_j$, 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 ∞.

$d_G = 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

$d_G(u, v) = min\{ delta(P)| P: u → v \}$