Cesta (teória grafov)

Cesta na siedmich vrcholoch

V teórii grafov sa termínom cesta v grafe G = (V, E) označuje postupnosť $P=(v_0,e_1,v_1,\dots ,e_n,v_n)$, pre ktorú platí $e_i=\{v_{i-1},v_i\}$ (poprípade $e_i=(v_{i-1},v_i)$ pre orientované grafy) a naviac $v_i\ne v_j\text{ pro }i\ne j$. Je to teda postupnosť vrcholov, pre ktorú platí, že v grafe existuje hrana z daného vrcholu do jeho následníka. Žiadne dva vrcholy (a teda ani hrany) sa neopakujú.

Posledná podmienka odlišuje cestu od dvoch podobných pojmov:

• ťah je postupnosť, v ktorej sa môžu opakovať vrcholy, ale nie hrany
• sled je postupnosť, v ktorej sa môžu opakovať aj hrany

Vlastnosti

• dĺžka cesty je počet jej hrán alebo vrcholov (pre rôzne účely sa definuje rôzne)
• ak je graf G = (V, E) vážený s ohodnotením $w:E\to ℝ$, potom váha (cena, …) cesty P v grafe G je $\sum _{e\in P}w(e)$
• ak povolíme $v_0=v_n$, už nejde o cestu, ale o kružnicu

Disjunktné cesty

Cesty $P=(v_0,e_1,v_1,\dots ,e_n,v_n)$ a $P^{\prime }=({v_0}^{\prime },{e_1}^{\prime },{v_1}^{\prime },\dots ,{e_m}^{\prime },{v_m}^{\prime })$ sú

• vrcholovo disjunktné, pokiaľ $\{v_i\}\cap \{{v_j}^{\prime }\}=\mathrm{\varnothing }$
• hranovo disjunktné, pokiaľ $\{e_i\}\cap \{{e_j}^{\prime }\}=\mathrm{\varnothing }$

Kružnica

Kružnicou nazývame uzavrenú cestu. Teda cestu, ktorá začína a končí v rovnakom vrchole.

Pozri aj

• Eulerovský graf
• Súvislý graf
• Problém obchodného cestujúceho