Kruskalov algoritam - izgradnja optimalnog kostura

Početkom 19. stoljeća, geometri iz Berlina, Jacob Steiner, postavili su zadatak kako povezati tri sela tako da njihova dužina bude najkraća. Kasnije je generalizirao ovaj problem: potrebno je pronaći točku na ravnini tako da je udaljenost od nje do n drugih točaka bila najmanja. U 20. stoljeću nastavlja se 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. Ovo je poseban slučaj problema koji se istražuje.

Pohlepni algoritmi

Kruskalov algoritam odnosi se na "pohlepni" algoritmi (oni se nazivaju i algoritmi gradijenta). Bit onih - najveća pobjeda na svakom koraku. Ne uvijek "pohlepni" algoritmi daju najbolje rješenje zadatku. Postoji teorija koja pokazuje da se, kada se primjenjuju na specifične probleme, pružaju optimalno rješenje. Ovo je teorija matroida. Kruskalov algoritam se odnosi na takve probleme.

Pronalaženje kostura minimalne težine

Algoritam koji se razmatra konstruira optimalni kostur grafikona. Problem je u tome što slijedi. Dan neusmjereni graf bez paralelnih bridova i petlje, i skup rubova daje funkciju težine w, a dodjeljuje broj svakog ruba e - težina rebro - w (e). Težina svakog podskupa skupova rubova određuje se zbrojem težina njegovih rubova. Potrebno je pronaći kostur od najmanje težine.

opis

Kruskalov algoritam ovako funkcionira. Prvo, svi rubovi izvornog grafikona su poredani po porastu težine. U početku, okvir ne sadrži rubove, ali uključuje sve vrhove grafikona. Nakon sljedećeg koraka algoritma, jedan rub se dodaje već izgrađenom dijelu okvira, koji je šumska širina. Nije izabrano samovoljno. Svi rubovi grafikona koji ne pripadaju kosturu mogu se nazvati crveno i zeleno. Vrhovi svake crvene rebra su u jednoj komponenti povezanosti šume koja se gradi, a vrhovi zelenog su u različitim komponentama. Stoga, ako dodate crvenu rubu, pojavit će se ciklus, a ako zeleni - u rezultiranom koraku šume, komponenta povezivanja bit će manja za jedan. Dakle, ne može se dodati crveni rub u dobivenu konstrukciju, ali se može dodati bilo koji zeleni rub kako bi se dobila šuma. I dodaje se zeleni rebro s minimalnom težinom. Kao rezultat, dobiva se skelet s najmanjom težinom.

izvršenje

Označavamo trenutnu šumu F. Podjeljuje skup vertica grafikona u povezane domene (njihovi sindikalni oblici F, a ne presijecaju se parovima). Crveni rubovi imaju oba vrha u jednom dijelu. Dio (x) je funkcija koja vraća naziv dijela kojem x pripada za svaki vrh x. Unite (x, y) je postupak koji gradi novu particiju koja se sastoji od sjedinjenja dijelova x i y i svih ostalih dijelova. Neka n bude broj rubova grafikona. Svi ti pojmovi su uključeni u algoritam Kruskal. provedba:

1. Rasporedite sve rubove grafikona od prvog do nultih uzlaznih utega. (ai, bi su vrhovi ruba s indeksom i).

2. za i = 1 do n.

3. x: = Dio (ai).

4. y: = Dio (bi).

5. Ako x nije jednak y, onda Unite (x, y), uključite rub s brojem i u F.

ispravnost

Neka T bude kostur izvornog grafikona konstruiranog korištenjem algoritma Kruskal, i neka S bude njegov proizvoljni kostur. Potrebno je dokazati da w (T) ne prelazi w (S).

Neka M - više perajica S, P - veći broj krilaca T. Ako S nije jednak T, tada postoji i okvir rebro T, ne pripadaju S. S. et graničiti ciklus, to se zove C C ukloniti iz svih rubnih es, pripadaju S. smo dobili novi okvir, jer su rubovi i vrhovi u njoj mnogo. Njegova težina nije veća od w (S), budući w (et) više ne w (e) u električnu Kruskal algoritam. Ovaj postupak (T S zamjena rebra na rebrima) se ponavlja sve dok se dobiti T. težinu svakog sljedećeg primljene okvira nije veća od prethodne težine, što pokazuje da masa (T) nije veća od w (S).

Također, ispravnost algoritma Kruskal slijedi iz Rado-Edmondsovog teorema na matroidima.

Primjeri primjene algoritma Kruskal

Dan graf sa čvorovima a, b, c, d, e i rebara (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Težine rubova su prikazani u tablici i na slici. U početku, izgradnja šumskih F sadrži sve vrhove grafa i ne sadrži nikakve rebra. Algoritam Kruskal najprije dodati rebro (a, e), budući da težina imao najmanji, a vrhovi A i E su u različite dijelove drvo povezivanja F (rebra (a, e) zeleno), a zatim je rebro (c, d), jer da barem taj rub težina bridova grafa, ne pripadaju F, a to je zelena, onda iz istih razloga prikupljati rub (a, b). Ali rub (b, e) je prošao, iako je i minimalna težina od preostalih rubova, jer je crvena: Vrhovi B i E pripadaju istoj komponenti šuma povezivanje F, koji je, ako se tome doda F rub (b, e), nastaje ciklus. Zatim se doda zeleni rub (b, c), se prenosi crveni rub (c, e), a zatim d, e. Tako, se doda uzastopce rubovi (a, c), (c, d), (a, b), (b, c). Iz nje se sastoji od optimalnog kostura izvornog grafa. Tako se Crascal algoritam radi u ovom slučaju. Primjer pokazuje ovo.

Slika prikazuje grafikon koji se sastoji od dvije komponente povezivanja. Podebljane linije prikazuju rubove optimalnog okvira (zeleno), konstruirane pomoću algoritma Kruskal.

Gornja slika prikazuje izvorni grafikon, a na donjem - kostur minimalne težine, konstruiran za njega uz pomoć algoritma koji se razmatra.

Slijed dodanih rubova: (1,6) - (0,3), (2,6) ili (2,6), (0,3) - bez obzira na (3,4) - (0,1) (1.6) ili (1.6), (0.1) također je indiferentna (5.6).

Kruskal algoritam pronalazi praktičnu primjenu, na primjer, kako bi se optimizirala brtve komunikacije, ceste u novim stambenim zgradama lokaliteta u svakoj zemlji, kao iu drugim slučajevima.