Cesta (teória grafov)
Vzhled
![](https://upload.wikimedia.org/wikipedia/commons/thumb/b/bd/Cesta_%28graf%29.svg/220px-Cesta_%28graf%29.svg.png)
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
[upraviť | upraviť zdroj]- 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ť | upraviť zdroj]Cesty a sú
- vrcholovo disjunktné, pokiaľ
- hranovo disjunktné, pokiaľ
Kružnica
[upraviť | upraviť zdroj]Kružnicou nazývame uzavrenú cestu. Teda cestu, ktorá začína a končí v rovnakom vrchole.
Pozri aj
[upraviť | upraviť zdroj]Tento článok je čiastočný alebo úplný preklad článku Cesta (graf) na českej Wikipédii.