Cesta (graf)

V teorii grafů se termínem cesta v grafu G = (V, E) označuje posloupnost ${\displaystyle P=(v_{0},e_{1},v_{1},\ldots ,e_{n},v_{n})}$, pro kterou platí ${\displaystyle e_{i}=\{v_{i-1},v_{i}\}}$ (případně ${\displaystyle e_{i}=(v_{i-1},v_{i})}$ pro orientované grafy) a navíc ${\displaystyle v_{i}\neq v_{j}{\mbox{ pro }}i\neq j}$. 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