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\ne 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