Cesta (graf)

V teorii grafů se termínem cesta v grafu G = (V, E) označuje posloupnost $P=(v_0,e_1,v_1,\dots <!--\; \dots \; -->,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 <!--\; \ne \; -->v_j\text{ pro }i\ne <!--\; \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\to <!--\; \to \; -->R$, pak váha (cena, …) cesty P v grafu G je $\underset{e\in <!--\; \in \; -->P}{\sum <!--\; \sum \; -->}w\left(e\right)$
• 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,\dots <!--\; \dots \; -->,e_n,v_n)$ a $P^{\prime }=(v_0^{\prime },e_1^{\prime },v_1^{\prime },\dots <!--\; \dots \; -->,e_m^{\prime },v_m^{\prime })$ jsou

• vrcholově disjunktní, pokud $\left\{v_i\right\}\cap <!--\; \cap \; -->\left\{v_j^{\prime }\right\}=\mathrm{\varnothing <!--\; \varnothing \; -->}$
• hranově disjunktní, pokud $\left\{e_i\right\}\cap <!--\; \cap \; -->\left\{e_j^{\prime }\right\}=\mathrm{\varnothing <!--\; \varnothing \; -->}$

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

Autoritní data	LCCN: sh85098695 NLI: 987007529530805171