1800-luvun alussa Berliinin geometrin Jacob SteinerHän asetti tehtävän yhdistää kolme kylää niin, että niiden pituus oli lyhin. Myöhemmin hän yleisti tämän ongelman: on löydettävä piste pisteestä, joka on etäisyydellä n muusta pisteestä pienin. 1900-luvulla tätä aihetta jatkettiin. Päätettiin ottaa useita pisteitä ja yhdistää ne siten, että niiden välinen etäisyys oli lyhin. Tämä on kaikki tutkittavan ongelman erityistapaus.
Ahne algoritmit
Kruskalin algoritmi viittaa ahneuteen(niitä kutsutaan myös gradienteiksi). Niiden ydin on suurin hyöty jokaisessa vaiheessa. Ei aina "ahne" algoritmit tarjoavat parhaan ratkaisun ongelmaan. On olemassa teoria, joka osoittaa, että tiettyihin tehtäviin sovellettaessa ne tarjoavat optimaalisen ratkaisun. Tämä on matroidien teoria. Kraskal-algoritmi viittaa tällaisiin ongelmiin.
Pienin luuranko löytyy
Tarkasteltava algoritmi rakentaa optimaalisenkuvaajakehys. Ongelma siinä on seuraava. Suuntaamaton kuvaaja annetaan ilman useita reunoja ja silmukoita, ja reunajoukolle annetaan painofunktio w, joka antaa jokaiselle reunalle e numeron - reunan painon - w (e). Reunajoukon kunkin osajoukon paino määräytyy sen reunojen painojen summan perusteella. Vaaditaan pienimmän kehyksen löytäminen.
kuvaus
Kraskal-algoritmi toimii näin.Ensinnäkin alkuperäisen kuvaajan kaikki reunat on järjestetty nousevassa painojärjestyksessä. Alun perin kehys ei sisällä reunoja, mutta sisältää kaikki kuvaajan kärjet. Algoritmin seuraavan vaiheen jälkeen yksi reuna lisätään kehysten jo rakennettuun osaan, joka on kattava metsä. Sitä ei ole valittu mielivaltaisesti. Kaikkia kuvaajan reunoja, jotka eivät kuulu kehykseen, voidaan kutsua punaisiksi ja vihreiksi. Kunkin punaisen reunan kärjet ovat rakenteilla olevan metsän yhdessä kytketyssä osassa, ja vihreät kärjet ovat eri. Siksi, jos lisäät sinne punaisen reunan, sykli ilmestyy, ja jos vihreä, tämän vaiheen jälkeen saatuun metsään, kytkettyjä komponentteja on yksi vähemmän. Siksi tuloksena olevaan rakenteeseen ei voida lisätä yhtään punaista reunaa, vaan mitä tahansa vihreää reunaa voidaan lisätä metsän saamiseksi. Ja vihreä kylkiluu, jolla on vähän painoa, lisätään. Tuloksena on pienimmän painoinen kehys.
täytäntöönpano
Merkitse nykyinen metsä F.Se jakaa kuvaajan pisteiden joukon kytkettyihin alueisiin (niiden liitosmuodot ovat F, ja ne eivät leikkaudu pareittain). Punaisissa reunoissa molemmat huiput sijaitsevat yhdessä osassa. Osa (x) on funktio, joka jokaiselle kärkipisteelle x palauttaa sen osan nimen, johon x kuuluu. Yhdistä (x, y) on menetelmä, joka rakentaa uuden osion, joka koostuu osien x ja y ja kaikkien muiden osien liitoksesta. Olkoon n graafin reunojen lukumäärä. Kaikki nämä käsitteet sisältyvät Kraskal-algoritmiin. toteutus:
Lajittele kaavion kaikki reunat 1.: n ja n: nnen välillä nousevassa painojärjestyksessä. (ai, bi ovat reunan huiput numerolla i).
i = 1 - n tehdä.
x: = osa (ai).
y: = osa (bi).
Jos x ei ole yhtä suuri kuin y, niin Yhdistä (x, y), lisää reunaan F luku i.
oikeellisuutta
Olkoon T Kruskal-algoritmia käyttäen konstruoidun alkuperäisen kuvaajan kehys ja S on sen mielivaltainen kehys. On tarpeen todistaa, että w (T) ei ylitä w (S).
Olkoon M reunajoukko S, P reunajoukkoT. Jos S ei ole yhtä suuri kuin T, niin siellä on luurankon T reuna, joka ei kuulu S: iin. Kiinnitämme et S.: iin. Muodostamme syklin, kutsumme sitä C. Poistamme C: stä kaikki S.: een kuuluvat reunat. Saamme uuden luurankon, koska siellä on myös reunoja ja siinä on yhtä monta huippua. Sen paino ei ylitä w (S), koska w (et) ei ole suurempi kuin w (es) Kraskal-algoritmin nojalla. Tämä toimenpide (korvaamalla S: n reunat T: n reunoilla) toistetaan, kunnes saamme T. Kunkin seuraavan saadun kehyksen paino ei ole suurempi kuin edellisen paino, mikä tarkoittaa, että w (T) ei ole suurempi kuin w (S).
Kruskal-algoritmin oikeellisuus seuraa myös matroidien Rado-Edmond-lauseesta.
Esimerkkejä Kruskal-algoritmin soveltamisesta
Graafi, jossa on huiput a, b, c, d, e ja reunat (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Kylkiluiden painot on esitetty taulukossa ja kuvassa. Aluksi rakenteilla oleva metsä F sisältää kaikki kuvaajan huiput eikä sisällä reunoja. Kraskal-algoritmi lisää ensin reunan (a, e), koska sillä on pienin paino ja huiput a ja e ovat metsän F eri komponenteissa (reuna (a, e) on vihreä), sitten reuna (c, d), siksi Koska tällä reunalla on pienin graafin reunojen paino, jotka eivät kuulu F: hen, ja se on vihreä, niin reuna (a, b) lisätään samoista syistä. Mutta reuna (b, e) ohitetaan, vaikka sillä on pienin jäljellä olevien reunojen paino, koska se on punainen: kärjet b ja e kuuluvat samaan yhdistettyyn metsän F komponenttiin, ts. Jos lisäämme reunan (b, e) F: iin, niin sykli. Sitten lisätään vihreä reuna (b, c), ohitetaan punainen reuna (c, e) ja sitten d, e. Siten reunat (a, e), (c, d), (a, b), (b, c) lisätään peräkkäin. Alkuperäisen kuvaajan optimaalinen kehys koostuu niheristä. Näin algoritmi toimii tässä tapauksessa. Kruskal. Esimerkki esitetään.
Kuvassa on graafi, joka koostuu kahdesta kytketystä komponentista. Lihavoidut viivat osoittavat Kraskal-algoritmin avulla rakennetun optimaalisen kehyksen (vihreä) reunat.
Ylempi kuva esittää alkuperäisen kaavion ja alempi kuvaa pienimmän luurungon, joka on rakennettu sille käyttämällä kyseistä algoritmia.
Lisättyjen reunojen sekvenssi: (1,6); (0,3), (2,6) tai (2,6), (0,3) - ei ole väliä; (3,4); (0,1), (1,6) tai (1,6), (0,1) on myös välinpitämätön (5,6).
Kruskalin algoritmi löytää käytännön sovelluksia esimerkiksi tietoliikenteen, teiden asentamisen optimointiin jokaisen maan asutuskeskusten uusilla asuinalueilla ja myös muissa tapauksissa.
