Minimale opspannende bomen

In 1926 kreeg Otakar Borůvka de opdracht om het elektriciteitsnet van het zuiden van Moravië zo goedkoop mogelijk te plannen. Zijn vraag, hoe je elke plaats verbindt met zo weinig mogelijk totale lengte aan leiding, is het probleem van de minimale opspannende boom, en het heeft enkele van de eenvoudigste en elegantste antwoorden in de hele informatica.

Een graaf waarvan de kanten lengtes hebben, met de korte kanten van een groeiende boom gemarkeerd, een overgeslagen kant die een cyclus zou sluiten rood gestreept, en daaronder de lijst met kanten die nog geprobeerd moeten worden
Een graaf waarvan de kanten lengtes hebben, met de korte kanten van een groeiende boom gemarkeerd, een overgeslagen kant die een cyclus zou sluiten rood gestreept, en daaronder de lijst met kanten die nog geprobeerd moeten worden

Het probleem

Neem een samenhangende graaf waarvan de kanten lengtes, of kosten, hebben. Een opspannende boom is een verzameling kanten die alle knopen verbindt en geen cyclus bevat; met n knopen heeft die altijd precies n − 1 kanten, omdat elke kant één knoop meer verbindt. Van alle opspannende bomen heeft een minimale opspannende boom de kleinste totale lengte. Een graaf kan enorm veel opspannende bomen hebben, maar je hoeft ze niet allemaal te proberen.

Waarom gretig werkt

Verdeel de knopen op welke manier ook in twee groepen. De kortste kant tussen de groepen hoort altijd bij een minimale opspannende boom: als een boom in plaats daarvan een langere kant tussen de groepen gebruikte, zou je die kunnen ruilen voor de kortere en dezelfde knopen goedkoper verbinden. Dit is de snede-eigenschap. De keerzijde is de cyclus-eigenschap: de langste kant op een cyclus is nooit nodig. Beide algoritmen hieronder passen deze regels gewoon steeds toe.

Een voorbeeld

Neem de kanten A–B met lengte 1, B–C 2, A–C 3, C–D 4 en B–D 5. Het algoritme van Kruskal neemt A–B, dan B–C, slaat dan A–C over, omdat A en C al verbonden zijn en die kant een cyclus zou sluiten, en neemt dan C–D. De boom heeft drie kanten voor vier knopen, dus hij is klaar, met totale lengte 7, en B–D wordt niet eens bekeken. Het algoritme van Prim vanaf A voegt eerst B toe via A–B; de kant B–C (2) van B wint van A–C (3) als weg naar C, dus C sluit aan via B–C; de kant C–D (4) van C wint van B–D (5), dus D sluit aan via C–D. Dezelfde boom, dezelfde 7.

Kruskal, Prim en Borůvka

Het algoritme van Kruskal, in 1956 gepubliceerd door Joseph Kruskal, sorteert de kanten en gebruikt een union-find-structuur om kanten binnen één stuk over te slaan, dus groeit het werk met E log E. Het algoritme van Prim werd voor het eerst beschreven door Vojtěch Jarník in 1930 en herontdekt door Robert Prim in 1957 en Edsger Dijkstra in 1959; met een binaire heap groeit het werk met E log V, en met een eenvoudige array met V², wat goed is voor dichte grafen. Het algoritme van Borůvka uit 1926 laat elk stuk tegelijk zijn kortste uitgaande kant pakken, wat goed past bij parallelle computers.

Otakar Borůvka in 1981. In 1926 werd hem gevraagd het elektriciteitsnet van Zuid-Moravië zo goedkoop mogelijk te plannen, en hij gaf het eerste algoritme voor een minimale opspannende boom.
Otakar Borůvka in 1981. In 1926 werd hem gevraagd het elektriciteitsnet van Zuid-Moravië zo goedkoop mogelijk te plannen, en hij gaf het eerste algoritme voor een minimale opspannende boom.

Toepassingen

Met minimale opspannende bomen ontwerp je goedkope netwerken van kabels, leidingen en wegen. Ze delen gegevens in clusters in: haal de langste kanten uit de boom, en de stukken die overblijven zijn de clusters. Ze geven een snelle route voor het handelsreizigersprobleem die hoogstens twee keer zo lang is als de beste, als de afstanden aan de driehoeksongelijkheid voldoen. En het algoritme van Kruskal of Prim op een rooster met willekeurige kantlengtes is een klassieke manier om een doolhof te maken.

Probeer het zelf

Open de app, kies Kruskal of Prim en druk op Stap. Bij Kruskal staan de kanten die nog geprobeerd moeten worden onder de graaf, van kort naar lang; kanten die een cyclus zouden sluiten, zijn rood gestreept getekend. Bij Prim staan daar de knopen die wachten om aan te sluiten, met de lengte van hun beste kant, die gestreept is getekend. Laat beide op dezelfde graaf lopen en vergelijk: de volgorde verschilt, maar de totale lengte is altijd gelijk.

Veelgestelde vragen

Hoeveel kanten heeft een opspannende boom?

Precies één minder dan het aantal knopen. Met minder kanten kun je niet elke knoop verbinden, en één kant meer maakt altijd een cyclus.

Wat is sneller, Kruskal of Prim?

Het algoritme van Kruskal, dat de kanten sorteert, is meestal eenvoudiger en snel op ijle grafen met weinig kanten. Het algoritme van Prim met een heap doet het goed op dichte grafen, en met een gewone array heeft het ongeveer V² stappen nodig, hoeveel kanten er ook zijn.

Wat is union-find?

Een datastructuur die bijhoudt welke knopen in hetzelfde stuk zitten. Ze beantwoordt “zijn deze twee verbonden?” en voegt twee stukken bijna meteen samen, precies wat het algoritme van Kruskal voor elke kant nodig heeft.

Werkt een minimale opspannende boom voor gerichte grafen?

Niet zomaar. Voor grafen met eenrichtingskanten is het overeenkomstige probleem de minimale opspannende arborescentie, opgelost door het algoritme van Chu–Liu/Edmonds.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Bouw een minimale opspannende boom