Spannender Baum - Spanning tree

Ein aufspannender Baum (blaue schwere Kanten) eines Gittergraphen

Auf dem mathematischen Gebiet der Graphentheorie ist ein aufspannender Baum T eines ungerichteten Graphen G ein Untergraph, der ein Baum ist, der alle Ecken von G enthält . Im Allgemeinen kann ein Graph mehrere Spannbäume haben, aber ein Graph, der nicht verbunden ist, enthält keinen Spannbaum (siehe Spannen von Wäldern weiter unten). Wenn alle Kanten von G auch Kanten eines aufspannenden Baums T von G sind , dann ist G ein Baum und identisch mit T (dh ein Baum hat einen eindeutigen aufspannenden Baum und ist er selbst).

Anwendungen

Mehrere Pfadfindungsalgorithmen , darunter der Dijkstra-Algorithmus und der A*-Suchalgorithmus , bauen intern einen Spannbaum als Zwischenschritt bei der Lösung des Problems auf.

Um die Kosten von Stromnetzen, Kabelverbindungen, Rohrleitungen, automatischer Spracherkennung usw. zu minimieren, werden häufig Algorithmen verwendet, die nach und nach einen Spannbaum (oder viele solcher Bäume) als Zwischenschritte beim Finden des minimalen Spannbaums aufbauen build .

Das Internet und viele andere Telekommunikationsnetze haben Übertragungsverbindungen, die Knoten in einer Maschentopologie , die einige Schleifen enthält, miteinander verbinden. Um Bridge-Loops und Routing-Loops zu vermeiden, erfordern viele Routing-Protokolle, die für solche Netzwerke entwickelt wurden – einschließlich Spanning Tree Protocol , Open Shortest Path First , Link-State-Routing-Protokoll , Augmented Tree-based Routing usw spannender Baum.

Eine besondere Art von Spannbaum, der Xuong-Baum , wird in der topologischen Graphentheorie verwendet , um Grapheneinbettungen mit maximaler Gattung zu finden . Ein Xuong-Baum ist ein aufspannender Baum, so dass im verbleibenden Graphen die Anzahl der Zusammenhangskomponenten mit ungerader Kantenzahl möglichst klein ist. Ein Xuong-Baum und eine zugehörige Maximum-Genus-Einbettung können in polynomieller Zeit gefunden werden .

Definitionen

Ein Baum ist ein zusammenhängender ungerichteter Graph ohne Zyklen . Er ist ein aufspannender Baum eines Graphen G, wenn er G überspannt (dh er enthält jede Ecke von G ) und ein Untergraph von G ist (jede Kante im Baum gehört zu G ). Ein aufspannender Baum eines zusammenhängenden Graphen G kann auch als eine maximale Menge von Kanten von G definiert werden , die keinen Kreis enthält, oder als eine minimale Menge von Kanten, die alle Knoten verbinden.

Grundlegende Zyklen

Das Hinzufügen von nur einer Kante zu einem Spannbaum erzeugt einen Zyklus; ein solcher Zyklus wird als Fundamentalzyklus bezeichnet . Für jede Kante, die nicht im Spannbaum ist, gibt es einen eigenen fundamentalen Zyklus; somit gibt es eine Eins-zu-Eins-Entsprechung zwischen Fundamentalzyklen und Kanten, die sich nicht im Spannbaum befinden. Für einen zusammenhängenden Graphen mit V Knoten hat jeder aufspannende Baum V  − 1 Kanten, und somit hat ein Graph mit E Kanten und einer seiner aufspannenden Bäume E  −  V  + 1 Fundamentalzyklen (Die Anzahl der Kanten subtrahiert von der Anzahl von Kanten, die in einem Spannbaum enthalten sind; gibt die Anzahl der Kanten an, die nicht im Spannbaum enthalten sind). Für einen gegebenen aufspannenden Baum bildet die Menge aller E  −  V  + 1 Fundamentalzyklen eine Zyklenbasis , eine Basis für den Zyklenraum .

Grundlegende Cutsets

Dual zum Begriff eines fundamentalen Zyklus ist der Begriff eines fundamentalen Cutsets . Durch das Löschen nur einer Kante des Spannbaums werden die Knoten in zwei disjunkte Mengen aufgeteilt. Die fundamentale Schnittmenge ist definiert als die Menge von Kanten, die aus dem Graphen G entfernt werden müssen, um dieselbe Partition zu erreichen. Somit definiert jeder Spannbaum eine Menge von V  − 1 fundamentalen Schnittmengen, eine für jede Kante des Spannbaums.

Die Dualität zwischen fundamentalen Cutsets und fundamentalen Zyklen wird dadurch begründet, dass Zyklenkanten, die sich nicht im Spannbaum befinden, nur in den Cutsets der anderen Kanten im Zyklus auftreten können; und umgekehrt : Kanten in einem Cutset können nur in den Zyklen erscheinen, die die dem Cutset entsprechende Kante enthalten. Diese Dualität kann auch unter Verwendung der Theorie der ausgedrückt werden Matroide , wonach ein Spanning Tree eine Base der ist Grafik Matroid , ist ein Grundzyklus der einzigartige Schaltung innerhalb des Satzes , der durch ein Element auf der Basis Hinzufügen und Grund cutsets definiert in gleicher Weise vom dualen Matroid .

Durch Wälder

In Graphen, die nicht verbunden sind, kann es keinen Spanning Tree geben, und man muss stattdessen Spanning Forests in Betracht ziehen . Hier gibt es zwei konkurrierende Definitionen:

  • Einige Autoren betrachten einen Spannwald als einen maximalen azyklischen Teilgraphen des gegebenen Graphen oder äquivalent als einen Graphen, der aus einem Spannbaum in jeder zusammenhängenden Komponente des Graphen besteht.
  • Für andere Autoren ist ein aufspannender Wald ein Wald, der alle Scheitelpunkte überspannt, was bedeutet, dass nur jeder Scheitelpunkt des Graphen ein Scheitelpunkt im Wald ist. Für diese Definition kann sogar ein verbundener Graph einen nicht zusammenhängenden aufspannenden Wald haben, wie beispielsweise den Wald, in dem jeder Scheitelpunkt einen Baum mit einem einzelnen Scheitelpunkt bildet.

Um Verwechslungen zwischen diesen beiden Definitionen zu vermeiden, schlagen Gross & Yellen (2005) den Begriff "Full Spanning Forest" für einen Spanning Forest mit der gleichen Konnektivität wie der gegebene Graph vor, während Bondy & Murty (2008) diese Art von Forest stattdessen als " maximal aufspannender Wald".

Spannende Bäume zählen

Die Formel von Cayley zählt die Anzahl der aufspannenden Bäume in einem vollständigen Graphen. Da sind Bäume drin , Bäume drin und Bäume drin .

Die Anzahl t ( G ) aufspannender Bäume eines zusammenhängenden Graphen ist eine gut untersuchte Invariante .

In bestimmten Grafiken

In einigen Fällen ist es einfach, t ( G ) direkt zu berechnen :

  • Ist G selbst ein Baum, dann ist t ( G ) = 1 .
  • Wenn G der Kreisgraph C n mit n Ecken ist, dann ist t ( G ) =  n .
  • Für einen vollständigen Graphen mit n Knoten gibt die Formel von Cayley die Anzahl der aufspannenden Bäume als n n  − 2 an .
  • Wenn G der vollständige bipartite Graph ist , dann .
  • Für den n- dimensionalen Hyperwürfel-Graphen beträgt die Anzahl der aufspannenden Bäume .

In beliebigen Graphen

Allgemeiner kann für jeden Graphen G die Zahl t ( G ) in polynomieller Zeit als Determinante einer aus dem Graphen abgeleiteten Matrix unter Verwendung des Matrix-Baum-Theorems von Kirchhoff berechnet werden .

Um t ( G ) zu berechnen , konstruiert man insbesondere die Laplace-Matrix des Graphen, eine quadratische Matrix, in der die Zeilen und Spalten beide durch die Scheitelpunkte von G indiziert sind . Der Eintrag in Zeile i und Spalte j ist einer von drei Werten:

  • Der Vertexgrad i , wenn i  =  j ,
  • −1, wenn die Ecken i und j benachbart sind, oder
  • 0, wenn die Scheitelpunkte i und j voneinander verschieden, aber nicht benachbart sind.

Die resultierende Matrix ist singulär , also ist ihre Determinante null. Das Löschen von Zeile und Spalte für eine willkürlich gewählte Ecke führt jedoch zu einer kleineren Matrix, deren Determinante genau  t ( G ) ist.

Löschung-Kontraktion

Ist G ein Graph oder Multigraph und e eine beliebige Kante von G , dann erfüllt die Anzahl t ( G ) aufspannender Bäume von G die Deletion-Kontraktions-Rekursion t ( G ) =  t ( G  −  e ) +  t ( G / e ), wobei G  −  e der Multigraph ist, der durch das Löschen von e erhalten wird und G / e die Kontraktion von G um e ist . Der Term t ( G  −  e ) in dieser Formel zählt die aufspannenden Bäume von  G , die keine Kante  e verwenden , und der Term t ( G / e ) zählt die aufspannenden Bäume von  G , die  e verwenden .

Wenn in dieser Formel der gegebene Graph G ein Multigraph ist oder eine Kontraktion dazu führt, dass zwei Ecken durch mehrere Kanten miteinander verbunden werden, sollten die redundanten Kanten nicht entfernt werden, da dies zu einer falschen Summe führen würde. Zum Beispiel hat ein Bindungsgraph , der zwei Knoten durch k Kanten verbindet, k verschiedene aufspannende Bäume, die jeweils aus einer einzigen dieser Kanten bestehen.

Tutte-Polynom

Das Tutte-Polynom eines Graphen kann als eine Summe über die aufspannenden Bäume des Graphen von Termen definiert werden, die aus der "internen Aktivität" und der "externen Aktivität" des Baums berechnet wurden. Sein Wert an den Argumenten (1,1) ist die Anzahl der aufspannenden Bäume oder, in einem nicht zusammenhängenden Graphen, die Anzahl der maximalen aufspannenden Wälder.

Das Tutte-Polynom kann auch mit einer Deletion-Contraction-Recurrence berechnet werden, aber seine Rechenkomplexität ist hoch: Für viele Werte seiner Argumente ist seine exakte Berechnung #P-complete , und es ist auch schwer, mit einem garantierten Approximationsverhältnis zu approximieren . Der Punkt (1,1), an dem er mit dem Kirchhoffschen Theorem ausgewertet werden kann, ist eine der wenigen Ausnahmen.

Algorithmen

Konstruktion

Ein einzelner aufspannender Baum eines Graphen kann in linearer Zeit entweder durch Tiefensuche oder Breitensuche gefunden werden . Beide dieser Algorithmen untersuchen den gegebenen Graphen ausgehend von einem beliebigen Knoten v , indem sie die Nachbarn der von ihnen entdeckten Knoten durchlaufen und jeden unerforschten Nachbarn zu einer später zu untersuchenden Datenstruktur hinzufügen. Sie unterscheiden sich darin, ob diese Datenstruktur ein Stack (bei der Tiefensuche) oder eine Warteschlange (bei der Breitensuche) ist. In jedem Fall kann man einen Spannbaum bilden, indem man jeden anderen Scheitel als den Wurzelscheitel v mit dem Scheitel verbindet, von dem er entdeckt wurde. Dieser Baum ist als Tiefensuchbaum oder Breitensuchbaum bekannt, entsprechend dem Graphen-Explorationsalgorithmus, der verwendet wird, um ihn zu erstellen. Tiefensuchbäume sind ein Sonderfall einer Klasse von Spannbäumen, die als Trémaux-Bäume bezeichnet werden und nach dem Entdecker der Tiefensuche im 19. Jahrhundert benannt wurden.

Spanning Trees sind wichtig beim parallelen und verteilten Rechnen, um die Kommunikation zwischen einer Reihe von Prozessoren aufrechtzuerhalten; siehe zum Beispiel das Spanning Tree Protocol, das von OSI-Link-Layer- Geräten verwendet wird, oder das Shout (Protokoll) für verteiltes Rechnen. Die Tiefen-zuerst- und Breiten-zuerst-Verfahren zum Konstruieren von Spannbäumen auf sequentiellen Computern sind jedoch für parallele und verteilte Computer nicht gut geeignet. Stattdessen haben Forscher mehrere spezialisiertere Algorithmen entwickelt, um Spannbäume in diesen Berechnungsmodellen zu finden.

Optimierung

In bestimmten Gebieten der Graphentheorie ist es oft nützlich, einen minimalen Spannbaum eines gewichteten Graphen zu finden . Es wurden auch andere Optimierungsprobleme auf Spannbäumen untersucht, darunter der maximale Spannbaum, der minimale Baum, der mindestens k Knoten überspannt , der Spannbaum mit den wenigsten Kanten pro Knoten , der Spannbaum mit der größten Anzahl von Blättern , der Spannbaum mit den wenigsten Blättern (in engem Zusammenhang mit dem Hamiltonschen Pfadproblem ), dem Spannbaum mit minimalem Durchmesser und dem Spannbaum mit minimaler Dilatation.

Optimale Spannbaumprobleme wurden auch für endliche Punktmengen in einem geometrischen Raum wie der euklidischen Ebene untersucht . Für eine solche Eingabe ist ein aufspannender Baum wiederum ein Baum, der als Eckpunkte die gegebenen Punkte hat. Die Qualität des Baums wird auf die gleiche Weise wie in einem Graphen gemessen, wobei der euklidische Abstand zwischen Punktpaaren als Gewicht für jede Kante verwendet wird. So ist zum Beispiel ein euklidischer minimaler Spannbaum dasselbe wie ein minimaler Spannbaum eines Graphen in einem vollständigen Graphen mit euklidischen Kantengewichten. Es ist jedoch nicht notwendig, diesen Graphen zu konstruieren, um das Optimierungsproblem zu lösen; das Problem des euklidischen minimalen Spannbaums kann zum Beispiel effizienter in O ( n  log  n ) Zeit gelöst werden, indem die Delaunay-Triangulation konstruiert wird und dann ein minimaler Spannbaum-Algorithmus für lineare Zeitplanargraphen auf die resultierende Triangulation angewendet wird.

Randomisierung

Ein zufällig aus allen aufspannenden Bäumen mit gleicher Wahrscheinlichkeit ausgewählter Spannbaum wird als einheitlicher Spannbaum bezeichnet . Wilsons Algorithmus kann verwendet werden, um in polynomieller Zeit gleichförmige Spannbäume zu erzeugen, indem man einen zufälligen Spaziergang auf dem gegebenen Graphen macht und die durch diesen Spaziergang erzeugten Zyklen löscht.

Ein alternatives Modell zum zufälligen, aber nicht einheitlichen Erzeugen von Spannbäumen ist der zufällige minimale Spannbaum . In diesem Modell werden den Kanten des Graphen zufällige Gewichte zugewiesen und dann wird der minimale Spannbaum des gewichteten Graphen konstruiert.

Aufzählung

Da ein Graph exponentiell viele aufspannende Bäume haben kann, ist es nicht möglich, sie alle in polynomieller Zeit aufzulisten . Es sind jedoch Algorithmen bekannt, um alle aufspannenden Bäume in polynomieller Zeit pro Baum aufzulisten.

In unendlichen Graphen

Jeder endliche zusammenhängende Graph hat einen aufspannenden Baum. Für unendlich zusammenhängende Graphen ist die Existenz aufspannender Bäume jedoch äquivalent zum Auswahlaxiom . Ein unendlicher Graph ist verbunden, wenn jedes seiner Knotenpaare das Endpunktpaar eines endlichen Pfades bildet. Wie bei endlichen Graphen ist ein Baum ein zusammenhängender Graph ohne endliche Kreise, und ein aufspannender Baum kann entweder als maximale azyklische Menge von Kanten oder als Baum definiert werden, der jeden Knoten enthält.

Die Bäume innerhalb eines Graphen können teilweise nach ihrer Untergraphenbeziehung geordnet sein, und jede unendliche Kette in dieser Teilordnung hat eine obere Schranke (die Vereinigung der Bäume in der Kette). Das Lemma von Zorn , eine von vielen äquivalenten Aussagen zum Auswahlaxiom, erfordert, dass eine partielle Ordnung, in der alle Ketten nach oben beschränkt sind, ein maximales Element hat; in der partiellen Ordnung auf den Bäumen des Graphen muss dieses maximale Element ein aufspannender Baum sein. Wenn also das Lemma von Zorn angenommen wird, hat jeder unendliche zusammenhängende Graph einen aufspannenden Baum.

Umgekehrt ist es bei einer gegebenen Mengenfamilie möglich, einen unendlichen Graphen so zu konstruieren, dass jeder aufspannende Baum des Graphen einer Auswahlfunktion der Mengenfamilie entspricht . Wenn also jeder unendliche zusammenhängende Graph einen aufspannenden Baum hat, dann ist das Auswahlaxiom wahr.

In gerichteten Multigraphen

Die Idee eines Spannbaums lässt sich auf gerichtete Multigraphen verallgemeinern. Bei einem gegebenen Eckpunkt v auf einer gerichteten Multigraph G , eine orientierte Spannbaum T an wurzelt v eine acyclische Graph von G , in dem jeder Knoten außer v outdegree 1. Diese Definition hat , ist nur erfüllt , wenn die „Zweige“ des T Punkt in Richtung v .

Siehe auch

Verweise