In diesem Tutorial lernen Sie anhand von Beispielen und Abbildungen den Spanning Tree und den Minimum Spanning Tree kennen.
Bevor wir lernen, wie man Bäume überspannt, müssen wir zwei Diagramme verstehen: ungerichtete Diagramme und verbundene Diagramme.
Ein ungerichteter Graph ist ein Graph, in dem die Kanten in keine Richtung zeigen (dh die Kanten sind bidirektional).

Ein verbundener Graph ist ein Graph, in dem es immer einen Pfad von einem Scheitelpunkt zu einem anderen Scheitelpunkt gibt.

Spanning Tree
Ein Spanning Tree ist ein Untergraph eines ungerichteten verbundenen Graphen, der alle Eckpunkte des Graphen mit einer möglichst geringen Anzahl von Kanten enthält. Wenn ein Scheitelpunkt übersehen wird, handelt es sich nicht um einen Spannbaum.
Den Kanten können Gewichte zugewiesen sein oder nicht.
Die Gesamtzahl der Spannbäume mit n
Eckpunkten, die aus einem vollständigen Diagramm erstellt werden können, entspricht .n(n-2)
Wenn ja n = 4
, ist die maximale Anzahl möglicher Spannbäume gleich . Somit können 16 überspannende Bäume aus einem vollständigen Graphen mit 4 Eckpunkten gebildet werden.44-2
= 16
Beispiel eines Spanning Tree
Lassen Sie uns den Spanning Tree anhand der folgenden Beispiele verstehen:
Das ursprüngliche Diagramm sei:

Einige der möglichen Spannbäume, die aus dem obigen Diagramm erstellt werden können, sind:






Minimum Spanning Tree
Ein minimaler Spannbaum ist ein Spannbaum, bei dem die Summe des Gewichts der Kanten so gering wie möglich ist.
Beispiel eines Spanning Tree
Lassen Sie uns die obige Definition anhand des folgenden Beispiels verstehen.
Das erste Diagramm lautet:

Die möglichen Spannbäume aus der obigen Grafik sind:




Der minimale Spannbaum von den oben genannten Spannbäumen ist:

Der minimale Spannbaum aus einem Diagramm wird mithilfe der folgenden Algorithmen ermittelt:
- Prims Algorithmus
- Kruskals Algorithmus
Spanning Tree-Anwendungen
- Computer Network Routing Protocol
- Clusteranalyse
- Planung des zivilen Netzwerks
Minimum Spanning Tree-Anwendungen
- Pfade in der Karte finden
- Entwerfen von Netzen wie Telekommunikationsnetzen, Wasserversorgungsnetzen und Stromnetzen.