Pienin jännittävä puu

Useita graafiteorian ongelmia kutsutaan nimellä Minimum spanning tree. Graafiteoriassa puu on tapa yhdistää kaikki kärkipisteet toisiinsa siten, että mistä tahansa kärkipisteestä on täsmälleen yksi polku mihin tahansa puun toiseen kärkipisteeseen. Jos graafi edustaa useita kaupunkeja, jotka on yhdistetty toisiinsa teillä, voidaan valita sellainen määrä teitä, että jokaiseen kaupunkiin pääsee jokaisesta toisesta kaupungista, mutta että kaupungista toiseen pääsee vain yhtä reittiä.

Graafilla voi olla useampi kuin yksi jänneväli, aivan kuten voi olla useampi kuin yksi tapa valita kaupunkien väliset tiet.

Useimmiten kuvaajat ovat painotettuja; jokaisella kahden kaupungin välisellä yhteydellä on painoarvo: tietyn tien kulkeminen saattaa maksaa jotakin, tai yksi yhteys voi olla pidempi kuin toinen, mikä tarkoittaa, että kyseisellä yhteydellä matkustamiseen kuluu enemmän aikaa. Graafiteorian kielellä yhteyksiä kutsutaan reunoiksi.

Pienin jännevä puu on puu. Se eroaa muista puista siinä, että se minimoi reunoihin liitettyjen painojen yhteismäärän. Riippuen siitä, miltä graafi näyttää, minimitilannepuuta voi olla useampi kuin yksi. Graafissa, jossa kaikilla reunoilla on sama paino, jokainen puu on minimitilannepuu. Jos kaikilla reunoilla on eri painot (eli ei ole kahta reunaa, joilla on sama paino), on olemassa täsmälleen yksi minimaalinen jännevä puu.

Tasomaisen graafin pienin jännevä puu. Jokainen reuna on merkitty painollaan, joka tässä tapauksessa on suunnilleen verrannollinen sen pituuteen.

Pienimmän jännityspuun löytäminen

Ensimmäinen yritys

Voi olla hyvin yksinkertaista tehdä algoritmi, joka löytää pienimmän jännityspuun:

funktio MST(G,W): T = {} kun T ei muodosta jännevälirakennetta: etsi pienin painotettu reuna E:ssä, joka on turvallinen T:lle T = T union {(u,v)} return T

Tässä tapauksessa "turvallinen" tarkoittaa, että reunan sisällyttäminen ei muodosta sykliä kuvaajaan. Sykli tarkoittaa sitä, että aloitetaan jostakin pisteestä, kuljetaan useisiin muihin pisteisiin ja päädytään taas lähtöpisteeseen ilman, että samaa reunaa käytetään kahdesti.

Historia

Tšekkiläinen tiedemies Otakar Borůvka kehitti ensimmäisen tunnetun algoritmin pienimmän jännityspuun löytämiseksi vuonna 1926. Hän halusi ratkaista ongelman, joka koski Mährin tehokkaan sähköpeiton löytämistä. Nykyään tämä algoritmi tunnetaan nimellä Borůvkan algoritmi. Nykyään käytetään yleisesti kahta muuta algoritmia. Toisen niistä kehitti Vojtěch Jarník vuonna 1930, ja Robert Clay Prim otti sen käyttöön vuonna 1957. Edsger Wybe Dijkstra löysi sen uudelleen vuonna 1959 ja kutsui sitä Primin algoritmiksi. Toisen algoritmin nimi on Kruskalin algoritmi, ja sen kehitti Joseph Kruskal vuonna 1956. Kaikki kolme algoritmia ovat ahneita ja toimivat polynomiajassa.

Bernard Chazelle on kehittänyt tähän mennessä nopeimman minimihajontapuualgoritmin. Algoritmi perustuu pehmeään kasaan, joka on likimääräinen prioriteettijono. Sen suoritusaika on O(m α(m,n)), missä m on reunojen lukumäärä, n on kärkien lukumäärä ja α on Ackermannin funktion klassinen käänteisfunktio. Funktio α kasvaa erittäin hitaasti, joten käytännössä sitä voidaan pitää vakiona, jonka arvo on enintään 4. Chazellen algoritmi kestää siis hyvin lähellä lineaarista aikaa.

Mikä on nopein mahdollinen algoritmi tähän ongelmaan? Tämä on yksi tietojenkäsittelytieteen vanhimmista avoimista kysymyksistä. On selvästi olemassa lineaarinen alaraja, koska meidän on ainakin tutkittava kaikki painot. Jos reunapainot ovat kokonaislukuja, joiden bittien pituus on rajoitettu, tunnetaan deterministisiä algoritmeja, joiden suoritusaika on lineaarinen. Yleisille painoille on olemassa satunnaistettuja algoritmeja, joiden odotettu suoritusaika on lineaarinen.

Ongelmaa voidaan lähestyä myös hajautetusti. Jos jokaista solmua pidetään tietokoneena, eikä yksikään solmu tiedä muuta kuin omat linkkinsä, voidaan silti laskea hajautettu minimihaaroituspuu.

Kysymyksiä ja vastauksia

Kysymys: Mikä on minimaalinen jännityspuu graafiteoriassa?

A: Minimaalinen jännevä puu on graafiteoriassa puu, joka minimoi reunoihin liitettyjen kokonaispainojen kokonaismäärän.

K: Mikä on puu graafiteoriassa?

A: Puu on tapa yhdistää kaikki kärjet toisiinsa graafiteoriassa siten, että mistä tahansa kärjestä on vain yksi polku mihin tahansa puun toiseen kärkeen.

K: Mikä on teiden valinnan tarkoitus kaupunkeja esittävässä graafiteorian skenaariossa?

V: Kaupunkeja esittävässä graafiteoriaskenaariossa teiden valinnan tarkoituksena on mahdollistaa, että jokaiseen kaupunkiin pääsee jokaisesta toisesta kaupungista, mutta että kaupungista toiseen voi matkustaa vain yhtä reittiä.

Kysymys: Voiko graafilla olla useampi kuin yksi jänneväyläpuu?

V: Kyllä, graafilla voi olla useampi kuin yksi jänneväyläpuu.

Kysymys: Mitä eroa on minimitilannepuun ja muiden graafiteorian puiden välillä?

V: Minimitilan kattava puu minimoi reunojen kokonaispainot, kun taas muilla puilla ei ole tätä ominaisuutta.

K: Mitä ovat särmät graafiteoriassa?

V: Särmät ovat kahden kärkipisteen välisiä yhteyksiä graafiteoriassa.

Kysymys: Voiko graafissa olla useampi kuin yksi minimitilanvarauspuu, jonka reunojen painot ovat erilaiset?

V: Kyllä, riippuen siitä, miltä graafi näyttää, voi olla useampi kuin yksi minimitilanvarauspuu.