On the leaves of graph search trees

angleški

2026

letnik 26, številka 1, article p1.08

akordni grafi   iskalna drevesa grafov   iskanje v grafu   listi

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Iskanja v grafih in njihova ustrezna iskalna drevesa so široko uporabljena v algoritmični teoriji grafov. Problem, ali je dano vpeto drevo lahko iskalno drevo grafa, je bil obravnavan za različna iskanja, razrede grafov in paradigme iskalnih dreves. Podobno je bilo vprašanje, ali je lahko določeno vozlišče obiskano zadnje pri nekem iskanju, v zadnjih letih obsežno raziskano. Združujemo ti dve vprašanji z obravnavo vprašanja, ali je lahko vozlišče list iskalnega drevesa grafa. Pokažemo, da je za določena iskalna drevesa, vključno z DFS drevesi, ta problem enostaven, če dovolimo, da je list prvo vozlišče v iskalnem urejanju. Ta rezultat postavimo v kontrast s tem, da pokažemo, kako problem postane težaven za mnoga iskanja, vključno z DFS in BFS, če prepovemo, da je list prvo vozlišče. Poleg tega predstavimo več strukturnih in algoritmičnih rezultatov za liste iskalnih dreves akordnih grafov.

27.10.2026