Cesta (graf)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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

Související články[editovat | editovat zdroj]