Datenstruktur & Algorithmen - Spanning Tree

Ein Spanning Tree ist eine Teilmenge von Graph G, bei der alle Eckpunkte mit einer möglichst geringen Anzahl von Kanten abgedeckt sind. Daher hat ein Spanning Tree keine Zyklen und kann nicht getrennt werden.

Durch diese Definition können wir den Schluss ziehen, dass jeder verbundene und ungerichtete Graph G mindestens einen Spannbaum hat. Ein nicht verbundener Graph hat keinen Spanning Tree, da er nicht auf alle seine Eckpunkte gespannt werden kann.

Wir fanden drei überspannende Bäume in einem vollständigen Diagramm. Ein vollständiger ungerichteter Graph kann maximal seinn^n-2 Anzahl der überspannenden Bäume, wo nist die Anzahl der Knoten. In dem oben angesprochenen Beispiel istn is 3, daher 3³⁻² = 3 Spannbäume sind möglich.

Allgemeine Eigenschaften von Spanning Tree

Wir verstehen jetzt, dass ein Graph mehr als einen Spanning Tree haben kann. Im Folgenden sind einige Eigenschaften des Spanning Tree aufgeführt, die mit dem Diagramm G verbunden sind.

Ein verbundener Graph G kann mehr als einen Spannbaum haben.
Alle möglichen Spannbäume des Graphen G haben die gleiche Anzahl von Kanten und Eckpunkten.
Der Spanning Tree hat keinen Zyklus (Schleifen).
Wenn Sie eine Kante aus dem Spanning Tree entfernen, wird das Diagramm getrennt, dh der Spanning Tree ist minimally connected.
Durch Hinzufügen einer Kante zum Spanning Tree wird eine Schaltung oder Schleife erstellt, dh der Spanning Tree ist maximally acyclic.

Mathematische Eigenschaften von Spanning Tree

Spanning Tree hat n-1 Kanten, wo n ist die Anzahl der Knoten (Eckpunkte).
Aus einem vollständigen Diagramm durch Entfernen des Maximums e - n + 1 Kanten können wir einen Spannbaum konstruieren.
Ein vollständiger Graph kann maximal sein n^n-2 Anzahl der überspannenden Bäume.

Wir können daher den Schluss ziehen, dass Spanning Tree eine Teilmenge des verbundenen Graphen G ist und getrennte Graphen keinen Spanning Tree haben.

Anwendung von Spanning Tree

Spanning Tree wird im Wesentlichen verwendet, um einen Mindestpfad für die Verbindung aller Knoten in einem Diagramm zu finden. Übliche Anwendung von Spannbäumen sind -

Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis

Lassen Sie uns dies anhand eines kleinen Beispiels verstehen. Betrachten Sie das Stadtnetz als ein riesiges Diagramm und planen Sie nun, Telefonleitungen so bereitzustellen, dass wir mit minimalen Leitungen eine Verbindung zu allen Stadtknoten herstellen können. Hier kommt der Spannbaum ins Spiel.

Minimum Spanning Tree (MST)

In einem gewichteten Diagramm ist ein minimaler Spannbaum ein Spannbaum, der ein minimales Gewicht hat als alle anderen Spannbäume desselben Graphen. In realen Situationen kann dieses Gewicht als Entfernung, Überlastung, Verkehrslast oder ein beliebiger Wert gemessen werden, der an den Kanten angegeben wird.