Sled (teória grafov)



Sled 
Sledom dĺžky n v grafe G nazývame striedavú postupnosť vrcholov  a hrán  grafu  kde hrana  je incidentná s vrcholmi , aj , pričom ak  nie je slučka, tak . 
Napr. na obrázku v grafe G existuje sled  s dĺžkou .

Ťah 

Ťahom v grafe nazývame sled, v ktorom sa každá hrana objavuje najviac raz. Ťah, v ktorom  sa nazýva uzavretý, ináč sa nazýva otvorený. Vyššie uvedený príklad sledu teda nie je ťahom, pretože hrana  sa v ňom objavuje dvakrát. Naproti tomu, ťahom je postupnosť (opäť v grafe G na obrázku)  s dĺžkou , pretože obsahuje navzájom rôzne hrany. V tomto prípade neplatí  teda ide o otvorený ťah. Avšak postupnosť  je uzavretým ťahom s dĺžkou , pretože platí .

Cesta 
Sled, v ktorom sa každý vrchol vyskytuje najviac raz, nazývame cestou. Ani jeden z hore uvedených sledov nie je cestou. Cestou v grafe G na obrázku je napr. postupnosť  s dĺžkou . Z definície cesty vypláva, že žiadna cesta neobsahuje tú istú hranu dvakrát, pretože každý vrchol môže byť v ceste obsiahnutý maximálne raz. Cesta je teda sledom, v ktorom je každý vrchol a každá hrana obsiahnutá práve raz.

Pozri aj 
 Vrchol (teória grafov)
 Graf (matematika)

Literatúra 
 Znám, Š: Kombinatorika a teória grafov. Bratislava, Matematicko-fyzikálna fakulta Univerzity Komenského. 1982, s. 39

Teória grafov