Otevřít hlavní menu

Cesta (graf)

posloupnost po sobě jdoucích vrcholů spojených hranami v grafu, ve které se žádný vrchol neopakuje
Cesta na šesti vrcholech

V teorii grafů se termínem cesta v grafu G = (V, E) označuje posloupnost , pro kterou platí (případně pro orientované grafy) a navíc . 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

Obsah

VlastnostiEditovat

  • 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  , pak váha (cena, …) cesty P v grafu G je  
  • povolíme-li  , formálně již nejde o cestu, ale o kružnici

Disjunktní cestyEditovat

Cesty   a   jsou

  • vrcholově disjunktní, pokud  
  • hranově disjunktní, pokud  

KružniceEditovat

Kružnicí nazýváme uzavřenou cestu. Tedy cestu, která začíná a končí ve stejném vrcholu.

Související článkyEditovat