Minimaalinen kantava puu (Minimum Spanning Tree, MST) — määritelmä ja esimerkit
Selkeä opas minimaaliseen kantavaan puuhun (MST): määritelmä, algoritmit ja käytännön esimerkit graafiteoriassa ja verkkooptimoinnissa.
Useita graafiteorian ongelmia kutsutaan nimellä Minimum spanning tree (suomeksi yleensä minimaalinen kantava puu tai lyhyemmin MST). Graafiteoriassa puu on tapa yhdistää kaikki kärkipisteet toisiinsa siten, että mistä tahansa kärkipisteestä on täsmälleen yksi polku mihin tahansa toiseen kärkipisteeseen. Esimerkiksi 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ä — tällainen valinta muodostaa puun.
Määritelmä
Olkoon G = (V, E) yhdistetty, painotettu, ei-suunnattu graafi, jossa V on kärkipisteiden joukko ja E reunojen joukko. Reunalle e ∈ E on liitetty paino w(e) (esimerkiksi kustannus, etäisyys tai aika). Spanning tree (kantava puu) on alipuuna puu, joka sisältää kaikki kärkipisteet V ja tarkalleen |V| − 1 reunaa. Minimaalinen kantava puu (MST) on kantava puu, jonka reunapainojen summa ∑ w(e) on pienin mahdollinen kaikista kantavista puista.
Perusominaisuudet ja huomiot
- Jos graafi on epäyhdistetty, ei ole yhtenäistä kantavaa puuta; tällöin puhutaan minimaalisesta kantavasta metsästä (minimum spanning forest), joka on MST jokaiselle komponentille erikseen.
- MST:n reunamäärä on aina |V| − 1, missä |V| on kärkipisteiden lukumäärä.
- Jos kaikilla reunoilla on eri painot (ei kahta reunaa samalla painolla), MST on yksikäsitteinen (ainutlaatuinen). Jos painoja on yhtä paljon, graafilla voi olla useampi kuin yksi MST.
- Negatiiviset reunapainot eivät estä MST:n olemassaoloa — algoritmit toimivat myös silloin, kunhan graafi on ei-suunnattu.
- MST määritellään vain ei-suunnatuille graafeille; suunnatuissa graafeissa on muita vastaavia käsitteitä (esim. arboresenssi).
Tärkeitä ominaisuuksia (leikkaus- ja sykkelauseet)
- Leikkausominaisuus (cut property): Jos graafi on jaettu kahteen osaan (leikkaus), pienimmän leikkauksen reunapainon omaava reuna kuuluu johonkin MST:hen.
- Sykeeliö (cycle property): Jos reunassa kuuluu sykkeeseen (cycle) eikä se ole suurimman painon reunana siinä sykliessä, se voi kuulua MST:hen; toisaalta suurin reuna syklissä ei kuulu mihinkään MST:hen.
Algoritmit
Useita tehokkaita algoritmeja laskee MST:n. Yleisimmät ovat:
- Kruskalin algoritmi: Järjestä reunat nousevaan painoarvoon ja lisää reunat yksi kerrallaan MST:hen, ellei lisäys muodosta sykliä. Yleensä toteutetaan union-find-rakenteella (disjoint set union, DSU). Aikavaativuus O(E log E) eli käytännössä O(E log V).
- Primin algoritmi: Aloita mistä tahansa kärjestä ja laajenna puuta lisäämällä aina pienipainoinen reuna, joka yhdistää jo rakennetun osan ja siihen kuulumattoman kärjen. Toteutetaan prioriteettijonolla (binary heap tai Fibonacci-heap). Aikavaativuus binary heapillä O(E log V); Fibonacci-heapillä O(E + V log V).
- Borůvkan algoritmi: Toistaa komponenttien yhdistämistä etsimällä kullekin komponentille edullisin reuna. Hyödyllinen rinnakkaistoteutuksissa ja historiallisesti tärkeä.
Yksinkertainen esimerkki
Kuvitellaan neljä kaupunkia A, B, C ja D ja seuraavat tievälit painoineen: AB=1, AC=3, BC=2, BD=4, CD=5. Kruskalin menetelmällä järjestämme reunat: AB(1), BC(2), AC(3), BD(4), CD(5).
- Valitaan AB (1). Ei sykliä → lisätään.
- Valitaan BC (2). Ei sykliä → lisätään. Nyt A, B, C ovat yhdistettyjä.
- Seuraavaksi AC(3) muodostaisi syklin A–B–C → ohitetaan.
- Valitaan BD(4). Ei sykliä → lisätään. Nyt kaikki neljä kaupunkia yhdistetty |V| − 1 = 3 reunalla.
MST:n reunat ovat AB, BC ja BD, ja niiden yhteispaino on 1 + 2 + 4 = 7. Saattaa löytyä myös toinen samanpainoinen MST, jos joillain reunoilla olisi sama paino.
Sovelluksia
- Verkkojen suunnittelu: tele- ja sähköverkot, jossa pyritään minimikustannuksiin yhdistäen solmut.
- Tien- ja putkiverkostot, missä halutaan pienin rakennuskustannus, mutta kaikki kohteet yhdistettynä.
- Klusteroilu ja kuvankäsittely (esimerkiksi segmentointi käyttämällä MST-pohjaisia menetelmiä).
- Algoritmiset apuvälineet muihin ongelmiin, kuten likimääräinen ratkaisu Travelling Salesman Problem -ongelmaan.
Lisätiedot ja huomautuksia
- MST-algoritmit ovat käytännössä hyvin tehokkaita ja toimivat suurissakin verkoissa.
- Jos kiinnostaa toteutus, Kruskalin kanssa kannattaa tutustua union-find-rakenteeseen; Primin kanssa prioriteettijonon valinta vaikuttaa suorituskykyyn.
- Kun reunapainot ovat reaalilukuja ja monia reunoja voi olla yhtä painavia, kannattaa huomioida, että useita eri MST-ratkaisuja voi olla oikeita — usein riittää yksi.


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 TTä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.
Etsiä