Cesta (graf)

Z Wikipedie, otevřené encyklopedie

Cesta na šesti vrcholech
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í ei = {vi − 1,vi} (případně ei = (vi − 1,vi) 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

[editovat] 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 v0 = vn, formálně již nejde o cestu, ale o kružnici

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

[editovat] Podívejte se také na