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ů taková, že pro každé dva vrcholy existuje orientovná hrana vedoucí z vrcholu do vrcholu .[1]
Definice
Uvažujme graf s posloupností uzlů (), hran () a (v případě orientovaného sledu orientovanou) incidencí () . Tuto posloupnost nazýváme sledem mezi uzly a .
Uzly a jsou krajními uzly. Zbylé uzly sledu nazýváme uzly vnitřními. Číslo nazýváme délkou sledu.
Pokud jsou uzly a shodné, tak sled nazýváme uzavřeným. V opačném případě jde o sled otevřený.
Reference
Literatura
-
KOLÁŘ, Josef. Teoretická informatika. Praha: [s.n.], 2004. ISBN 80-900853-8-5. Kapitola 2.1, s. 23.
Zdroj
Poslední aktualizace obsahu: 2024-04-04 14:10:21
Zdroj: Wikipedia (autoři článku Sled (graf))
Licence textu: CC-BY-SA-3.0 Unported
Tento článek byl automaticky přejat z Wikipedie. Na obrázcích nebyly provedeny žádné změny. Obrázky se zobrazují ve zmenšené velikosti (jako miniatury). Kliknutím na obrázek získáte další informace o autorovi a licenci. Byly změněny prvky designu, odstraněny některé odkazy specifické pro Wikipedii (např. odkazy na Editaci a nebo na neexistující hesla) a provedena optimalizace pro rychlé načítání.