Sled (teória grafov)

Graf G

Sled

Sledom dĺžky n v grafe G nazývame striedavú postupnosť vrcholov $x_{i}$ a hrán $h_{i}$ grafu $x_{0},h_{1},x_{1},h_{2},...,x_{n-1},h_{n},x_{n}$ kde hrana $h_{i}$ je incidentná s vrcholmi $x_{i-1}$, aj $x_{i}(i=1,2,...,n)$, pričom ak $h_{i}$ nie je slučka, tak $x_{i}\neq x_{i-1}$. Napr. na obrázku v grafe G existuje sled $6,64,4,45,5,52,2,25,5$ s dĺžkou $4$.

Ťah

Ťahom v grafe nazývame sled, v ktorom sa každá hrana objavuje najviac raz. Ťah, v ktorom $x_{0}=x_{n}$ sa nazýva uzavretý, ináč sa nazýva otvorený. Vyššie uvedený príklad sledu teda nie je ťahom, pretože hrana $52$ sa v ňom objavuje dvakrát. Naproti tomu, ťahom je postupnosť (opäť v grafe G na obrázku) $6,64,4,43,3,32,2,21,1,15,5,54,4$ s dĺžkou $6$, pretože obsahuje navzájom rôzne hrany. V tomto prípade neplatí $x_{0}=x_{n}$ teda ide o otvorený ťah. Avšak postupnosť $4,43,3,32,2,25,5,54,4$ je uzavretým ťahom s dĺžkou $4$, pretože platí $x_{0}=x_{n}$.

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ť $6,64,4,45,5,51,1$ s dĺžkou $3$. 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