Izpitno vprašanje RAČ2PRA 16500

Iz MaFiRaWiki

Vprašanje

Razlike med Primovim in Kruskalovim postopkom, kdaj bi lahko uporabili ta postopek?

Odgovor

    Razlika med Primovim in Kruskalovim postopkom
  • Primov postopek gradi minimalno vpeto drevo tako, da množica U na začetku vsebuje eno samo (poljubno) vozlišče in v vpeto drevo U vsakič doda najkrajšo povezavo med U in U - V.
  • Kruskalov postopek pa gradi minimalni vpeti gozd. Na začetku je vsako vozlišče eno drevo. V enem koraku postopka združi dve minimalni vpeti drevesi v eno minimalno vpeto drevo, tako da uporabi minimalno povezavo med dvema drevesoma. Paziti moramo le na to, da povezava ne povezuje dveh vozlišč v istem drevesu, saj sicer ustvarimo cikel. V povezanem grafu Kruskalov postopek zaporedoma združi vsa vpeta drevesa v eno minimalno vpeto drevo.


Postopka bi lahko uporabljali za reševanje problemov načrtovanja čim cenejših energetskih, prometnih in komunikacijskih omrežji. Problem energetske, prometne ali komunikacijske povezave mest nekega ozemlja lahko rešujemo s pomočjo neusmerjenega grafa. Vozlišča v grafu so vsa mesta, ki jih želimo povezati, povezave pa so označene z razdaljami oziroma cenami povezave med dvema mestoma. 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. Minimalno vpeto drevo, pa gradimo s Primovim ali pa Kruskalovim postopkom.

Osebna orodja