Minimaler Spannbaum - Minimum spanning tree

Ein planarer Graph und sein minimaler aufspannender Baum. Jede Kante ist mit ihrem Gewicht beschriftet, das hier ungefähr proportional zu ihrer Länge ist.

Ein Minimum Spanning Tree ( MST ) oder Minimum Weight Spanning Tree ist eine Teilmenge der Kanten eines zusammenhängenden , kantengewichteten ungerichteten Graphen, der alle Knoten miteinander verbindet, ohne Zyklen und mit dem minimal möglichen Gesamtkantengewicht. Das heißt, es handelt sich um einen aufspannenden Baum, dessen Summe der Kantengewichte möglichst klein ist. Allgemeiner gesagt hat jeder kantengewichtete ungerichtete Graph (nicht notwendigerweise zusammenhängend) einen minimalen Spannwald , der eine Vereinigung der minimalen Spannbäume für seine verbundenen Komponenten ist .

Es gibt viele Anwendungsfälle für minimal aufspannende Bäume. Ein Beispiel ist ein Telekommunikationsunternehmen, das versucht, Kabel in einer neuen Nachbarschaft zu verlegen. Wenn das Kabel nur entlang bestimmter Pfade (z. B. Straßen) vergraben werden muss, gibt es einen Graphen, der die durch diese Pfade verbundenen Punkte (z. B. Häuser) enthält. Einige der Pfade können teurer sein, weil sie länger sind oder das Kabel tiefer vergraben werden müssen. diese Pfade würden durch Kanten mit größeren Gewichten dargestellt. Währung ist eine akzeptable Einheit für das Kantengewicht – Kantenlängen müssen nicht den normalen Regeln der Geometrie wie der Dreiecksungleichung gehorchen . Ein Spannbaum für diesen Graphen wäre eine Teilmenge dieser Pfade, die keine Zyklen hat, aber dennoch jedes Haus verbindet; es können mehrere aufspannende Bäume möglich sein. Ein minimaler Spannbaum wäre einer mit den niedrigsten Gesamtkosten und repräsentiert den günstigsten Weg zum Verlegen des Kabels.

Eigenschaften

Mögliche Vielfalt

Wenn der Graph n Knoten hat, hat jeder aufspannende Baum n − 1 Kanten.

Diese Abbildung zeigt, dass es in einem Graphen mehr als einen minimalen Spannbaum geben kann. In der Abbildung sind die beiden Bäume unterhalb des Graphen zwei Möglichkeiten des minimalen Spannbaums des gegebenen Graphen.

Es können mehrere minimale Spannbäume gleichen Gewichts vorhanden sein; insbesondere wenn alle Kantengewichte eines gegebenen Graphen gleich sind, dann ist jeder aufspannende Baum dieses Graphen minimal.

Einzigartigkeit

Wenn jede Kante ein bestimmtes Gewicht hat, gibt es nur einen eindeutigen minimalen Spannbaum . Dies trifft in vielen realistischen Situationen zu, wie zum Beispiel im obigen Beispiel der Telekommunikationsunternehmen, in denen es unwahrscheinlich ist, dass zwei Pfade genau die gleichen Kosten haben. Dies lässt sich auch auf übergreifende Wälder verallgemeinern.

Nachweisen:

1. Nehmen wir das Gegenteil , dass es zwei verschiedene MSTs A und B .
2. Da A und B sich unterscheiden, obwohl sie die gleichen Knoten enthalten, gibt es mindestens eine Kante, die zu dem einen gehört, aber nicht zum anderen. Unter diesen Kanten sei e ₁ diejenige mit dem geringsten Gewicht; Diese Wahl ist einzigartig, da die Kantengewichte alle unterschiedlich sind. Ohne Beschränkung der Allgemeinheit sei e ₁ in A .
3. Da B ein MST ist, muss { e ₁ } B einen Zyklus C mit e _{1 enthalten} .${\displaystyle \cup}$
4. Als Baum enthält A keine Zyklen, daher muss C eine Kante e _{2 haben} , die nicht in A liegt .
5. Da e ₁ als die eindeutige Kante mit dem niedrigsten Gewicht unter denen gewählt wurde, die genau zu A und B gehören , muss das Gewicht von e ₂ größer sein als das Gewicht von e ₁ .
6. Da e ₁ und e ₂ Teil des Kreises C sind, ergibt das Ersetzen von e ₂ durch e ₁ in B daher einen aufspannenden Baum mit geringerem Gewicht.
7. Dies widerspricht der Annahme, dass B ein MST ist.

Allgemeiner gesagt, wenn die Kantengewichte nicht alle verschieden sind, dann ist nur die (Mehrfach-)Menge von Gewichten in minimal aufspannenden Bäumen mit Sicherheit eindeutig; es ist für alle minimal aufspannenden Bäume gleich.

Untergrafik zu minimalen Kosten

Wenn die Gewichte positiv , dann Baum ein minimaler Spann ist in der Tat ein Minimum-Kosten Subgraphen alle Vertices verbindet, da Subgraphen enthält Zyklen notwendigerweise Gesamtgewicht haben.

Zyklus-Eigenschaft

Wenn das Gewicht einer Kante e von C für jeden Zyklus C im Graphen größer ist als die Einzelgewichte aller anderen Kanten von C , dann kann diese Kante nicht zu einer MST gehören.

Beweis: Nehmen Sie das Gegenteil an , dh dass e zu einem MST T _{1 gehört} . Dann löscht e brechen T ₁ in zwei Teilbäume mit den beiden Enden von e in verschiedenen Teilbäumen. Der Rest von C verbindet die Teilbäume neu, daher gibt es eine Kante f von C mit Enden in verschiedenen Teilbäumen, dh er verbindet die Teilbäume wieder zu einem Baum T ₂ mit einem Gewicht von weniger als dem von T ₁ , weil das Gewicht von f kleiner ist als das Gewicht von z .

Eigenschaft ausschneiden

Diese Abbildung zeigt die Schnitteigenschaft von MSTs. T ist der einzige MST des gegebenen Graphen. Wenn S = {A,B,D,E}, also VS = {C,F}, dann gibt es 3 Möglichkeiten der Kante über den Schnitt(S,VS), es sind Kanten BC, EC, EF des Originals Graph. Dann ist e eine der Kanten mit minimalem Gewicht für den Schnitt, daher ist S ∪ {e} Teil des MST T.

Wenn das Gewicht einer Kante e in der Schnittmenge von C für jeden Schnitt C des Graphen streng kleiner ist als die Gewichte aller anderen Kanten der Schnittmenge von C , dann gehört diese Kante zu allen MSTs des Graphen .

Beweis: Nehmen Sie an, dass es eine MST T gibt, die e nicht enthält . Das Hinzufügen von e zu T erzeugt einen Zyklus, der den Schnitt einmal bei e kreuzt und an einer anderen Kante e' zurückkreuzt . Löschen von e ' erhalten wir ein Spanning - Tree - T ∖ {e'} ∪ {e} streng geringeres Gewicht als T . Dies widerspricht der Annahme, dass T ein MST war.

Nach einem ähnlichen Argument ist jede dieser Kanten in einem minimalen Spannbaum enthalten, wenn mehr als eine Kante ein minimales Gewicht über einen Schnitt hat.

Kostenminimum

Wenn die minimale Kostenkante e eines Graphen eindeutig ist, dann ist diese Kante in jeder MST enthalten.

Beweis: Wenn e nicht in der MST enthalten wäre, würde das Entfernen einer der (kostenintensiveren) Kanten in dem Zyklus, der nach dem Hinzufügen von e zu der MST gebildet wurde, einen aufspannenden Baum mit geringerem Gewicht ergeben.

Kontraktion

Wenn T ein Baum von MST Kanten ist, dann können wir Vertrag T in einen einzelnen Scheitelpunkt , während der invariant Aufrechterhaltung , dass die MST des vertraglich vereinbarten Graph und T die MST für das Diagramm vor Schrumpfung gibt.

Algorithmen

In allen folgenden Algorithmen ist m die Anzahl der Kanten im Graphen und n die Anzahl der Scheitelpunkte.

Klassische Algorithmen

Der erste Algorithmus zum Finden eines minimalen Spannbaums wurde 1926 vom tschechischen Wissenschaftler Otakar Borůvka entwickelt (siehe Borůvkas Algorithmus ). Ihr Zweck war eine effiziente elektrische Versorgung Mährens . Der Algorithmus läuft in einer Abfolge von Stufen ab. In jeder Stufe, Boruvka-Schritt genannt , identifiziert es einen Wald F, der aus der minimalgewichtigen Kante besteht, die auf jeden Scheitelpunkt im Graphen G einfällt , und bildet dann den Graphen als Eingabe für den nächsten Schritt. Hier bezeichnet den Graphen, der von G durch Kontraktion von Kanten in F abgeleitet wird (durch die Cut-Eigenschaft gehören diese Kanten zum MST). Jeder Boruvka-Schritt benötigt lineare Zeit. Da die Anzahl der Scheitelpunkte in jedem Schritt um mindestens die Hälfte reduziert wird, benötigt der Algorithmus von Boruvka O( m log n ) Zeit. ${\displaystyle G_{1}=G\setminus F}$${\displaystyle G\setminus F}$

Ein zweiter Algorithmus ist Prim-Algorithmus , der durch erfunden wurde Vojtěch Jarník 1930 neu entdeckt und von Prim 1957 und Dijkstra 1959. Im Allgemeinen wächst die MST ( T ) eine Kante zu einem Zeitpunkt. Anfangs enthält T einen beliebigen Knoten. In jedem Schritt wird T um eine Kante mit dem geringsten Gewicht ( x , y ) erweitert, so dass x in T ist und y noch nicht in T ist . Durch die Cut-Eigenschaft befinden sich alle zu T hinzugefügten Kanten im MST. Seine Laufzeit beträgt entweder O( m log n ) oder O( m + n log n ), abhängig von den verwendeten Datenstrukturen.

Ein dritter allgemein verwendeter Algorithmus ist der Algorithmus von Kruskal , der ebenfalls O( m log n ) Zeit benötigt.

Ein vierter Algorithmus, der nicht so häufig verwendet wird, ist der Reverse-Delete-Algorithmus , der die Umkehrung von Kruskals Algorithmus ist. Seine Laufzeit ist O( m log n (log log n ) ³ ).

Alle vier sind gierige Algorithmen . Da sie in polynomialer Zeit laufen, ist in dem Problem solche Bäume zu finden , FP und die damit verbundene Entscheidungsprobleme wie die Bestimmung , ob eine bestimmte Kante in der MST ist oder bestimmt wird, ob das Mindestgesamtgewicht einen bestimmten Wert sind in überschreitet P .

Schnellere Algorithmen

Mehrere Forscher haben versucht, recheneffizientere Algorithmen zu finden.

In einem Vergleichsmodell, in dem die einzigen erlaubten Operationen auf Kantengewichte paarweise Vergleiche sind, fanden Karger, Klein & Tarjan (1995) einen linear-zeit-randomisierten Algorithmus basierend auf einer Kombination des Borůvka-Algorithmus und des Reverse-Delete-Algorithmus.

Der schnellste nicht-randomisierte vergleichsbasierte Algorithmus mit bekannter Komplexität von Bernard Chazelle basiert auf dem Soft Heap , einer ungefähren Prioritätswarteschlange. Seine Laufzeit ist O ( m  α( m , n )), wobei α die klassische funktionale Umkehrung der Ackermann-Funktion ist . Die Funktion α wächst extrem langsam, so dass sie für alle praktischen Zwecke als eine Konstante von nicht mehr als 4 angesehen werden kann; daher nimmt der Algorithmus von Chazelle sehr nahe an der linearen Zeit.

Linearzeitalgorithmen in Sonderfällen

Dichte Grafiken

Wenn der Graph dicht ist (dh m / n log log log n ), dann findet ein deterministischer Algorithmus von Fredman und Tarjan die MST in der Zeit O( m ). Der Algorithmus führt eine Reihe von Phasen aus. Jede Phase führt den Algorithmus von Prim viele Male aus, jeweils für eine begrenzte Anzahl von Schritten. Die Laufzeit jeder Phase beträgt O( m + n ). Wenn die Anzahl der Scheitelpunkte vor einer Phase beträgt , beträgt die Anzahl der nach einer Phase verbleibenden Scheitelpunkte höchstens . Daher werden höchstens Phasen benötigt, was eine lineare Laufzeit für dichte Graphen ergibt. ${\displaystyle n'}$${\displaystyle n'/2^{m/n'}}$${\displaystyle \log^{*}{n}}$

Es gibt andere Algorithmen, die in dichten Graphen in linearer Zeit arbeiten.

Ganzzahlige Gewichte

Wenn die Kantengewichte binär dargestellte Ganzzahlen sind, dann sind deterministische Algorithmen bekannt, die das Problem in O ( m  +  n ) ganzzahligen Operationen lösen . Ob das Problem für einen allgemeinen Graphen in linearer Zeit durch einen vergleichsbasierten Algorithmus deterministisch gelöst werden kann , bleibt offen.

Entscheidungsbäume

Bei einem gegebenen Graphen G, bei dem die Knoten und Kanten fixiert sind, aber die Gewichte unbekannt sind, ist es möglich, einen binären Entscheidungsbaum (DT) zum Berechnen des MST für jede beliebige Permutation von Gewichten zu konstruieren . Jeder interne Knoten des DT enthält einen Vergleich zwischen zwei Kanten, zB "Ist das Gewicht der Kante zwischen x und y größer als das Gewicht der Kante zwischen w und z ?". Die beiden Kinder des Knotens entsprechen den beiden Antwortmöglichkeiten „ja“ oder „nein“. In jedem Blatt des DT gibt es eine Liste von Kanten von G , die einem MST entsprechen. Die Laufzeitkomplexität eines DT ist die größte Anzahl von Abfragen, die erforderlich ist, um den MST zu finden, was nur der Tiefe des DT entspricht. Ein DT für einen Graphen G heißt optimal, wenn er die kleinste Tiefe aller korrekten DTs für G hat .

Für jede ganze Zahl r ist es möglich, durch Brute-Force-Suche optimale Entscheidungsbäume für alle Graphen auf r Knoten zu finden . Diese Suche erfolgt in zwei Schritten.

A. Generieren aller potenziellen DTs

• Es gibt verschiedene Graphen auf r Knoten.${\displaystyle 2^{r \choose 2}}$
• Für jeden Graphen kann immer ein MST durch r ( r -1) Vergleiche gefunden werden, zB durch den Algorithmus von Prim .
• Daher ist die Tiefe eines optimalen DT kleiner als .${\displaystyle r^{2}}$
• Daher ist die Anzahl interner Knoten in einem optimalen DT kleiner als .${\displaystyle 2^{r^{2}}}$
• Jeder interne Knoten vergleicht zwei Kanten. Die Anzahl der Kanten ist höchstens, also ist die unterschiedliche Anzahl von Vergleichen höchstens .${\displaystyle r^{2}}$${\displaystyle r^{4}}$
• Daher ist die Anzahl potenzieller DTs geringer als: .${\displaystyle {(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}}$

B. Identifizieren der richtigen DTs Um zu überprüfen, ob eine DT korrekt ist, sollte sie auf alle möglichen Permutationen der Kantengewichte überprüft werden.

• Die Anzahl solcher Permutationen beträgt höchstens .${\displaystyle (r^{2})!}$
• Lösen Sie für jede Permutation das MST-Problem in dem gegebenen Graphen mit einem beliebigen vorhandenen Algorithmus und vergleichen Sie das Ergebnis mit der vom DT gegebenen Antwort.
• Die Laufzeit eines MST-Algorithmus beträgt höchstens , also beträgt die Gesamtzeit, die zum Prüfen aller Permutationen benötigt wird, höchstens .${\displaystyle (r^{2})}$${\displaystyle (r^{2}+1)!}$

Somit beträgt die Gesamtzeit, die zum Finden einer optimalen DT für alle Graphen mit r Ecken benötigt wird: , was kleiner ist als: . ${\displaystyle 2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!}$${\displaystyle 2^{2^{r^{2}+o(r)}}}$

Optimaler Algorithmus

Seth Pettie und Vijaya Ramachandran haben einen nachweislich optimalen deterministischen vergleichsbasierten minimalen Spannbaum-Algorithmus gefunden. Das Folgende ist eine vereinfachte Beschreibung des Algorithmus.

1. Sei , wobei n die Anzahl der Ecken ist. Finden Sie alle optimalen Entscheidungsbäume auf r Knoten. Dies kann in der Zeit O( n ) erfolgen (siehe Entscheidungsbäume oben).${\displaystyle r=\log\log\log n}$
2. Partitionieren Sie den Graphen in Komponenten mit höchstens r Scheitelpunkten in jeder Komponente. Diese Partition verwendet einen weichen Heap , der eine kleine Anzahl von Kanten des Graphen "korrumpiert".
3. Verwenden Sie die optimalen Entscheidungsbäume, um einen MST für den unbeschädigten Teilgraphen innerhalb jeder Komponente zu finden.
4. Kontrahiere jede zusammenhängende Komponente, die von den MSTs aufgespannt wird, auf einen einzelnen Knoten und wende einen beliebigen Algorithmus an, der auf dichten Graphen in der Zeit O( m ) funktioniert, auf die Kontraktion des unverfälschten Teilgraphen
5. Fügen Sie die korrumpierten Kanten dem resultierenden Wald wieder hinzu, um einen Untergraphen zu bilden, der garantiert den minimalen Spannbaum enthält und um einen konstanten Faktor kleiner ist als der Ausgangsgraph. Wenden Sie den optimalen Algorithmus rekursiv auf diesen Graphen an.

Die Laufzeit aller Schritte im Algorithmus beträgt O( m ), mit Ausnahme des Schritts der Verwendung der Entscheidungsbäume . Die Laufzeit dieses Schrittes ist unbekannt, aber es wurde bewiesen, dass er optimal ist – kein Algorithmus kann besser als der optimale Entscheidungsbaum. Somit hat dieser Algorithmus die besondere Eigenschaft, dass er beweisbar optimal ist, obwohl seine Laufzeitkomplexität unbekannt ist .

Parallele und verteilte Algorithmen

Die Forschung hat auch parallele Algorithmen für das Problem des minimalen Spannbaums in Betracht gezogen . Mit einer linearen Anzahl von Prozessoren ist es möglich, das Problem rechtzeitig zu lösen . Bader & Cong (2006) demonstrieren einen Algorithmus, der MSTs auf 8 Prozessoren fünfmal schneller berechnen kann als ein optimierter sequentieller Algorithmus. ${\displaystyle O(\log n)}$

Andere spezialisierte Algorithmen wurden entwickelt, um minimale Spannbäume eines Graphen zu berechnen, der so groß ist, dass das meiste davon jederzeit auf der Festplatte gespeichert werden muss. Diese externen Speicheralgorithmen , wie sie beispielsweise in "Engineering an External Memory Minimum Spanning Tree Algorithm" von Roman, Dementiev et al Algorithmus. Sie berufen sich auf eine effiziente externe Speichersortieralgorithmen und auf Graph Kontraktion Techniken zur Verringerung der Größe des Graphen effizient.

Das Problem kann auch verteilt angegangen werden . Wenn jeder Knoten als Computer betrachtet wird und kein Knoten außer seinen eigenen verbundenen Links etwas weiß, kann man immer noch den verteilten minimalen Spannbaum berechnen .

MST auf vollständigen Grafiken

Alan M. Frieze zeigte , dass eine gegebene vollständige Graph auf n Vertices, mit Kantengewichten, die unabhängig identisch verteilte Zufallsvariablen mit Verteilungsfunktion erfüllen , dann als n - Ansätze + ∞ das erwartete Gewicht des MST nähert , wo die Riemann zeta Funktion ( genauer gesagt die Konstante von Apéry ). Frieze und Steele bewiesen auch Konvergenz in der Wahrscheinlichkeit. Svante Janson bewies einen zentralen Grenzwertsatz für das Gewicht des MST. ${\displaystyle F}$${\displaystyle F'(0)>0}$${\displaystyle \zeta (3)/F'(0)}$${\displaystyle\zeta}$${\displaystyle\zeta (3)}$

Für gleichförmige Zufallsgewichte in wurde die exakte erwartete Größe des minimalen Spannbaums für kleine vollständige Graphen berechnet. ${\displaystyle [0,1]}$

Anwendungen

Minimale Spannbäume haben direkte Anwendungen beim Entwurf von Netzwerken, einschließlich Computernetzwerken , Telekommunikationsnetzwerken , Transportnetzwerken , Wasserversorgungsnetzwerken und Stromnetzen (für die sie zuerst erfunden wurden, wie oben erwähnt). Sie werden als Unterroutinen in Algorithmen für andere Probleme aufgerufen, einschließlich des Christofides-Algorithmus zur Approximation des Travelling-Salesman-Problems , zur Approximation des Multiterminal-Minimum-Cut-Problems (das im Einzelterminal-Fall äquivalent zum Maximum-Flow-Problem ist ) und zur Approximation der gewichtetes perfektes Matching mit minimalen Kosten .

Weitere praktische Anwendungen, die auf minimalen Spannbäumen basieren, sind:

• Taxonomie .
• Clusteranalyse : Clustering-Punkte in der Ebene, Single-Linkage-Clustering (eine Methode des hierarchischen Clusterings ), graphentheoretisches Clustering und Clustering von Genexpressionsdaten .
• Erstellen von Bäumen für die Übertragung in Computernetzwerken.
• Bildregistrierung und Segmentierung – siehe Minimum Spanning Tree-basierte Segmentierung .
• Extraktion von krummlinigen Merkmalen in der Computer Vision .
• Handschrifterkennung mathematischer Ausdrücke.
• Schaltungsdesign : Implementieren effizienter mehrfacher konstanter Multiplikationen, wie sie in Filtern mit endlicher Impulsantwort verwendet werden.
• Regionalisierung sozio-geographischer Gebiete, Gruppierung von Gebieten in homogene, zusammenhängende Regionen.
• Vergleich von ökotoxikologischen Daten.
• Topologische Beobachtbarkeit in Energiesystemen.
• Messung der Homogenität von zweidimensionalen Materialien.
• Minimax- Prozesskontrolle .
• Minimum Spanning Trees können auch zur Beschreibung von Finanzmärkten verwendet werden. Eine Korrelationsmatrix kann erstellt werden, indem ein Korrelationskoeffizient zwischen zwei beliebigen Aktien berechnet wird. Diese Matrix kann topologisch als komplexes Netzwerk dargestellt werden und ein minimaler Spannbaum kann konstruiert werden, um Zusammenhänge zu visualisieren.

Verwandte Probleme

Minimale Steiner-Bäume von Ecken regelmäßiger Vielecke mit N = 3 bis 8 Seiten. Die kleinste Netzlänge L für N > 5 ist der Umfang abzüglich einer Seite. Quadrate repräsentieren Steiner-Punkte.

Das Problem, den Steiner-Baum einer Teilmenge der Knoten zu finden, dh des minimalen Baums, der die gegebene Teilmenge überspannt, ist bekannt als NP-vollständig .

Ein verwandtes Problem ist der k- minimale Spannbaum ( k- MST), der der Baum ist, der eine Teilmenge von k Knoten im Graphen mit minimalem Gewicht überspannt .

Eine Menge von k-kleinsten Spannbäumen ist eine Teilmenge von k Spannbäumen (von allen möglichen Spannbäumen), so dass kein Spannbaum außerhalb der Teilmenge ein geringeres Gewicht hat. (Beachten Sie, dass dieses Problem nichts mit dem k- minimalen Spannbaum zu tun hat.)

Der euklidische minimale Spannbaum ist ein Spannbaum eines Graphen mit Kantengewichten entsprechend dem euklidischen Abstand zwischen Knoten, die Punkte in der Ebene (oder im Raum) sind.

Der geradlinige minimale Spannbaum ist ein Spannbaum eines Graphen mit Kantengewichten, die dem geradlinigen Abstand zwischen Scheitelpunkten entsprechen, die Punkte in der Ebene (oder im Raum) sind.

Im verteilten Modell , bei dem jeder Knoten als Computer betrachtet wird und kein Knoten außer seinen eigenen verbundenen Verbindungen etwas weiß, kann man einen verteilten minimalen Spannbaum betrachten . Die mathematische Definition des Problems ist dieselbe, aber es gibt verschiedene Lösungsansätze.

Der kapazitierte minimale Spannbaum ist ein Baum, der einen markierten Knoten (Ursprung oder Wurzel) hat und jeder der an den Knoten angehängten Unterbäume enthält nicht mehr als c Knoten. c heißt Baumkapazität. CMST optimal zu lösen ist NP-schwer , aber gute Heuristiken wie Esau-Williams und Sharma produzieren Lösungen in polynomieller Zeit nahe dem Optimum.

Der gradbeschränkte minimale Spannbaum ist ein minimaler Spannbaum, bei dem jeder Scheitel mit nicht mehr als d anderen Scheiteln für eine gegebene Zahl d verbunden ist . Der Fall d  = 2 ist ein Spezialfall des Travelling-Salesman-Problems , so dass der gradbeschränkte minimale Spannbaum im Allgemeinen NP-hart ist .

Für gerichtete Graphen wird das minimale Spannbaumproblem Arborescence- Problem genannt und kann in quadratischer Zeit mit dem Chu-Liu/Edmonds-Algorithmus gelöst werden .

Ein maximaler Spannbaum ist ein Spannbaum mit einem Gewicht, das größer oder gleich dem Gewicht jedes anderen Spannbaums ist. Ein solcher Baum kann mit Algorithmen wie Prims oder Kruskals gefunden werden, nachdem die Kantengewichte mit -1 multipliziert und das MST-Problem auf dem neuen Graphen gelöst wurden. Ein Pfad im maximalen Spannbaum ist der breiteste Pfad im Graphen zwischen seinen beiden Endpunkten: Unter allen möglichen Pfaden maximiert er das Gewicht der Kante mit minimalem Gewicht. Maximum Spanning Trees finden Anwendungen in Parsing- Algorithmen für natürliche Sprachen und in Trainingsalgorithmen für bedingte Zufallsfelder .

Das dynamische MST- Problem betrifft die Aktualisierung einer zuvor berechneten MST nach einer Kantengewichtsänderung im ursprünglichen Graphen oder dem Einfügen/Löschen eines Scheitelpunkts.

Das Spanning-Tree-Problem mit minimaler Beschriftung besteht darin, einen Spannbaum mit den wenigsten Typen von Beschriftungen zu finden, wenn jeder Kante in einem Graphen eine Beschriftung aus einem endlichen Beschriftungssatz anstelle einer Gewichtung zugeordnet ist.

Eine Engpasskante ist die am höchsten gewichtete Kante in einem Spannbaum. Ein Spannbaum ist ein minimaler Flaschenhalsspannbaum (oder MBST ), wenn der Graph keinen Spannbaum mit einem kleineren Flaschenhalskantengewicht enthält. Ein MST ist notwendigerweise ein MBST (beweisbar durch die cut-Eigenschaft ), aber ein MBST ist nicht unbedingt ein MST.

Verweise

Weiterlesen

• Otakar Boruvka on Minimum Spanning Tree Problem (Übersetzung der beiden Aufsätze von 1926, Kommentare, Geschichte) (2000) Jaroslav Nešetřil , Eva Milková, Helena Nesetrilová. (Abschnitt 7 beschreibt seinen Algorithmus, der wie eine Kreuzung zwischen Prims und Kruskals Algorithmus aussieht.)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest und Clifford Stein . Einführung in Algorithmen , Zweite Auflage. MIT Press und McGraw-Hill, 2001. ISBN  0-262-03293-7 . Kapitel 23: Minimum Spanning Trees, S. 561–579.
• Eisner, Jason (1997). Modernste Algorithmen für minimale Spannbäume: Eine Tutorial-Diskussion . Manuskript, University of Pennsylvania, April. 78 S.
• Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Verwendung eines minimalen Spannbaums als Methode der demografischen Analyse der ethnischen Vielfalt in den Vereinigten Staaten).

Externe Links

• Implementiert in BGL, der Boost Graph Library
• Das Stony Brook Algorithm Repository - Minimum Spanning Tree Codes
• Implementiert in QuickGraph für .Net