Cesta na siedmich vrcholoch

V teórii grafov sa termínom cesta v grafe G = (V, E) označuje postupnosť ${\displaystyle P=(v_{0},e_{1},v_{1},\ldots ,e_{n},v_{n})}$, pre ktorú platí ${\displaystyle e_{i}=\{v_{i-1},v_{i}\}}$ (poprípade ${\displaystyle e_{i}=(v_{i-1},v_{i})}$ pre orientované grafy) a naviac ${\displaystyle v_{i}\neq v_{j}{\mbox{ pro }}i\neq j}$. Je to teda postupnosť vrcholov, pre ktorú platí, že v grafe existuje hrana z daného vrcholu do jeho následníka. Žiadne dva vrcholy (a teda ani hrany) sa neopakujú.

Posledná podmienka odlišuje cestu od dvoch podobných pojmov:

• ťah je postupnosť, v ktorej sa môžu opakovať vrcholy, ale nie hrany
• sled je postupnosť, v ktorej sa môžu opakovať aj hrany

Vlastnosti

• dĺžka cesty je počet jej hrán alebo vrcholov (pre rôzne účely sa definuje rôzne)
• ak je graf G = (V, E) vážený s ohodnotením ${\displaystyle w:E\rightarrow \mathbb {R} }$, potom váha (cena, …) cesty P v grafe G je ${\displaystyle \sum _{e\in P}{w(e)}}$
• ak povolíme ${\displaystyle v_{0}=v_{n}}$, už nejde o cestu, ale o kružnicu

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}')}$ sú

• vrcholovo disjunktné, pokiaľ ${\displaystyle \{v_{i}\}\cap \{v_{j}'\}=\emptyset }$
• hranovo disjunktné, pokiaľ ${\displaystyle \{e_{i}\}\cap \{e_{j}'\}=\emptyset }$

Kružnica

Kružnicou nazývame uzavrenú cestu. Teda cestu, ktorá začína a končí v rovnakom vrchole.

Pozri aj

• Eulerovský graf
• Súvislý graf
• Problém obchodného cestujúceho

Tento článok je čiastočný alebo úplný preklad článku Cesta (graf) na českej Wikipédii.