Minimalno vpeto drevo
(Preusmerjeno s strani Minimalna vpeta drevesa)
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: