Cesta (graf)

Cesta na šesti vrcholech

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

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

Disjunktní cesty

Cesty ${\displaystyle P=(v_{0},e_{1},v_{1},\ldots ,e_{n},v_{n})}$ a ${\displaystyle P'=(v_{0}',e_{1}',v_{1}',\ldots ,e_{m}',v_{m}')}$ jsou

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