Sled (graf)

Sled v grafu je posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana.

Orientovaný sled v orientovaném grafu je posloupnost vrcholů $v_1,v_2...,v_n$ taková, že pro každé dva vrcholy $v_i,v_{i+1}$ existuje orientovná hrana vedoucí z vrcholu $v_i$ do vrcholu $v_{i+1}$.

Definice

Uvažujme graf $G=<H,U,i>$ s posloupností uzlů ($u$), hran ($h$) a (v případě orientovaného sledu orientovanou) incidencí ($i$) $<u_0,h_1,u_1,h_2,u_2,...,h_{n-1},u_{n-1},h_n,u_n>$. Tuto posloupnost nazýváme sledem mezi uzly $u_0$ a $u_n$.

Uzly $u_0$ a $u_n$ jsou krajními uzly. Zbylé uzly sledu nazýváme uzly vnitřními. Číslo $n$ nazýváme délkou sledu.

Pokud jsou uzly $u_0$ a $u_n$ shodné, tak sled nazýváme uzavřeným. V opačném případě jde o sled otevřený.

Literatura

• Šablona:Citace monografie