Razapinjuće stablo
Izvor: Hrvatska internetska enciklopedija
Razapinjuće stablo, pojam iz teorije grafova. Ako je graf povezan i neusmjeren, razapinjuće stablo u tom grafu je podgraf koji je stablo i razapinje taj graf. Stablo težine (tj. zbroja težina njegovih bridova) manje ili jednake težini svakog drugog razapinjućeg stabla u težinskom grafu predstavlja minimalno razapinjuće stablo u tom grafu.[1]
Razapinjući podgraf grafa [math]\displaystyle{ G=(V,E) }[/math] je graf oblika [math]\displaystyle{ G'=(V,E') }[/math], gdje je [math]\displaystyle{ E' \subseteq E }[/math].[2]
Izvori
- ↑ math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 8. siječnja 2020.)
- ↑ Prirodoslovno-matematički fakultet u Zagrebu Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)