Zobrazenie zdroja stránky Sled (teória grafov)

[[Súbor:6n-graf.svg|náhľad|Graf G]]
== Sled ==
'''Sled'''om dĺžky '''n''' v grafe '''G''' nazývame striedavú postupnosť vrcholov <math>x_i</math> a hrán <math>h_i</math> grafu <math>x_0,h_1,x_1,h_2,...,x_{n-1},h_n,x_n</math> kde hrana <math>h_i</math> je incidentná s vrcholmi <math>x_{i-1}</math>, aj <math>x_i (i=1,2,...,n)</math>, pričom ak <math>h_i</math> nie je slučka, tak <math>x_i \neq x_{i-1}</math>. 
Napr. na obrázku v grafe G existuje sled <math>6, 64, 4, 45, 5, 52, 2, 25, 5</math> s dĺžkou <math>4</math>.

== Ťah ==

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

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

[[Kategória:Teória grafov]]