Minimum spanning tree
En række problemer fra grafteori kaldes Minimum spanning tree. I grafteori er et træ en måde at forbinde alle toppene på, således at der er præcis én vej fra et hvilket som helst toppunkt til et hvilket som helst andet toppunkt i træet. Hvis grafen repræsenterer en række byer, der er forbundet med veje, kan man vælge et antal veje, så hver by kan nås fra hver anden by, men så der ikke er mere end én vej fra den ene by til den anden.
En graf kan have mere end ét spændetræ, ligesom der kan være mere end én måde at vælge vejene mellem byerne på.
Oftest er graferne vægtede; hver forbindelse mellem to byer har en vægt: Det kan koste noget at rejse ad en given vej, eller en forbindelse kan være længere end den anden, hvilket betyder, at det tager længere tid at rejse ad den pågældende forbindelse. I grafteoriens sprog kaldes forbindelserne for kanter.
Et minimum spanning tree er et træ. Det adskiller sig fra andre træer ved at minimere summen af de vægte, der er knyttet til kanterne. Afhængigt af, hvordan grafen ser ud, kan der være mere end ét minimumspaningstræ. I en graf, hvor alle kanter har den samme vægt, er alle træer et minimum spanning tree. Hvis alle kanter har forskellige vægte (dvs. at der ikke er to kanter med samme vægt), er der præcis ét minimalt overspændende træ.
Det mindste træ i en planar graf. Hver kant er mærket med sin vægt, som her er nogenlunde proportional med dens længde.
Findelse af det mindst mulige træ
Et første forsøg
Det kan være meget enkelt at lave en algoritme, der kan finde et minimum spanning tree:
funktion MST(G,W): T = {} mens T ikke danner et spændetræ: Find den mindste vægtede kant i E, der er sikker for T T T = T union {(u,v)} return TI dette tilfælde betyder "sikker", at hvis kanten medtages, danner den ikke en cyklus i grafen. En cyklus betyder, at man starter ved et toppunkt, rejser til et antal andre toppunkter og ender ved udgangspunktet igen uden at bruge den samme kant to gange.
Historie
Den tjekkiske videnskabsmand Otakar Borůvka udviklede den første kendte algoritme til at finde et minimum spanning tree i 1926. Han ønskede at løse problemet med at finde en effektiv dækning af Mähren med elektricitet. I dag er denne algoritme kendt som Borůvka's algoritme. To andre algoritmer er almindeligt anvendte i dag. Den ene af dem blev udviklet af Vojtěch Jarník i 1930 og anvendt i praksis af Robert Clay Prim i 1957. Edsger Wybe Dijkstra genopdagede den i 1959 og kaldte den Prim's algoritme. Den anden algoritme kaldes Kruskals algoritme og blev udviklet af Joseph Kruskal i 1956. Alle tre algoritmer er greedy-algoritmer og kører på polynomial tid.
Den hurtigste algoritme til dato for minimum spanning tree blev udviklet af Bernard Chazelle. Algoritmen er baseret på soft heap, en tilnærmelsesvis prioriteret kø. Dens løbetid er O(m α(m,n))), hvor m er antallet af kanter, n er antallet af hjørner, og α er den klassiske funktionelle omvendte funktion af Ackermann-funktionen. Funktionen α vokser ekstremt langsomt, således at den til alle praktiske formål kan betragtes som en konstant, der ikke er større end 4; Chazelles algoritme tager således meget tæt på lineær tid.
Hvad er den hurtigst mulige algoritme til dette problem? Det er et af de ældste åbne spørgsmål inden for datalogi. Der findes helt klart en lineær nedre grænse, da vi i det mindste skal undersøge alle vægte. Hvis kantvægtene er hele tal med en begrænset bitlængde, er der deterministiske algoritmer kendt med lineær løbetid. For generelle vægte findes der randomiserede algoritmer, hvis forventede løbetid er lineær.
Problemet kan også gribes an på en distribueret måde. Hvis hver enkelt knude betragtes som en computer, og ingen knude kender andet end sine egne forbundne forbindelser, kan man stadig beregne det distribuerede minimum spanning tree.
Spørgsmål og svar
Q: Hvad er et minimum spanning tree i grafteori?
A: Et minimum spanning tree er et træ, der minimerer de samlede vægte, der er knyttet til kanterne i grafteori.
Q: Hvad er et træ i grafteori?
A: Et træ er en måde at forbinde alle toppunkter på i grafteori, så der kun er én vej fra et hvilket som helst toppunkt til et hvilket som helst andet toppunkt i træet.
Q: Hvad er formålet med at vælge veje i et grafteoretisk scenarie, der repræsenterer byer?
A: Formålet med at vælge veje i et grafteoretisk scenarie, der repræsenterer byer, er at gøre det muligt at nå hver by fra alle andre byer, men uden at der er mere end én mulig måde at rejse fra en by til en anden på.
Q: Kan en graf have mere end ét spændetræ?
A: Ja, en graf kan have mere end ét træ.
Q: Hvad er forskellen mellem et minimum spanning tree og andre træer i grafteori?
A: Et minimum spanning tree minimerer de samlede vægte, der er knyttet til kanterne, mens andre træer ikke har denne funktion.
Q: Hvad er kanter i grafteori?
A: Kanter er forbindelserne mellem to hjørner i grafteori.
Q: Kan der være mere end ét minimum spanning tree i en graf med forskelligt vægtede kanter?
A: Ja, afhængigt af hvordan grafen ser ud, kan der være mere end ét minimum spanning tree.
