Minimalno vpeto drevo

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.

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

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