Cesta (teória grafov)

V teórii grafov sa termínom cesta v grafe G = (V, E) označuje postupnosť , pre ktorú platí  (poprípade  pre orientované grafy) a naviac . 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 , potom váha (cena, …) cesty P v grafe G je 
ak povolíme , už nejde o cestu, ale o kružnicu

 Disjunktné cesty 
Cesty  a  sú
vrcholovo disjunktné, pokiaľ 
hranovo disjunktné, pokiaľ 

 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

Kategória:Teória grafov