Cesta (graf)

Cesta na šesti vrcholech

V teorii grafů se termínem cesta v grafu G = (V, E) označuje posloupnost $P = (v_0, e_1, v_1,\ldots, e_n, v_n)$, pro kterou platí $e_i = \{ v_{i-1}, v_i \}$ (případně $e_i = (v_{i-1}, v_i)$ pro orientované grafy) a navíc $v_i\ne v_j \mbox{ pro } i \ne 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

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 $w: E \rightarrow\mathbb{R}$, pak váha (cena, …) cesty P v grafu G je $\sum_{e\in P}{w(e)}$
• povolíme-li $v_0 = v_n$, formálně již nejde o cestu, ale o kružnici

Disjunktní cesty

Cesty $P = (v_0, e_1, v_1,\ldots, e_n, v_n)$ a $P' = (v_0', e_1', v_1',\ldots, e_m', v_m')$ jsou

• vrcholově disjunktní, pokud $\{v_i\}\cap \{v_j'\} = \empty$
• hranově disjunktní, pokud $\{e_i\}\cap \{e_j'\} = \empty$

Související články

• Eulerovský graf
• Souvislý graf
• Problém obchodního cestujícího