Minimum spanning tree

A Planare Graph und sein minimaler Spannungsbaum. Jede Kante ist mit seinem Gewicht gekennzeichnet, was hier ungefähr proportional zu seiner Länge ist.

A Minimum Spanning Tree (Mst) oder minimales Gewichtsspannungsbaum ist eine Untergruppe der Kanten von a in Verbindung gebracht, Kantengewichted ungerichtete Graphen, das alle verbindet Eckpunkte zusammen ohne irgendwelche Fahrräder und mit dem minimal möglichen Gesamtkantengewicht.[1] Das heißt, es ist ein Spannungsbaum deren Summe von Kantengewichten so klein wie möglich ist.[2] Im Allgemeinen hat jedes von Kantengewicht gewichtete, ungerichtete Diagramm (nicht unbedingt miteinander verbunden) a Mindestwald, was eine Vereinigung des Mindestbäume für seine ist verbundene Komponenten.

Es gibt viele Anwendungsfälle für minimale Spannbäume. Ein Beispiel ist ein Telekommunikationsunternehmen, das versucht, Kabel in einer neuen Nachbarschaft zu legen. Wenn es eingeschränkt ist, das Kabel nur entlang bestimmter Pfade (z. B. Straßen) zu begraben, würde es ein Diagramm geben, das die Punkte (z. B. Häuser) enthält, die durch diese Pfade verbunden sind. Einige der Wege sind möglicherweise teurer, da sie länger sind oder das Kabel tiefer begraben wird. Diese Pfade würden durch Kanten mit größeren Gewichten dargestellt. Währung ist eine akzeptable Einheit für das Randgewicht - es ist nicht erforderlich, dass die Kantenlängen normale Geometrieregeln wie die befolgen Dreiecksungleichung. EIN Spannungsbaum Denn dieses Diagramm wäre eine Untergruppe dieser Pfade, die keine Zyklen hat, aber immer noch jedes Haus verbindet; Möglicherweise können mehrere Bäume möglich sein. EIN Minimum Spanning Tree wäre eins mit den niedrigsten Gesamtkosten, was den kostengünstigsten Pfad für das Verlegen des Kabels darstellt.

Eigenschaften

Mögliche Multiplizität

Wenn es gibt n Scheitelpunkte im Diagramm, dann hat jeder Spannungsbaum n - 1 Kanten.

Diese Abbildung zeigt, dass es möglicherweise mehr als einen minimalen Spannungsbaum in einem Diagramm gibt. In der Abbildung sind die beiden Bäume unterhalb der Grafik zwei Möglichkeiten des minimalen Spannungsbaums des angegebenen Graphen.

Es kann mehrere minimale Spannbäume mit gleichem Gewicht geben; Insbesondere wenn alle Kantengewichte eines bestimmten Diagramms gleich sind, ist jeder Spannungsbaum dieses Diagramms minimal.

Einzigartigkeit

Wenn jede Kante ein ausgeprägtes Gewicht hat, gibt es nur einen einzigartigen minimalen Spannungsbaum. Dies gilt in vielen realistischen Situationen, wie dem obigen Beispiel des Telekommunikationsunternehmens, in dem es unwahrscheinlich ist exakt die gleichen Kosten. Dies verallgemeinert auch Wälder.

Nachweisen:

  1. Übernehmen das Gegenteil, dass es zwei verschiedene MSTs gibt A und B.
  2. Seit A und B Unterscheiden Sie sich trotz der gleichen Knoten, es gibt mindestens eine Kante, die zu einem gehört, aber nicht den anderen. Unter solchen Kanten lassen e1 Sei der mit geringstem Gewicht; Diese Wahl ist einzigartig, da die Kantengewichte alle unterschiedlich sind. Ohne Verlust der Allgemeinheit annehmen e1 ist in A.
  3. Wie B ist ein MST, {e1} ∪ B Muss einen Zyklus enthalten C mit e1.
  4. Als Baum, A enthält daher keine Zyklen, deshalb C Muss eine Kante haben e2 das ist nicht in A.
  5. Seit e1 wurde als die einzigartige Kante mit niedrigster Gewicht unter denjenigen ausgewählt, die genau einem von gehören A und Bdas Gewicht von e2 muss größer sein als das Gewicht von e1.
  6. Wie e1 und e2 sind Teil des Zyklus C, ersetzen e2 mit e1 in B Daher liefert ein Spannbaum mit einem geringeren Gewicht.
  7. Dies widerspricht der Annahme, dass B ist ein MST.

Wenn die Kantengewichte nicht alle unterschiedlich sind, ist nur der (multi-) Satz von Gewichten in minimalen Spannbäumen sicher einzigartig. Es ist für alle minimalen Spannbäume gleich.[3]

Mindestpreis-Subgraph

Wenn die Gewichte sind positivund dann ist ein minimaler Spannungsbaum tatsächlich ein Mindestpreis Untergraph Verbinden Sie alle Scheitelpunkte, da Untergraphen enthalten sind Fahrräder notwendigerweise mehr Gesamtgewicht.

Zykluseigenschaft

Für jeden Zyklus C In der Grafik, wenn das Gewicht einer Kante e von C ist größer als die individuellen Gewichte aller anderen Kanten von Cund dann kann diese Kante nicht zu einem MST gehören.

Nachweisen: Übernehmen das Gegenteil, d.h. das e gehört zu einer MST T1. Dann löschen e wird brechen T1 in zwei Unterbäume mit den beiden Enden von e In verschiedenen Teilbäumen. Der Rest von C verbindet die Unterbälle wieder, daher gibt es eine Kante f von C mit den Enden in verschiedenen Unterbällen, d. H. Es verbindet die Unterbälde wieder zu einem Baum T2 mit weniger Gewicht als das von T1, weil das Gewicht von f ist weniger als das Gewicht von e.

Eigenschaft abschneiden

Diese Abbildung zeigt die geschnittene Eigenschaft von MSTs. T ist der einzige MST des angegebenen Diagramms. Wenn S = {{A,B,D,E}, daher V – S = {{C,F}, Dann gibt es 3 Möglichkeiten der Kante über den Schnitt (S, V – S), sie sind Kanten BC, EC, EF der ursprünglichen Grafik. Dann ist E daher einer der Mindestgewichtskanten für den Schnitt S ∪ {e} ist Teil der MST T.

Für jeden schneiden C der Grafik, wenn das Gewicht einer Kante e im geschnittenen Set von C ist streng kleiner als die Gewichte aller anderen Kanten des geschnittenen Sets von Cund dann gehört diese Kante zu allen MSTs des Diagramms.

Nachweisen: Davon ausgehen dass es eine MST gibt T das enthält nicht e. Hinzufügen e zu T wird einen Zyklus erzeugen, der den Schnitt einmal bei kreuzt e und überquert an einer anderen Kante zurück E '. Löschen E ' Wir bekommen einen Spannungsbaum T∖ {E ' } ∪ {e} von streng kleinerem Gewicht als T. Dies widerspricht der Annahme, dass T war ein MST.

Wenn mehr als eine Kante über einen Schnitt minimales Gewicht ist, ist durch ein ähnliches Argument jede solche Kante in einem minimalen Spannungsbaum enthalten.

Mindestpreiskante

Wenn die Mindestkostenkante e einer Grafik ist einzigartig, dann ist diese Kante in jedem MST enthalten.

Beweis: if e wurde nicht in der MST enthalten, wobei die (größeren Kosten-) Kanten im Zyklus entfernt wurden, das nach dem Hinzufügen gebildet wurde e Zum MST würde ein Spannungsbaum mit kleineren Gewicht liefern.

Kontraktion

Wenn T ist ein Baum von MST -Kanten, dann können wir Vertrag T in einen einzelnen Scheitelpunkt, während die Invariante beibehält, dass der MST des Contracted Graph Plus T Gibt den MST für die Grafik vor der Kontraktion an.[4]

Algorithmen

In allen unten stehenden Algorithmen, m ist die Anzahl der Kanten in der Grafik und n ist die Anzahl der Eckpunkte.

Klassische Algorithmen

Der erste Algorithmus zum Auffinden eines minimalen Spannungsbaums wurde vom tschechischen Wissenschaftler entwickelt Otakar Borůvka 1926 (siehe Borůvkas Algorithmus). Sein Zweck war eine effiziente elektrische Abdeckung von Mähren. Der Algorithmus geht in einer Reihenfolge von Stadien fort. In jeder Phase, genannt Boruvka Schritt, es identifiziert einen Wald F bestehend aus der minimalen Gewichtskante, die jedem Scheitelpunkt in der Grafik findet Gbildet dann die Grafik G1 = G \ F als Eingabe zum nächsten Schritt. Hier G \ F bezeichnet die abgeleitete Grafik von G durch Vertragskanten in F (bis zum Eigenschaft abschneiden, diese Kanten gehören zum MST). Jeder Boruvka -Schritt dauert linear. Da die Anzahl der Scheitelpunkte in jedem Schritt um mindestens die Hälfte reduziert wird, nimmt Boruvkas Algorithmus ein O(m Protokoll n) Zeit.[4]

Ein zweiter Algorithmus ist Prims Algorithmus, was erfunden wurde von Vojtěch Jarník im Jahr 1930 und wiederentdeckt von Prim im Jahr 1957 und Dijkstra 1959. Grundsätzlich wächst es den MST ((T) eine Kante nach dem anderen. Anfänglich, T Enthält einen willkürlichen Scheitelpunkt. In jedem Schritt, T wird mit einer Kante mit kleinem Gewicht erweitert (x,y) so dass x ist in T und y ist noch nicht in T. Bis zum Eigenschaft abschneiden, alle Kanten hinzugefügt zu T sind in der MST. Die Laufzeit ist entweder O(m Protokoll n) oder O(m + n Protokoll n)abhängig von den verwendeten Datenstrukturen.

Ein dritter Algorithmus, der häufig verwendet wird Kruskals Algorithmus, was auch nimmt O(m Protokoll n) Zeit.

Ein vierter Algorithmus, der nicht so häufig verwendet wird, ist das Reverse-Delete-Algorithmus, das ist die Rückseite des Algorithmus von Kruskal. Seine Laufzeit ist Ö(m Protokoll n (Protokollprotokoll n)3).

Alle vier sind gierige Algorithmen. Da sie in Polynomzeit laufen, liegt das Problem, solche Bäume zu finden FP, und die damit verbundenen Entscheidungsprobleme z. B. zu bestimmen, ob sich eine bestimmte Kante im MST befindet, oder festzustellen, ob das minimale Gesamtgewicht einen bestimmten Wert überschreitet P.

Schnellere Algorithmen

Mehrere Forscher haben versucht, rechnerisch effizientere Algorithmen zu finden.

In einem Vergleichsmodell, bei dem die einzigen zulässigen Operationen für Kantengewichte paarweise Vergleiche sind, Karger, Klein & Tarjan (1995) ein gefunden randomisierte lineare Zeitalgorithmus Basierend auf einer Kombination aus Borůvkas Algorithmus und dem umgekehrten Algorithmus.[5][6]

Der am schnellsten nicht randomisierte, vergleichsbasierte Algorithmus mit bekannter Komplexität durch Bernard Chazelle, basiert auf dem weicher Haufen, eine ungefähre Prioritätswarteschlange.[7][8] Seine Laufzeit ist O(m α (m,n)), wo α ist die klassische Funktional Umkehrung der Ackermann -Funktion. Die Funktion α wächst extrem langsam, so dass es für alle praktischen Zwecke als konstante als 4 angesehen werden kann; Somit dauert Chazelles Algorithmus sehr nahe an der linearen Zeit.

Linear-Zeit-Algorithmen in besonderen Fällen

Dichte Grafiken

Wenn die Grafik dicht ist (d. H. m/n ≥ Protokollprotokollprotokoll n)dann findet ein deterministischer Algorithmus von Fredman und Tarjan den MST rechtzeitig Ö(m).[9] Der Algorithmus führt eine Reihe von Phasen aus. Jede Phase wird ausgeführt Prims Algorithmus Oft für eine begrenzte Anzahl von Schritten. Die Laufzeit jeder Phase ist Ö(m + n). Wenn die Anzahl der Eckpunkte vor einer Phase ist n'Die Anzahl der verbleibenden Eckpunkte, die nach einer Phase bestehen, ist höchstens . Daher höchstens Protokoll*n Es werden Phasen benötigt, die eine lineare Laufzeit für dichte Graphen verleihen.[4]

Es gibt andere Algorithmen, die in der linearen Zeit in dichten Graphen arbeiten.[7][10]

Ganzzahlgewichte

Wenn die Kantengewichte in binär dargestellt sind, sind deterministische Algorithmen bekannt, die das Problem in lösen O(m + n) Ganzzahloperationen.[11] Ob das Problem gelöst werden kann deterministisch Für ein Allgemeine Grafik in lineare Zeit Durch einen vergleichsbasierten Algorithmus bleibt eine offene Frage.

Entscheidungsbäume

Gegebene Grafik G Wenn die Knoten und Kanten festgelegt sind, die Gewichte jedoch unbekannt sind, ist es möglich, ein binär Entscheidungsbaum (Dt) zur Berechnung des MST für jede Permutation von Gewichten. Jeder interne Knoten des DT enthält einen Vergleich zwischen zwei Kanten, z. "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 möglichen Antworten" Ja "oder" Nein ". In jedem Blatt des DT gibt es eine Liste von Kanten aus G das entspricht einem MST. Die Laufzeitkomplexität eines DT ist die größte Anzahl von Abfragen, die erforderlich sind, um den MST zu finden, der nur die Tiefe des DT ist. Ein DT für eine Grafik G wird genannt optimal Wenn es die kleinste Tiefe aller korrekten DTs für hat G.

Für jede ganze Zahl rEs ist möglich, optimale Entscheidungsbäume für alle Grafiken auf zu finden r Eckpunkte von Brute-Force-Suche. Diese Suche erfolgt in zwei Schritten.

A. Alle potenziellen DTs erzeugen

  • Es gibt Verschiedene Grafiken auf r Eckpunkte.
  • Für jedes Diagramm kann ein MST immer verwendet werden r(r - 1) Vergleiche, z. durch Prims Algorithmus.
  • Daher ist die Tiefe eines optimalen DT geringer als r2.
  • Daher ist die Anzahl der internen Knoten in einem optimalen DT geringer als .
  • Jeder interne Knoten vergleicht zwei Kanten. Die Anzahl der Kanten ist höchstens r2 Die unterschiedliche Anzahl der Vergleiche ist also höchstens r4.
  • Daher ist die Anzahl der potenziellen DTs geringer als

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

  • Die Anzahl solcher Permutationen ist höchstens (r2)!.
  • Lösen Sie für jede Permutation das MST -Problem in der angegebenen Grafik mit einem vorhandenen Algorithmus und vergleichen Sie das Ergebnis mit der von der DT angegebenen Antwort.
  • Die Laufzeit eines MST -Algorithmus ist höchstens r2Die Gesamtzeit, die erforderlich ist, um alle Permutationen zu überprüfen (r2 + 1)!.

Daher die Gesamtzeit für die Suche nach einem optimalen DT für alle Grafiken mit r Scheitelpunkte ist:[4]

das ist weniger als

Siehe auch: Entscheidungsbaummodell

Optimaler Algorithmus

Seth Pettie und Vijaya Ramachandran haben einen nachweislich optimalen deterministischen Vergleichs-basierten Mindestspannungsbaumalgorithmus gefunden.[4] Das Folgende ist eine vereinfachte Beschreibung des Algorithmus.

  1. Lassen r = Protokollprotokollprotokoll n, wo n ist die Anzahl der Eckpunkte. Finden Sie alle optimalen Entscheidungsbäume auf r Eckpunkte. Dies kann rechtzeitig erfolgen O(n) (sehen Entscheidungsbäume Oben).
  2. Partitionieren Sie die Grafik in Komponenten mit höchstens r Scheitelpunkte in jeder Komponente. Diese Partition verwendet a weicher Haufen, was eine kleine Anzahl der Kanten des Diagramms "verderbt".
  3. Verwenden Sie die optimalen Entscheidungsbäume, um einen MST für den nicht korrumpierten Untergraph in jeder Komponente zu finden.
  4. Vertrag jede von den MSTS überholte verbundene angeschlossene Komponente an einen einzelnen Scheitelpunkt und wenden Sie jeden Algorithmus an, an dem funktioniert dichte Grafiken rechtzeitig O(m) zur Kontraktion des nicht korrumpierten Untergraphen
  5. Fügen Sie die beschädigten Kanten in den resultierenden Wald zurück, um einen Untergraphen zu bilden, der garantiert den minimalen Spannungsbaum enthält, und um einen konstanten Faktor als das Startdiagramm kleiner. Wenden Sie den optimalen Algorithmus rekursiv auf dieses Diagramm an.

Die Laufzeit aller Schritte im Algorithmus ist O(m), Mit Ausnahme des Schritts der Entscheidungsbäume. Die Laufzeit dieses Schritts ist unbekannt, aber es wurde bewiesen, dass er optimal ist - kein Algorithmus kann es besser machen als der optimale Entscheidungsbaum. Somit hat dieser Algorithmus die besondere Eigenschaft, die es ist nachweislich optimal Obwohl seine Laufzeitkomplexität ist Unbekannt.

Parallele und verteilte Algorithmen

Weitere Informationen: Parallelalgorithmen für minimale Spannbäume

Die Forschung hat auch in Betracht gezogen Parallelalgorithmen für das minimale Spannungsbaumproblem. Mit einer linearen Anzahl von Prozessoren ist es möglich, das Problem in zu lösen O(Protokoll n) Zeit.[12][13] Bader & Cong (2006) Demonstrieren Sie einen Algorithmus, der MSTS 5 -mal schneller auf 8 Prozessoren berechnen kann als ein optimierter sequentieller Algorithmus.[14]

Andere spezialisierte Algorithmen wurden für die Berechnung von Mindestspannungsbäumen aus einem so großen Diagramm entwickelt, dass das meiste immer auf der Festplatte gespeichert werden muss. Diese externer Speicher Algorithmen, beispielsweise wie in "Engineering A External Memory Minimum Spanning Tree Algorithmus" von Roman, Demenz et al.,[15] kann nach Ansprüchen der Autoren betreiben, nur 2- bis 5-mal langsamer als ein herkömmlicher In-Memory-Algorithmus. Sie verlassen sich auf effiziente Externe Speichersortieralgorithmen und weiter Grafikkontraktion Techniken zur effizienten Reduzierung der Größe des Diagramms.

Das Problem kann auch in a angegangen werden verteilte Weise. Wenn jeder Knoten als Computer angesehen wird und kein Knoten etwas außer seinen eigenen verbundenen Links weiß, kann man dennoch die berechnen verteilter minimaler Spannungsbaum.

MST in vollständigen Grafiken

Alan M. Frieze zeigte das gegeben a Komplette Graph an n Scheitelpunkte mit Kantengewichten, die unabhängige identisch verteilte Zufallsvariablen mit der Verteilungsfunktion sind befriedigend , Dann als n Ansätze +∞ Das erwartete Gewicht der MST nähert sich , wo ist der Riemann Zeta -Funktion (Genauer gesagt ist Apéry ist konstant). Frieze und Steele Auch die Wahrscheinlichkeitskonvergenz. Svante Janson bewiesen a Zentralgrenze Theorem Für das Gewicht des MST.

Für einheitliche zufällige Gewichte in Die genau erwartete Größe des minimalen Spannungsbaums wurde für kleine vollständige Graphen berechnet.[16]

Eckpunkte Erwartete Größe Ungefähre erwartete Größe
2
1/2
0,5
3
3/4
0,75
4
31/35
0,8857143
5
893/924
0,9664502
6
278/273
1.0183151
7
30739/29172
1.053716
8
199462271/184848378
1.0790588
9
126510063932/115228853025
1.0979027

Anwendungen

Mindestüberschreitende Bäume haben direkte Anwendungen für die Gestaltung von Netzwerken, einschließlich Computernetzwerke, Telekommunikationsnetzwerke, Transportnetzwerke, Wasserversorgungsnetzwerke, und elektrische Gitter (für die sie zuerst erfunden wurden, wie oben erwähnt).[17] Sie werden als Unterprogramm in Algorithmen für andere Probleme, einschließlich der Christofides Algorithmus zum ungefähren Annäherungen Problem mit reisenden Verkäufern,[18] Annäherung des Multi-terminalen Mindestkürzungsproblem Maximales Durchflussproblem),[19] und approximieren Sie die minimalkostgewichtete perfekte Matching.[20]

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

Verwandte Probleme

Minimum Steinerbäume von Eckpunkte von normalen Polygonen mit N = 3 bis 8 Seiten. Die niedrigste Netzwerklänge L zum N > 5 ist der Umfang weniger auf einer Seite. Quadrate repräsentieren Steiner -Punkte.

Das Problem, das zu finden Steinerbaum von einer Teilmenge der Eckpunkte, dh minimaler Baum, der die angegebene Teilmenge überspannt, ist bekannt dafür NP-Complete.[39]

Ein verwandtes Problem ist das k-Minimum Spanning Tree (k-Mst), das ist der Baum, der eine Teilmenge von umfasst k Scheitelpunkte im Diagramm mit minimalem Gewicht.

Eine Menge von K-Smallest über Bäume ist eine Teilmenge von k Spannungsbäume (aus allen möglichen Spannbäumen), so dass kein Spannungsbaum außerhalb der Untergruppe ein geringer Gewicht hat.[40][41][42] (Beachten Sie, dass dieses Problem nichts mit dem zu tun hat k-Minimum Spannungsbaum.)

Das Euklidischer Minimum Spanning Tree ist ein Spannungsbaum eines Diagramms mit Kantengewichten, die dem euklidischen Abstand zwischen Scheitelpunkten entsprechen, die Punkte in der Ebene (oder in den Raum) sind.

Das geradliniger Mindestspannungsbaum ist ein Spannungsbaum eines Diagramms mit Kantengewichten, die dem entsprechen geradlinige Entfernung zwischen Scheitelpunkten, die Punkte in der Ebene (oder in Raum) sind.

In dem Verteilter Modell, wo jeder Knoten als Computer angesehen wird und kein Knoten etwas außer seinen eigenen verbundenen Links weiß, kann man berücksichtigen verteilter minimaler Spannungsbaum. Die mathematische Definition des Problems ist gleich, aber es gibt verschiedene Ansätze für eine Lösung.

Das kapazitierter minimaler Spannungsbaum ist ein Baum, der einen markierten Knoten (Ursprung oder Wurzel) hat, und jede der an den Knoten befestigten Unterbäume enthält nicht mehr als a c Knoten. c wird als Baumkapazität bezeichnet. CMST optimal zu lösen ist Np-harte,[43] Aber gute Heuristiken wie Esau-Williams und Sharma produzieren Lösungen, die in der Polynomzeit nahezu optimal sind.

Das Grad eingeschränkte minimale Spannungsbaum ist ein minimaler Spannungsbaum, bei dem jeder Scheitelpunkt mit nicht mehr als verbunden ist d Andere Scheitelpunkte für eine bestimmte Zahl d. Der Fall d= 2 ist ein Sonderfall der Problem mit reisenden Verkäufernso ist der Grad eingeschränkte minimale Spannungsbaum Np-harte Im Algemeinen.

Zum Regie GraphenDas Problem mit dem minimalen Spannungsbaum heißt das Arboreszenz Problem und kann gelöst werden Zeit mit dem Chu -Liu/Edmonds -Algorithmus.

A Maximaler Spannungsbaum ist ein Spannungsbaum mit Gewicht größer oder gleich dem Gewicht jedes anderen Spannungsbaums. Ein solcher Baum ist mit Algorithmen wie Prims oder Kruskal zu finden, nachdem die Kantengewichte mit -1 multipliziert und das MST -Problem auf dem neuen Diagramm gelöst werden kann. Ein Pfad im maximalen Spannungsbaum ist der Breitlichster Weg In der Grafik zwischen den beiden Endpunkten: Unter allen möglichen Pfaden maximiert es das Gewicht der minimalen Gewichtskante.[44] Maximale Spannbäume finden Anwendungen in Parsing Algorithmen für natürliche Sprachen[45] und in Trainingsalgorithmen für bedingte zufällige Felder.

Das Dynamischer MST Das Problem betrifft die Aktualisierung eines zuvor berechneten MST nach einer Kantengewichtsänderung im ursprünglichen Diagramm oder der Einfügung/Löschung eines Scheitelpunkts.[46][47][48]

Das Problem mit minimaler Beschriftung ist das Problem der Spannung mit einem Spannungsbaum mit den geringsten Arten von Etiketten, wenn jede Kante in einem Diagramm einer Etikett aus einem endlichen Etikettssatz anstelle eines Gewichts zugeordnet ist.[49]

Eine Engpasskante ist die höchste gewichtete Kante in einem Spannungsbaum. Ein Spannungsbaum ist ein minimaler Engpassspannungsbaum (oder Mbst) Wenn die Grafik keinen Spannungsbaum mit einem kleineren Engpass -Kantengewicht enthält. Ein MST ist notwendigerweise ein MBST (von der nachweisbar Eigenschaft abschneiden), aber ein MBST ist nicht unbedingt ein MST.[50][51]

Verweise

  1. ^ "scipy.sparse.csgraph.minimum_spanning_tree - scipy v1.7.1 Handbuch". Dokumentation von Numpy and Scipy - Numpy and Scipy -Dokumentation. Abgerufen 2021-12-10. Ein minimaler Spannungsbaum ist ein Graph, das aus der Teilmenge von Kanten besteht, die zusammen alle verbundenen Knoten verbinden und gleichzeitig die Gesamtsumme der Gewichte an den Kanten minimieren.
  2. ^ "networkx.algorithms.tree.mst.minimum_spanning_edges". NetworkX 2.6.2 Dokumentation. Abgerufen 2021-12-13. Ein minimaler Spannungsbaum ist ein Untergraphen des Graphen (ein Baum) mit der minimalen Summe der Kantengewichte. Ein Spannwald ist eine Vereinigung der Spannbäume für jede verbundene Komponente des Diagramms.
  3. ^ "Haben die minimalen Spannbäume eines gewichteten Diagramms die gleiche Anzahl von Kanten mit einem bestimmten Gewicht?". CS.Stackexchange.com. Abgerufen 4. April 2018.
  4. ^ a b c d e Pettie, Seth; Ramachandran, Vijaya (2002), "Ein optimaler minimaler Spanning -Baumalgorithmus" (PDF), Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, HERR 2148431, S2CID 5362916.
  5. ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "ein randomisierter Linear-Zeit-Algorithmus, um minimale Spannbäume zu finden", Journal of the Association for Computing Machinery, 42 (2): 321–328, doi:10.1145/201019.201022, HERR 1409738, S2CID 832583
  6. ^ Pettie, Seth; Ramachandran, Vijaya (2002), "Minimierung der Zufälligkeit des minimalen Spannungsbaums, paralleler Konnektivität und Maxima -Algorithmen", Proc. 13. ACM-SIAM-Symposium über diskrete Algorithmen (Soda '02), San Francisco, Kalifornien, S. 713–722.
  7. ^ a b Chazelle, Bernard (2000), "ein minimaler Spanning-Baumalgorithmus mit Komplexität des Typs inverse-ackermann", Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, HERR 1866456, S2CID 6276962.
  8. ^ Chazelle, Bernard (2000), "Der weiche Haufen: eine ungefähre Prioritätswarteschlange mit optimaler Fehlerrate", Journal of the Association for Computing Machinery, 47 (6): 1012–1027, doi:10.1145/355541.355554, HERR 1866455, S2CID 12556140.
  9. ^ Fredman, M. L.; Tarjan, R. E. (1987). "Fibonacci Heaps und ihre Verwendung in verbesserten Netzwerkoptimierungsalgorithmen". Journal of the ACM. 34 (3): 596. doi:10.1145/28869.28874. S2CID 7904683.
  10. ^ Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986). "Effiziente Algorithmen zum Auffinden minimaler Spannbäume in ungerichteten und gerichteten Graphen". Combinatorica. 6 (2): 109. doi:10.1007/bf02579168. S2CID 35618095.
  11. ^ Fredman, M. L.; Willard, D. E. (1994), "Trans-Dichotome Algorithmen für minimale Spannbäume und kürzeste Wege", Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/s0022-0000 (05) 80064-9, HERR 1279413.
  12. ^ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Gleichzeitige Fäden und optimale parallele Minimum -Spannungs -Bäume -Algorithmus", Journal of the Association for Computing Machinery, 48 (2): 297–323, doi:10.1145/375827.375847, HERR 1868718, S2CID 1778676.
  13. ^ Pettie, Seth; Ramachandran, Vijaya (2002), "Ein randomisierter Zeitwerk optimaler paralleler Algorithmus zum Auffinden eines minimalen Spannwaldes" (PDF), Siam Journal über Computing, 31 (6): 1879–1895, doi:10.1137/s0097539700371065, HERR 1954882.
  14. ^ Bader, David A.; Cong, Guojing (2006), "Schnell gemeinsam genutzte Memory-Algorithmen zum Berechnen des minimalen Spannungswaldes von spärlichen Graphen", Journal of Parallel und Distributed Computing, 66 (11): 1366–1378, doi:10.1016/j.jpdc.2006.06.001, S2CID 2004627.
  15. ^ Demenz, Roman; Sanders, Peter; Schulte, Dominik; SIBEYN, JOP F. (2004), "Engineering A External Memory Minimum Spanning Tree Algorithmus", Proc. IFIP 18. World Computer Congress, TC1 3. Internationaler Konferenz über theoretische Informatik (TCS2004) (PDF), S. 195–208.
  16. ^ Steele, J. Michael (2002), "minimale Spannbäume für Grafiken mit Zufallskantenlängen", Mathematik und Informatik, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, S. 223–245, HERR 1940139
  17. ^ Graham, R. L.; Hölle, Pavol (1985), "Über die Geschichte des Mindestproblems über Spanning Tree", Annalen der Geschichte des Computers, 7 (1): 43–57, doi:10.1109/mahc.1985.10011, HERR 0783327, S2CID 10555375
  18. ^ Nicos Christofides, Worst-Case-Analyse einer neuen Heuristik für das Problem des reisenden Verkäufers, Bericht 388, Graduate School of Industrial Administration, CMU, 1976.
  19. ^ Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. (August 1994). "Die Komplexität multitierter Schnitte" (PDF). Siam Journal über Computing. 23 (4): 864–894. doi:10.1137/s0097539792225297. Archiviert von das Original (PDF) am 24. August 2004. Abgerufen 17. Dezember 2012.
  20. ^ Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Heuristik für gewichtete perfekte Übereinstimmung. 12. jährliches ACM -Symposium über die Theorie des Computers (STOC '80). New York, NY, USA: ACM. S. 398–419. doi:10.1145/800141.804689.
  21. ^ Sneath, P. H. A. (1. August 1957). "Die Anwendung von Computern auf Taxonomie". Journal of General Microbiology. 17 (1): 201–226. doi:10.1099/00221287-17-1-201. PMID 13475686.
  22. ^ Asano, T.; Bhattacharya, b.; Keil, M.; Yao, F. (1988). Clustering -Algorithmen basierend auf minimalen und maximalen Spannbäumen. Viertes jährliches Symposium zur Computergeometrie (SCG '88). Vol. 1. S. 252–257. doi:10.1145/73393.73419.
  23. ^ Gower, J. C.; Ross, G. J. S. (1969). "Mindestüberschreitende Bäume und Clusteranalyse für ein Verknüpfung". Zeitschrift der Royal Statistical Society. C (angewandte Statistiken). 18 (1): 54–64. doi:10.2307/2346439. JStor 2346439.
  24. ^ Päivinen, Niina (1. Mai 2005). "Clustering mit einem minimalen Spannungsbaum aus skalierungsfreier Struktur". Mustererkennungsbuchstaben. 26 (7): 921–930. doi:10.1016/j.patrec.2004.09.039.
  25. ^ Xu, y.; Olman, V.; Xu, D. (1. April 2002). "Clustering-Genexpressionsdaten unter Verwendung eines graphentheoretischen Ansatzes: eine Anwendung von minimalen Spannungsbäumen". Bioinformatik. 18 (4): 536–545. doi:10.1093/bioinformatics/18.4.536. PMID 12016051.
  26. ^ Dalal, Yogen K.; Metcalfe, Robert M. (1. Dezember 1978). "Reverse Pfadweiterung von Broadcast -Paketen". Kommunikation der ACM. 21 (12): 1040–1048. doi:10.1145/359657.359665. S2CID 5638057.
  27. ^ Ma, b.; Held, a.; Gorman, J.; Michel, O. (2000). Bildregistrierung mit minimalem Spannungsbaumalgorithmus (PDF). Internationale Konferenz zur Bildverarbeitung. Vol. 1. S. 481–484. doi:10.1109/icip.2000.901000.
  28. ^ P. felzenszwalb, D. Huttenlocher: Effiziente grafische Bildsegmentierung. IJCV 59 (2) (September 2004)
  29. ^ Suk, Minsoo; Lied, Ohyoung (1. Juni 1984). "Kräuselle Merkmalextraktion mit minimalen Spannungsbäumen". Computer Vision, Grafik und Bildverarbeitung. 26 (3): 400–411. doi:10.1016/0734-189x (84) 90221-4.
  30. ^ Tapia, Ernesto; Rojas, Raúl (2004). "Erkennung von Online-handgeschriebenen mathematischen Ausdrücken unter Verwendung einer minimalen Spannungsbaumkonstruktion und Symboldominanz" (PDF). Grafikerkennung. Jüngste Fortschritte und Perspektiven. Vorlesungsnotizen in Informatik. Vol. 3088. Berlin Heidelberg: Springer-Verlag. S. 329–340. ISBN 978-3540224785.
  31. ^ Ohlsson, H. (2004). Implementierung von FIR -Filtern mit geringer Komplexität mit einem minimalen Spannungsbaum. 12. IEEE Mediterranean Electrotechnical Conference (MELECON 2004). Vol. 1. S. 261–264. doi:10.1109/melcon.2004.1346826.
  32. ^ Assunção, R. M.; M. C. Neves; G. Câmara; C. da Costa Freitas (2006). "Effiziente Regionalisierungstechniken für sozioökonomische geografische Einheiten unter Verwendung von Mindestspannungsbäumen". Internationales Journal of Geographical Information Science. 20 (7): 797–811. doi:10.1080/13658810600665111. S2CID 2530748.
  33. ^ Devillers, J.; Dore, J.C. (1. April 1989). "Heuristische Wirksamkeit der minimalen Spanning Tree (MST) -Methode in der Toxikologie". Ökotoxikologie und Umweltsicherheit. 17 (2): 227–235. doi:10.1016/0147-6513 (89) 90042-0. PMID 2737116.
  34. ^ Mori, H.; Tsuzuki, S. (1. Mai 1991). "Eine schnelle Methode zur topologischen Beobachtbarkeitsanalyse unter Verwendung einer minimalen Spannungsbaumtechnik". IEEE -Transaktionen auf Stromsystemen. 6 (2): 491–500. Bibcode:1991itpsie ... 6..491m. doi:10.1109/59.76691.
  35. ^ Filliben, James J.; Kafadar, Karen; Shier, Douglas R. (1. Januar 1983). "Tests auf Homogenität zweidimensionaler Oberflächen". Mathematische Modellierung. 4 (2): 167–189. doi:10.1016/0270-0255 (83) 90026-x.
  36. ^ Kalaba, Robert E. (1963), Graphentheorie und automatische Kontrolle (PDF), archiviert von das Original (PDF) am 21. Februar 2016
  37. ^ Mantegna, R. N. (1999). Hierarchische Struktur auf den Finanzmärkten. Das European Physical Journal B-Condensed Matter und komplexe Systeme, 11 (1), 193-197.
  38. ^ Djauhari, M. & Gan, S. (2015). Optimalitätsproblem der Netzwerk -Topologie in der Aktienmarktanalyse. Physica A: Statistische Mechanik und ihre Anwendungen, 419, 108-114.
  39. ^ Garey, Michael R.; Johnson, David S. (1979), Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung, W. H. Freeman, ISBN 0-7167-1045-5. Nd12
  40. ^ Gabow, Harold N. (1977), "Zwei Algorithmen zur Erzeugung gewichteter Spannungsbäume in Ordnung", Siam Journal über Computing, 6 (1): 139–150, doi:10.1137/0206011, HERR 0441784.
  41. ^ Eppstein, David (1992), "Finden Sie das k kleinste Spannbäume ", BISSCHEN, 32 (2): 237–248, doi:10.1007/bf01994879, HERR 1172188, S2CID 121160520.
  42. ^ Frederickson, Greg N. (1997), "Ambivalente Datenstrukturen für dynamische 2-Kanten-Konnektivität und k kleinste Spannbäume ", Siam Journal über Computing, 26 (2): 484–538, doi:10.1137/s0097539792226825, HERR 1438526.
  43. ^ Jothi, Raja; Raghavachari, Balaji (2005), "Approximationalgorithmen für das kapazitierte minimale Spanning -Baumproblem und seine Varianten im Netzwerkdesign", ACM trans. Algorithmen, 1 (2): 265–282, doi:10.1145/1103963.1103967, S2CID 8302085
  44. ^ Hu, T. C. (1961), "Das Problem der maximalen Kapazitätsroute", Unternehmensforschung, 9 (6): 898–900, doi:10.1287/Opre.9.6.898, JStor 167055.
  45. ^ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). "Nicht-projektive Abhängigkeitsanalyse mit Spanning-Baumalgorithmen" (PDF). Proc. HLT/EMNLP.
  46. ^ Spira, P. M.; Pan, A. (1975), "Über das Finden und Aktualisieren von Bäumen und kürzesten Wegen" (PDF), Siam Journal über Computing, 4 (3): 375–380, doi:10.1137/0204032, HERR 0378466.
  47. ^ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "Poly-logarithmische deterministische vollständig dynamische Algorithmen für Konnektivität, minimaler Spannungsbaum, 2-Kanten und Bikonnektivität", Journal of the Association for Computing Machinery, 48 (4): 723–760, doi:10.1145/502090.502095, HERR 2144928, S2CID 7273552.
  48. ^ Chin, F.; Houck, D. (1978), "Algorithmen zur Aktualisierung minimaler Spannungsbäume", Journal of Computer and System Sciences, 16 (3): 333–344, doi:10.1016/0022-0000 (78) 90022-3.
  49. ^ Chang, R.S.; Leu, S.J. (1997), "Die minimale Kennzeichnung über Bäume", " Informationsverarbeitungsbriefe, 63 (5): 277–282, doi:10.1016/s0020-0190 (97) 00127-0.
  50. ^ "Alles über Engpassspanning Tree". blinkende Gedanke.blogspot.ru. Abgerufen 4. April 2018.
  51. ^ "Archivierte Kopie" (PDF). Archiviert von das Original (PDF) Am 2013-06-12. Abgerufen 2014-07-02.{{}}: CS1 Wartung: Archiviertes Kopie als Titel (Link)

Weitere Lektüre

Externe Links