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}\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

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}'\}=\emptyset$
• hranově disjunktní, pokud $\{e_{i}\}\cap \{e_{j}'\}=\emptyset$

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