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,\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 v_j\text{ 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\to ℝ$, 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,\dots ,e_n,v_n)$ a $P^{\prime }=({v_0}^{\prime },{e_1}^{\prime },{v_1}^{\prime },\dots ,{e_m}^{\prime },{v_m}^{\prime })$ jsou

• vrcholově disjunktní, pokud $\{v_i\}\cap \{{v_j}^{\prime }\}=\mathrm{\varnothing }$
• hranově disjunktní, pokud $\{e_i\}\cap \{{e_j}^{\prime }\}=\mathrm{\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