Sled (graf)

Technology

12 hours ago

Author

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 = s posloupností uzlů (u), hran (h) a (v případě orientovaného sledu orientovanou) incidencí (i) . 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ý.