INTERNACIONALNI UNIVERZITET TRAVNIK
POLITEHNIČKI FAKULET – RAČUNARSTVO I INFORMATIKA
TRAVNIK
MINIMALNA RAZAPINJUĆA STABLA,
PLANARNOST I
PLATONOVA TIJELA
Diskretna matematika
Mentor:
prof. Resić Sead
Student:
Sabina Husanović
PT-110/15-II
Travnik, novembar 2016.
Sabina Husanović
Seminarski rad
Minimalna razapinjujuća stabla
Kako bi se razumjelo šta je to razapinjujuće stablo potrebno je pogledati sliku
grafa Slika 1
Graf na slici pokazuje cikluse, tj. puteve u grafu koji započinju i završavaju
istim vrhom. Ukoliko bi se uklonio dovoljan broj bridova iz grafa dobilo bi se graf
koji nema cikluse te takav graf se naziva stablo. Stablo koje se dobija uklanjanjem
određenog broja bridova iz grafa, a da pritom dobijeni graf ostane povezan, naziva se
razapinjujuće stablo[1].
Minimalno razapinjujuće stablo je razapinjujuće stablo nekog povezanog
težinskog i neusmjerenog grafa koji sadrži sve čvorove tog grafa, a zbir težina
njegovih grana je minimalan. Jedan graf može imati više ovakvih stabala, zavisno od
svoje konfiguracije. Minimalno razapinjujuće stablo je razapinjujuće stablo čija je
težina manja ili jednaka u odnosu na ostala razapinjujuća stabla nekog grafa[2]
2
Slika 1: Primjer grafa
Sabina Husanović
Seminarski rad
Graf na Slika 2 pretstavlja minimalno razapinjujuće stablo dobijeno iz grafa na
Slika 1. Za dobijanje takvih razapinjujućih stabala postoje dva poznata algoritma koja
će biti opisana u nastavku.
Algoritmi
Prvi algoritam za traženje razapinjujućeg stabla razvio je Češki naučnik
Otakar Boruvka
9
1926 g. Njegova svrha je bila izgradnja električne mreže za Moskvu.
Algoritam se izvršava u nekoliko faza, u svakoj fazi identifikuje se šuma
F
koja se
sastoji od grana identičnih sa svakim čvorom u grafu
G
a zatim formira graf
G1 = G
F
kao ulaz sljedećem koraku. Ovdje
G F
označava graf dobijen od
G
odsjecanjem
grana u
F[3]
.
Dobijanje razapinjujućeg stabla iz zadanog grafa
Primovim algoritmom
10
može se prikazati sljedećim postupkom:
9
https://en.wikipedia.org/wiki/Otakar_Bor%C5%AFvka
10 Primov algoritam je algoritam u teoriji grafova koja nalazi minimalno razapinjuće stablo za
povezani težinski graf.
3
Slika 2: Minimalno razapinjujuće stablo
