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ú.

Cesta na siedmich vrcholoch

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

upraviť
  • 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

upraviť

Cesty   a  

  • vrcholovo disjunktné, pokiaľ  
  • hranovo disjunktné, pokiaľ  

Kružnica

upraviť

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

Pozri aj

upraviť

Tento článok je čiastočný alebo úplný preklad článku Cesta (graf) na českej Wikipédii.