Cesta (graf)

Technology

12 hours ago

Author

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\ne v_j \mbox{ 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 \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'\} = \empty * hranově disjunktní, pokud \{e_i\}\cap \{e_j'\} = \empty