Kruskalov algoritem - konstrukcija optimalnega okostja

V začetku 19. stoletja je geometer iz Berlina Jacob Steiner postavil nalogo, kako povezati tri vasi, tako da je njihova dolžina najkrajša. Nato je generaliziral ta problem: potrebno je najti točko na ravnini, tako da je razdalja od nje do n drugih točk najmanjša. V 20. stoletju se je nadaljevalo delo na tej temi. Odločeno je bilo, da vzamete več točk in jih povežete tako, da je razdalja med njimi najkrajša. To je vsekakor poseben primer problema, ki se preučuje.

Pohlepni algoritmi

Kruskalov algoritem se nanaša na "pohlepne" algoritme (ti se imenujejo tudi gradientni algoritmi). Bistvo teh - največja zmaga na vsakem koraku. Ne vedno "pohlepni" algoritmi dajejo najboljšo rešitev za nalogo. Obstaja teorija, ki kaže, da če se uporabljajo za posebne probleme, zagotavljajo optimalno rešitev. To je teorija matroidov. Kruskalov algoritem se nanaša na takšne probleme.

Iskanje okostja najmanjše teže

Obravnavani algoritem konstruira optimalni skelet grafikona. Težava o tem je naslednja. Dan neusmerjeno graf brez vzporednih robov in zank, ter niz robov je podan funkcijo Masa, ki ustrezno število za vsako robno e - mas rebro - w (e). Masa vsake podskupine množice robov določi vsota uteži njegovih robov. Zahtevati je najti skelet najmanjše teže.

Opis

Algoritem Kruskal deluje takole. Prvič, vsi robovi prvotnega grafa so razporejeni glede na povečanje uteži. Sprva okvir ne vsebuje nobenih robov, temveč vključuje vse tocke grafikona. Po naslednjem koraku algoritma se že zgrajenemu delu ogrodja, ki je vmesni gozd, doda en rob. To ni izbrano samovoljno. Vsi robovi grafikona, ki ne spadajo v okostnjak, lahko imenujemo rdeče in zelene barve. Vrvice vsakega rdečega rebra so v eni komponenti povezanosti gozda, ki se gradi, zelene zelene pa so v različnih sestavnih delih. Če dodate rdeči rob, se prikaže cikel in če je zelena - v nastalem gozdičnem koraku bo komponenta povezljivosti manj za eno. Tako ni mogoče dodati nobenega rdečega roba do nastale konstrukcije, vendar je mogoče dobiti zeleni rob za pridobitev gozda. In dodamo zeleno rebro z najmanjšo težo. Posledično dobimo skelet najmanjše teže.

Izvajanje

Označimo trenutni gozd F. Deli niz vozlišč grafikona v povezane domene (njihovi sindikati F in se ne parče v seku). Rdeči robovi imajo v enem delu obe vrvi. Del (x) je funkcija, ki vrne ime dela, na katerega x pripada za vsako tocko x. Unite (x, y) je postopek, ki gradi novo particijo, sestavljeno iz združitve delov x in y ter vseh drugih delov. Naj bo n število robov grafov. Vsi ti koncepti so vključeni v Kruskalov algoritem. Izvajanje:

1. Razporedite vse robove grafa od 1. do n-ti naraščajoče uteži. (ai, bi so tocke roba z indeksom i).

2. za i = 1 do n.

3. x: = del (ai).

4. y: = del (bi).

5. Če x ni enak y, potem unite (x, y), vključite rob s številom i v F.

Pravilnost

Naj bo T okostje prvotnega grafa, zgrajenega z uporabo Kruskalovega algoritma, in naj bo S njegov poljuben ogrod. Dokazati moramo, da w (T) ne presega w (S).

Naj M - množica plavuti S, P - množico plavuti T. Če S ni enako T, potem je okvir rebro et T, ki ne pripadajo S. S. et mejijo cikel, ki se imenuje C, C odstrani iz enega od robov es, ki spada S. Dobi se nov okvir, saj je v njem tudi toliko robov in tock. Njegova teža ne presega w (S), saj w (et) ni večji od w (es) s Kruskalovim algoritmom. Ta operacija (nadomestnih rebra tS o mnenju) ponovi, dokler prejemajo T. maso vsakega naslednjega prejeto okvir ni večja od prejšnjega teže, kar pomeni, da w (T) ni večja od w (I).

Tudi pravilnost Kruskalovega algoritma izhaja iz izreka Rado-Edmunda na matroidih.

Primeri uporabe Kruskalovega algoritma

Dan graf z vozlišči a, b, c, d, e in rebri (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Uteži robov so prikazane v tabeli in na sliki. Na začetku gradnja gozda F vsebuje vse tocke grafa in ne vsebuje enega roba. Algoritem Kruskal najprej dodati rebro (a, e), saj je imela težo najnižja, in tocke A in E sta v različnih komponent povezljivost lesa F (rebro (a, e) je zelene barve), nato pa je rebro (c, d), saj da ima ta rob najmanjšo težo od robov grafa, ki ne spada v F, in je zelena, nato pa iz istih razlogov dodamo rob (a, b). Vendar pa je rob (b, e) opravili, čeprav on in minimalna teža preostalih robov, ker je rdeča: oglišči b in e pripadajo isti komponenti gozd povezljivost F, ki je, če temu dodamo F rob (b, e), ki je nastala cikel. Nato dodamo zeleni rob (b, c), rdeči rob (c, e) preskočimo in nato d, e. Tako se v zaporedju dodajo robovi (a, e), (c, d), (a, b), (b, c). Iz njega je optimalen skelet prvotnega grafa. Tako deluje v tem primeru algoritem Crascal. Primer to kaže.

Slika prikazuje graf, sestavljen iz dveh povezovalnih komponent. Krepke črte prikazujejo robove optimalnega okvira (zelenega), zgrajene z uporabo Kruskalovega algoritma.

Zgornja slika prikazuje prvotni graf, na spodnjem pa skelet minimalne teže, zgrajen za to s pomočjo obravnavanega algoritma.

Zaporedje dodanih reber (1,6) - (0,3), (2,6) ali (2,6), (0,3) - ne has- (3.4) - (0.1) (1.6) ali (1.6), (0.1) je tudi indiferenten (5.6).

Kruskalov algoritem najde praktično uporabo, na primer za optimizacijo komunikacijskih blazinic, cest v novih soseskah v krajih vsake države, pa tudi v drugih primerih.