Minimalno vpeto drevo

Zgled minimalnega vpetega drevesa. Številke pomenijo ceno povezave med točkama. Povezane so vse točke.

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:

• Primov algoritem
• Kruskalov algoritem
• Dijkstrov algoritem