Minimaal opspannende boom
Een aantal problemen uit de grafiektheorie worden Minimum Spanningsboom genoemd. In de grafiektheorie is een boom een manier om alle hoekpunten met elkaar te verbinden, zodat er precies één pad is van een bepaald hoekpunt naar een ander hoekpunt van de boom. Als de grafiek een aantal steden weergeeft die door wegen met elkaar verbonden zijn, dan zou men een aantal wegen kunnen selecteren, zodat elke stad vanuit elke andere stad bereikbaar is, maar dat er niet meer dan één manier is om van de ene stad naar de andere te reizen.
Een grafiek kan meer dan één overspannende boom hebben, net zoals er meer dan één manier kan zijn om de wegen tussen de steden te selecteren.
Meestal worden grafieken gewogen; elke verbinding tussen twee steden heeft een gewicht: het kan iets kosten om op een bepaalde weg te reizen, of de ene verbinding kan langer zijn dan de andere, dit betekent dat het meer tijd kost om op die verbinding te reizen. In de taal van de grafiektheorie worden de verbindingen randen genoemd.
Een minimale spanwijdte van een boom is een boom. Het onderscheidt zich van andere bomen doordat het totaal van de aan de randen bevestigde gewichten tot een minimum wordt beperkt. Afhankelijk van hoe de grafiek eruit ziet, kan er meer dan één minimumspannende boom zijn. In een grafiek waar alle randen hetzelfde gewicht hebben, is elke boom een minimale spanningsboom. Als alle randen verschillende gewichten hebben (dat wil zeggen: er zijn geen twee randen met hetzelfde gewicht), is er precies één minimale spanningsboom.
De minimale overspannende boom van een vlakke grafiek. Elke rand is gelabeld met zijn gewicht, dat hier ruwweg in verhouding staat tot zijn lengte.
Het vinden van de minimale spanningsboom
Een eerste poging
Het kan heel eenvoudig zijn om een algoritme te maken dat een minimale spanningsboom zal ontdekken:
functie MST(G,W) : T = { } terwijl T geen spanningsboom vormt: zoek de minimum gewogen rand in E die veilig is voor T T = T-verbinding {(u,v) } retour TIn dit geval betekent "veilig" dat het opnemen van de rand geen cyclus vormt in de grafiek. Een cyclus betekent beginnen bij een hoekpunt, naar een aantal andere hoekpunten gaan en weer bij het beginpunt eindigen zonder twee keer dezelfde rand te gebruiken.
Geschiedenis
De Tsjechische wetenschapper Otakar Borůvka ontwikkelde in 1926 het eerste bekende algoritme voor het vinden van een minimale spanningsboom. Hij wilde het probleem van het vinden van een efficiënte dekking van Moravië met elektriciteit oplossen. Tegenwoordig staat dit algoritme bekend als het algoritme van Borůvka. Twee andere algoritmen worden tegenwoordig veel gebruikt. Een ervan werd in 1930 door Vojtěch Jarník ontwikkeld en in 1957 door Robert Clay Prim in de praktijk gebracht. Edsger Wybe Dijkstra herontdekte het in 1959 en noemde het Prim's algoritme. Het andere algoritme heet het algoritme van Kruskal, en werd in 1956 door Joseph Kruskal gepulst. Alle drie de algoritmen zijn hebzuchtig, en lopen in polynomiale tijd.
Het snelste minimumspannings-boomalgoritme tot nu toe is ontwikkeld door Bernard Chazelle. Het algoritme is gebaseerd op de zachte hoop, een geschatte wachtrij voor prioriteiten. De looptijd is O(m α(m,n)), waarbij m het aantal randen is, n het aantal hoekpunten en α de klassieke functionele inverse van de Ackermann-functie. De functie α groeit extreem langzaam, zodat hij voor alle praktische doeleinden als een constante niet groter dan 4 kan worden beschouwd; het algoritme van Chazelle neemt dus zeer dicht bij de lineaire tijd.
Wat is het snelst mogelijke algoritme voor dit probleem? Dat is een van de oudste open vragen in de informatica. Er is duidelijk een lineaire ondergrens, want we moeten op zijn minst alle gewichten onderzoeken. Als de randgewichten gehele getallen zijn met een begrensde bitlengte, dan zijn deterministische algoritmen bekend met een lineaire looptijd. Voor algemene gewichten zijn er gerandomiseerde algoritmen waarvan de verwachte looptijd lineair is.
Het probleem kan ook op een gedistribueerde manier worden benaderd. Als elk knooppunt als een computer wordt beschouwd en het knooppunt weet iets anders dan zijn eigen verbonden links, kan men nog steeds de gedistribueerde minimale spanningsboom berekenen.
Vragen en antwoorden
V: Wat is een minimum overspanningsboom in de grafentheorie?
A: Een minimale overspannen boom is een boom die in de grafentheorie de totale gewichten aan de randen minimaliseert.
V: Wat is een boom in de grafentheorie?
A: Een boom is een manier om alle hoekpunten met elkaar te verbinden in de grafentheorie, zodat er slechts één pad is van een willekeurig hoekpunt naar een ander hoekpunt van de boom.
V: Wat is het doel van het selecteren van wegen in een grafentheoriescenario dat steden voorstelt?
A: Het doel van het kiezen van wegen in een grafentheoriescenario dat steden voorstelt, is om elke stad vanuit elke andere stad te kunnen bereiken, maar met niet meer dan één mogelijke manier om van de ene stad naar de andere te reizen.
V: Kan een grafiek meer dan één overspannen boom hebben?
A: Ja, een grafiek kan meer dan één overspannen boom hebben.
V: Wat is het verschil tussen een minimale overspannen boom en andere bomen in de grafentheorie?
A: Een minimale overspanningsboom minimaliseert de totale gewichten van de randen, terwijl andere bomen deze eigenschap niet hebben.
V: Wat zijn randen in de grafentheorie?
A: Randen zijn de verbindingen tussen twee vertices in de grafentheorie.
V: Kan er meer dan één minimale overspanningsboom in een grafiek zijn met verschillende gewogen randen?
A: Ja, afhankelijk van hoe de grafiek eruitziet, kan er meer dan één minimale overspanningsboom zijn.
