Naučte se

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 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 }

Související