V teorii grafů se termínem cesta v grafuG = (V, E) označuje posloupnost, pro kterou platí (případně pro orientované grafy) a navíc . Je to tedy posloupnost vrcholů, pro kterou platí, že v grafu existuje hrana z daného vrcholu do jeho následníka. Žádné dva vrcholy (a tedy ani hrany) se přitom neopakují.
Poslední podmínka odlišuje cestu od dvou podobných pojmů:
tah je posloupnost, kde se mohou opakovat vrcholy, ale ne hrany
sled je posloupnost, kde se mohou opakovat i hrany
Vlastnosti
délka cesty je počet jejích hran nebo vrcholů (pro různé účely se definuje různě)
je-li graf G = (V, E) vážený s ohodnocením , pak váha (cena, …) cesty P v grafu G je
povolíme-li , formálně již nejde o cestu, ale o kružnici
Disjunktní cesty
Cesty a jsou
vrcholově disjunktní, pokud
hranově disjunktní, pokud
Kružnice
Kružnicí nazýváme uzavřenou cestu. Tedy cestu, která začíná a končí ve stejném vrcholu.
Tento článek byl automaticky přejat z Wikipedie. Na obrázcích nebyly provedeny žádné změny. Obrázky se zobrazují ve zmenšené velikosti (jako miniatury). Kliknutím na obrázek získáte další informace o autorovi a licenci. Byly změněny prvky designu, odstraněny některé odkazy specifické pro Wikipedii (např. odkazy na Editaci a nebo na neexistující hesla) a provedena optimalizace pro rychlé načítání.