Berlinski geometar s početka 19. stoljeća Jacob Steinerpostavili zadatak kako povezati tri sela tako da im je duljina bila najkraća. Poslije je generalizirao ovaj problem: potrebno je pronaći točku na ravnini tako da je udaljenost od nje do n drugih točaka najmanja. U 20. stoljeću nastavljen je rad na ovoj temi. Odlučeno je uzeti nekoliko točaka i povezati ih na takav način da je udaljenost između njih bila najkraća. Sve je ovo poseban slučaj problema koji se proučava.
Pohlepni algoritmi
Kruskalov algoritam pripada "pohlepnim" algoritmima(nazivaju se i gradijentom). Suština je najveća isplata na svakom koraku. Ne uvijek "pohlepni" algoritmi daju najbolje rješenje problema. Postoji teorija koja pokazuje da kada se primjenjuju na određene probleme, oni pružaju optimalno rješenje. Ovo je teorija matroida. Kruskalov algoritam spada u takve probleme.
Pronalaženje okvira minimalne težine
Razmatrani algoritam konstruira optimalnograf žica. Problem je sljedeći. Dobit ćete neusmjereni graf bez više rubova i petlji, a na skupu njegovih bridova data je težinska funkcija w koja svakom rubu e dodjeljuje broj - težinu brida - w (e). Težina svakog podskupa iz skupa bridova određuje se zbrojem težina njegovih bridova. Potrebno je pronaći okvir s najmanjom težinom.
opis
Kruskalov algoritam radi ovako. Prvo su svi rubovi izvornog grafikona poredani u rastućem poretku težina. U početku kostur ne sadrži rubove, ali uključuje sve vrhove grafa. Nakon sljedećeg koraka algoritma, jedan rub dodaje se već izgrađenom dijelu kostura, koji je rasprostranjena šuma. Nije slučajno odabran. Svi rubovi grafikona koji ne pripadaju žičanom okviru mogu se nazvati crvenim i zelenim. Vrhovi svakog crvenog ruba nalaze se u istoj komponenti povezanosti šume u izgradnji, a vrhovi zelenog ruba su u različitim. Stoga, ako tamo dodate crveni rub, pojavit će se ciklus, a ako je zeleni, komponenta povezanosti u šumi dobivena nakon ovog koraka bit će jedna manje. Tako se rezultirajućoj konstrukciji ne može dodati crveni rub, već se može dodati bilo koji zeleni rub da bi se dobila šuma. I dodaje se zeleni rub s minimalnom težinom. Rezultat je najlakši okvir.
izvršenje
Označimo trenutnu šumu F. Dijeli skup vrhova grafa na područja povezanosti (njihov spoj formira F i oni se ne sijeku u parovima). Crveni rubovi imaju oba vrha u istom dijelu. Dio (x) je funkcija koja za svaki vrh x vraća ime dijela kojem x pripada. Ujediniti (x, y) je postupak koji gradi novu particiju, koja se sastoji od objedinjavanja x i y dijelova i svih ostalih dijelova. Neka je n broj bridova na grafikonu. Svi su ti pojmovi uključeni u Kruskalov algoritam. provedba:
Poredajte sve rubove grafikona od 1. do n. U rastućem poretku težina. (ai, bi su vrhovi brida numerirani).
za i = 1 do n učiniti.
x: = Dio (ai).
y: = Dio (bi).
Ako x nije jednako y, tada Unite (x, y), uključite rub i u F.
Ispravnost
Neka je T kostur izvornog grafa konstruiranog pomoću algoritma Kruskal, a S njegov proizvoljan kostur. Moramo dokazati da w (T) ne prelazi w (S).
Neka je M skup bridova S, P skup rubovaT. Ako S nije jednako T, tada postoji rub et okvira T koji ne pripada S. Pridajemo et et S. Nastaje ciklus, nazovimo ga C. Uklanjamo iz C bilo koji rub koji pripada S. Dobivamo novi okvir, jer rubovi, a u njemu ima isto toliko vrhova. Njegova težina ne prelazi w (S), jer je w (et) najviše w (e) na temelju Kruskalovog algoritma. Ponavljat ćemo ovu operaciju (zamjenjujući rubove S bridovima T) dok ne dobijemo T. Težina svakog sljedećeg rezultirajućeg okvira nije veća od težine prethodne, odakle proizlazi da w (T) nije veća od w (S).
Također, ispravnost Kruskalovog algoritma proizlazi iz Rado-Edmondsovog teorema o matroidima.
Primjeri uporabe algoritma Kruskal
Dat je graf s vrhovima a, b, c, d, e i bridovima (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Utezi rebara prikazani su u tablici i na slici. U početku šuma F u izgradnji sadrži sve vrhove grafa i ne sadrži rubove. Kruskalov algoritam prvo dodaje rub (a, e), jer ima najmanju težinu, a vrhovi a i e nalaze se u različitim povezanim komponentama šume F (rub (a, e) je zelen), a zatim rub (c, d), dakle da ovaj rub ima najmanju težinu bridova grafa koji ne pripada F, a on je zelen, tada se rub (a, b) dodaje iz istih razloga. Ali rub (b, e) se preskače, iako ima najmanju težinu od preostalih bridova, jer je crven: vrhovi b i e pripadaju istoj povezanoj komponenti šume F, odnosno ako F dodamo rub (b, e), on tvori ciklus. Zatim se dodaje zeleni rub (b, c), preskače crveni rub (c, e), a zatim d, e. Dakle, bridovi (a, e), (c, d), (a, b), (b, c) se dodaju sekvencijalno. Od njih se sastoji optimalni kostur početnog grafa. Tako algoritam radi u ovom slučaju Slikano. Primjer je to pokazao.
Na slici je prikazan graf koji se sastoji od dvije povezane komponente. Podebljane crte prikazuju rubove optimalnog kostura (zelenog), izrađenog pomoću algoritma Kruskal.
Gornja slika prikazuje izvorni graf, a donja kostur minimalne težine konstruiran za njega pomoću razmatranog algoritma.
Slijed dodanih bridova: (1,6); (0,3), (2,6) ili (2,6), (0,3) - nije važno; (3.4); (0,1), (1,6) ili (1,6), (0,1) je također indiferentno (5,6).
Kruskalov algoritam pronalazi praktičnu primjenu, na primjer, za optimizaciju polaganja komunikacija, cesta u novim naseljima naselja svake zemlje, kao i u drugim slučajevima.
