Sled (teória grafov)

postupnosť vrcholov a hrán grafu
Graf G

SledUpraviť

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  .

ŤahUpraviť

Ť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í  .

CestaUpraviť

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 ajUpraviť

LiteratúraUpraviť

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