náhled|Cesta na šesti vrcholech V teorii grafů se termínem cesta v grafu G = (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.
Související články Eulerovský graf Souvislý graf Problém obchodního cestujícího
Kategorie:Rovinné grafy Kategorie:Grafové pojmy