Sled (teória grafov)

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
Graf G

Sled[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

Ť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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

Literatúra[upraviť | upraviť zdroj]

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