Zobrazení zdroje stránky Cesta (graf)

[[Soubor:Cesta (graf).svg|náhled|Cesta na šesti vrcholech]]
V [[teorie grafů|teorii grafů]] se termínem '''cesta''' v [[Graf (teorie grafů)|grafu]] ''G = (V, E)'' označuje [[posloupnost]] <math>P = (v_0, e_1, v_1,\ldots, e_n, v_n)</math>, pro kterou platí <math>e_i = \{ v_{i-1}, v_i \}</math> (případně <math>e_i = (v_{i-1}, v_i)</math> pro [[orientovaný graf|orientované grafy]]) a navíc <math>v_i\ne v_j \mbox{ pro } i \ne j</math>. Je to tedy posloupnost [[vrchol (graf)|vrcholů]], pro kterou platí, že v grafu existuje [[hrana (graf)|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 (graf)|tah]]'' je posloupnost, kde se mohou opakovat vrcholy, ale ne hrany
* ''[[sled (graf)|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 <math>w: E \rightarrow\mathbb{R}</math>, pak ''váha'' (cena, …) cesty ''P'' v grafu G je <math>\sum_{e\in P}{w(e)}</math>
* povolíme-li <math>v_0 = v_n</math>, formálně již nejde o cestu, ale o [[kružnice (graf)|kružnici]]

== Disjunktní cesty ==
Cesty <math>P = (v_0, e_1, v_1,\ldots, e_n, v_n)</math> a <math>P' = (v_0', e_1', v_1',\ldots, e_m', v_m')</math> jsou
* ''vrcholově disjunktní'', pokud <math>\{v_i\}\cap \{v_j'\} = \empty</math>
* ''hranově disjunktní'', pokud <math>\{e_i\}\cap \{e_j'\} = \empty</math>

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

[[Kategorie:Rovinné grafy]]
[[Kategorie:Grafové pojmy]]