Minimalno vpeto drevo

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Definicija

Imamo graf G=(V,E), kjer je V množica vozlišč (angl. vertex - vozlišče) in E množica neusmerjenih povezav (angl. edge - povezava). Vsa vozlišča grafa so povezana (stopnja vsakega vozlišča je vsaj 1), povezave pa imajo uteži. Minimalno vpeto drevo T je acikličen podgraf grafa G, ki vsebuje vsa vozlišča grafa in zanj velja, da je njegova skupna teža (vsota uteži vseh povezav v njem) minimalna. Najmanjše vpeto drevo imenujemo še najcenejše vpeto drevo ali minimalno vpeto drevo.

Naj bo cena drevesa vsota vrednosti vseh povezav tega drevesa. Potem je minimalno vpeto drevo tisto vpeto drevo, ki ima ceno manjšo ali enako cenam vseh drugih vpetih dreves.

Primer minimalnega vpetega drevesa

Iskanje minimalnega vpetega drevesa

Uporaba

Gradnja kabelskega omrežja med mesti

  • Med n mesti želimo speljati kabelsko omrežje. Gradnje ni nujno začeti tam, kjer bo centralna oddajna postaja, saj je pomembna le dosegljivost vsake točke.
  • Začnemo v nekem mestu. Med tistimi mesti, do katerih je možno priti, izberemo tistega, do katerega lahko položimo kabel najceneje.
  • Položimo kabel.
  • Pregledamo, koliko nas stane gradnja do mest. Poiščemo torej najcenejšo povezavo med vozlišči v doslej zgrajenem vpetem drevesu in tistimi, ki tam še niso.
  • Dodamo najcenejše dosegljivo mesto.

električna napeljava

vodovodna napeljava

...

Osebna orodja