Spanning Tree und Minimum Spanning Tree

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).

Ungerichteter Graph

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

Verbundenes Diagramm

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 nEckpunkten, 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:

Normaler Graph

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

Ein Spannbaum Ein Spannbaum Ein Spannbaum Ein Spannbaum Ein Spannbaum Ein Spannbaum Ein Spannbaum

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:

Gewichteter Graph

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

Minimaler Spannbaum - 1 Minimaler Spannbaum - 2 Minimaler Spannbaum - 3 Minimaler Spannbaum - 4

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

Minimaler Spannbaum

Der minimale Spannbaum aus einem Diagramm wird mithilfe der folgenden Algorithmen ermittelt:

1. Prims Algorithmus
2. 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.