Baum mit minimaler Spannweite
Eine Reihe von Problemen aus der Graphentheorie werden Minimum spanning tree genannt. In der Graphentheorie ist ein Baum eine Möglichkeit, alle Scheitelpunkte miteinander zu verbinden, so dass es genau einen Pfad von einem beliebigen Scheitelpunkt zu jedem anderen Scheitelpunkt des Baums gibt. Wenn der Graph eine Anzahl von Städten darstellt, die durch Straßen miteinander verbunden sind, könnte man eine Anzahl von Straßen auswählen, so dass jede Stadt von jeder anderen aus erreicht werden kann, aber dass es nicht mehr als einen Weg gibt, um von einer Stadt zur anderen zu gelangen.
Ein Graph kann mehr als einen überspannenden Baum haben, genauso wie es mehr als eine Möglichkeit geben kann, die Straßen zwischen den Städten auszuwählen.
Meistens werden die Grafiken gewichtet; jede Verbindung zwischen zwei Städten hat ein Gewicht: Es kann etwas kosten, auf einer bestimmten Straße zu fahren, oder eine Verbindung kann länger als die andere sein, d.h. es dauert länger, auf dieser Verbindung zu fahren. In der Sprache der Graphentheorie werden die Verbindungen Kanten genannt.
Ein Baum ist ein Baum mit minimaler Spannweite. Er unterscheidet sich von anderen Bäumen dadurch, dass er die Summe der an den Rändern angebrachten Gewichte minimiert. Je nachdem, wie der Graph aussieht, kann es mehr als einen Baum mit minimaler Spannweite geben. In einem Graphen, in dem alle Kanten das gleiche Gewicht haben, ist jeder Baum ein Baum mit minimaler Spannweite. Wenn alle Kanten unterschiedlich gewichtet sind (d.h. es gibt keine zwei Kanten mit dem gleichen Gewicht), gibt es genau einen minimalen Spannbaum.
Der sich mindestens überspannende Baum eines planaren Graphen. Jede Kante ist mit ihrem Gewicht beschriftet, das hier ungefähr proportional zu ihrer Länge ist.
Finden des Baumes mit minimaler Spannweite
Ein erster Versuch
Es kann sehr einfach sein, einen Algorithmus zu erstellen, der einen minimalen überspannenden Baum entdeckt:
Funktion MST(G,W) : T = { } während T keinen überspannenden Baum bildet: die minimale gewichtete Kante in E finden, die für T sicher ist T = T Vereinigung {(u,v) } return TIn diesem Fall bedeutet "sicher", dass die Einbeziehung der Kante keinen Zyklus in der Grafik bildet. Ein Zyklus bedeutet, an einem Scheitelpunkt zu beginnen, sich zu einer Anzahl anderer Scheitelpunkte zu bewegen und wieder am Startpunkt zu enden, ohne die gleiche Kante zweimal zu verwenden.
Geschichte
Der tschechische Wissenschaftler Otakar Borůvka entwickelte 1926 den ersten bekannten Algorithmus für die Suche nach einem Baum mit minimaler Spannweite. Er wollte das Problem lösen, eine effiziente Abdeckung Mährens mit Elektrizität zu finden. Heute ist dieser Algorithmus als der Algorithmus von Borůvka bekannt. Zwei weitere Algorithmen werden heute allgemein verwendet. Einer dieser Algorithmen wurde 1930 von Vojtěch Jarník entwickelt und 1957 von Robert Clay Prim in die Praxis umgesetzt. Edsger Wybe Dijkstra entdeckte ihn 1959 wieder und nannte ihn Prim's Algorithmus. Der andere Algorithmus wird Kruskals Algorithmus genannt und wurde 1956 von Joseph Kruskal gepulvert. Alle drei Algorithmen sind gierig und laufen in polynomialer Zeit.
Der bisher schnellste Minimum Spanning Tree Algorithmus wurde von Bernard Chazelle entwickelt. Der Algorithmus basiert auf dem Soft-Heap, einer ungefähren Prioritätswarteschlange. Seine Laufzeit ist O(m α(m,n)), wobei m die Anzahl der Kanten, n die Anzahl der Vertices und α die klassische funktionale Inverse der Ackermann-Funktion ist. Die Funktion α wächst extrem langsam, so dass sie für alle praktischen Zwecke als eine Konstante betrachtet werden kann, die nicht größer als 4 ist; daher kommt der Algorithmus von Chazelle der linearen Zeit sehr nahe.
Welches ist der schnellstmögliche Algorithmus für dieses Problem? Das ist eine der ältesten offenen Fragen in der Informatik. Es gibt eindeutig eine lineare Untergrenze, da wir zumindest alle Gewichte untersuchen müssen. Wenn die Kantengewichte ganze Zahlen mit begrenzter Bitlänge sind, dann sind deterministische Algorithmen mit linearer Laufzeit bekannt. Für allgemeine Gewichte gibt es randomisierte Algorithmen, deren erwartete Laufzeit linear ist.
Das Problem kann auch auf verteilte Weise angegangen werden. Wenn jeder Knoten als ein Computer betrachtet wird und kein Knoten außer seinen eigenen verbundenen Verbindungen etwas weiß, kann man immer noch den verteilten minimalen Spannbaum berechnen.
Fragen und Antworten
F: Was ist ein minimal aufspannender Baum in der Graphentheorie?
A: Ein minimal aufspannender Baum ist ein Baum, der die Gesamtgewichte der Kanten in der Graphentheorie minimiert.
Q: Was ist ein Baum in der Graphentheorie?
A: In der Graphentheorie ist ein Baum eine Möglichkeit, alle Knoten miteinander zu verbinden, so dass es nur einen Weg von einem beliebigen Knoten zu einem anderen Knoten des Baums gibt.
F: Welchen Zweck hat die Auswahl von Straßen in einem Szenario der Graphentheorie, das Städte darstellt?
A: Der Zweck der Auswahl von Straßen in einem graphentheoretischen Szenario, das Städte darstellt, besteht darin, dass jede Stadt von jeder anderen Stadt aus erreicht werden kann, ohne dass es mehr als eine Möglichkeit gibt, von einer Stadt zur anderen zu gelangen.
F: Kann ein Graph mehr als einen spannenden Baum haben?
A: Ja, ein Graph kann mehr als einen überspannenden Baum haben.
F: Was ist der Unterschied zwischen einem minimal spannenden Baum und anderen Bäumen in der Graphentheorie?
A: Ein minimal spannender Baum minimiert die Gesamtgewichte der Kanten, während andere Bäume diese Eigenschaft nicht haben.
F: Was sind Kanten in der Graphentheorie?
A: Kanten sind die Verbindungen zwischen zwei Eckpunkten in der Graphentheorie.
F: Kann es in einem Graphen mehr als einen minimal spannenden Baum mit unterschiedlich gewichteten Kanten geben?
A: Ja, je nachdem, wie der Graph aussieht, kann es mehr als einen minimalen überspannenden Baum geben.
