Pogovor:Minimalno vpeto drevo
Narobe definicija. Minimalno vpeto drevo ni strategija, ampak vpeto drevo, ki je obenem najcenejši podgraf G' = <V',E'> danega povezanega grafa G = <V,E>, kjer veljajo naslednje relacije V'⊂ V in E'= E.
V - množica vozlišč
E - množica povezav
- drevo je podatkovna struktura, ki je sestavljena iz večih vozlišč, ki so med seboj povezana z usmerjenimi/neusmerjenimi povezavami v povezan graf brez ciklov
-povezan graf je graf v katerem med vsemi njegovimi vozlišči obstaja pot
-pot je podana z zaporedjem vozlišč v1,v2, ..., vk tako, da velja da je povezava <vi, vi+1> ∈ E , i ∈ [1,k]
-cena je vsota vrednosti vseh povezav danega grafa
-najcenejši podgraf je podgraf G', ki ima manjšo ali enako ceno kot ostali podgrafi danega