From Wikipedia, the free encyclopedia
Minimalno vpeto drevo je strategija, kjer je problem prikazan s povezanim neusmerjenim grafom z množico povezav E in množico točk (vozlišč) V. Točke v grafu predstavljajo mesta, ki jih želimo povezati, povezave pa so označene s cenami povezave med dvema mestoma. Naj bo graf neusmerjen in povezan. Podgraf G'=(V,E') se imenuje vpeto drevo, če je G' drevo. Ker za povezavo vseh mest zadošča, da v grafu obstaja ena pot med vsakim mestom, lahko problem definiramo kot iskanje minimalnega (najcenejšega) podgrafa, ki izpolnjuje ta pogoj. Tak podgraf je minimalno vpeto drevo.
Minimalno vpeto drevo vsebuje n-i povezav, pri čemer je n število točk v povezanem grafu in ne vsebuje ciklov.
Za določanje minimalnega vpetega drevesa poznamo tri algoritme:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
