Minimaalinen kantava puu (Minimum Spanning Tree, MST) — määritelmä ja esimerkit

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.