In diesem Artikel besprechen wir den Spanning Tree und den Minimum Spanning Tree. Bevor wir uns jedoch direkt dem Spanning Tree zuwenden, sehen wir uns zunächst eine kurze Beschreibung des Diagramms und seiner Typen an.
Graph
Ein Graph kann als eine Gruppe von Scheitelpunkten und Kanten definiert werden, um diese Scheitelpunkte zu verbinden. Die Diagrammtypen sind wie folgt angegeben:
Kommen wir nun zum Thema Spanning Tree.
Was ist ein Spannbaum?
Ein Spanning Tree kann als Teilgraph eines ungerichteten zusammenhängenden Graphen definiert werden. Es umfasst alle Eckpunkte zusammen mit der geringstmöglichen Anzahl von Kanten. Wenn ein Scheitelpunkt fehlt, handelt es sich nicht um einen Spanning Tree. Ein Spanning Tree ist eine Teilmenge des Graphen, die keine Zyklen hat und auch nicht getrennt werden kann.
Ein Spannbaum besteht aus (n-1) Kanten, wobei „n“ die Anzahl der Eckpunkte (oder Knoten) ist. Den Kanten des Spannbaums können Gewichtungen zugewiesen sein oder auch nicht. Alle möglichen Spannbäume, die aus dem gegebenen Graphen G erstellt werden, hätten die gleiche Anzahl an Eckpunkten, aber die Anzahl der Kanten im Spannbaum wäre gleich der Anzahl der Eckpunkte im gegebenen Graphen minus 1.
Ein vollständiger ungerichteter Graph kann haben Nn-2 Anzahl der Spannbäume wo N ist die Anzahl der Eckpunkte im Diagramm. Angenommen, wenn n = 5 , wäre die Anzahl der maximal möglichen Spannbäume 55-2= 125.
Anwendungen des Spannbaums
Grundsätzlich wird ein Spannbaum verwendet, um einen minimalen Pfad zum Verbinden aller Knoten des Diagramms zu finden. Einige der häufigsten Anwendungen des Spanning Tree sind wie folgt aufgeführt:
- Clusteranalyse
- Zivile Netzwerkplanung
- Routing-Protokoll für Computernetzwerke
Lassen Sie uns nun den Spanning Tree anhand eines Beispiels verstehen.
Beispiel für Spanning Tree
Angenommen, der Graph sei -
Wie oben erläutert, enthält ein Spanning Tree die gleiche Anzahl von Scheitelpunkten wie der Graph. Die Anzahl der Scheitelpunkte im obigen Graphen beträgt 5; Daher enthält der Spannbaum 5 Eckpunkte. Die Kanten im Spannbaum sind gleich der Anzahl der Eckpunkte im Diagramm minus 1. Es gibt also 4 Kanten im Spannbaum.
Einige der möglichen Spannbäume, die aus der obigen Grafik erstellt werden, sind wie folgt:
Eigenschaften von Spanning-Tree
Einige der Eigenschaften des Spannbaums sind wie folgt angegeben:
- Es kann mehr als einen aufspannenden Baum eines zusammenhängenden Graphen G geben.
- Ein Spanning Tree hat keine Zyklen oder Schleifen.
- Ein Spannbaum ist minimal verbunden, Wenn Sie also eine Kante aus dem Baum entfernen, wird die Verbindung des Diagramms unterbrochen.
- Ein Spannbaum ist maximal azyklisch, Wenn Sie also eine Kante zum Baum hinzufügen, entsteht eine Schleife.
- Es kann ein Maximum geben Nn-2 Anzahl der Spannbäume, die aus einem vollständigen Diagramm erstellt werden können.
- Ein Spannbaum hat n-1 Kanten, wobei „n“ die Anzahl der Knoten ist.
- Wenn der Graph ein vollständiger Graph ist, kann der Spannbaum durch Entfernen der maximalen (e-n+1) Kanten erstellt werden, wobei „e“ die Anzahl der Kanten und „n“ die Anzahl der Eckpunkte ist.
Ein Spannbaum ist also eine Teilmenge des verbundenen Graphen G, und es gibt keinen Spannbaum eines nicht zusammenhängenden Graphen.
Minimaler Spannbaum
Ein minimaler Spannbaum kann als der Spannbaum definiert werden, in dem die Summe der Gewichte der Kante minimal ist. Das Gewicht des Spannbaums ist die Summe der Gewichte, die den Kanten des Spannbaums gegeben werden. In der realen Welt kann dieses Gewicht als Entfernung, Verkehrsbelastung, Stau oder ein beliebiger Zufallswert betrachtet werden.
Beispiel für einen minimalen Spannbaum
Lassen Sie uns den minimalen Spannbaum anhand eines Beispiels verstehen.
Die Summe der Kanten des obigen Diagramms beträgt 16. Nun sind einige der möglichen Spannbäume, die aus dem obigen Diagramm erstellt wurden:
Der minimale Spannbaum, der aus den oben genannten Spannbäumen für den gegebenen gewichteten Graphen ausgewählt wird, ist also –
Anwendungen des minimalen Spannbaums
Die Anwendungen des minimalen Spannbaums sind wie folgt angegeben:
- Der minimale Spannbaum kann zum Entwurf von Wasserversorgungsnetzen, Telekommunikationsnetzen und Stromnetzen verwendet werden.
- Damit lassen sich Wege in der Karte finden.
Algorithmen für den minimalen Spannbaum
Mithilfe der unten angegebenen Algorithmen kann aus einem gewichteten Diagramm ein minimaler Spannbaum ermittelt werden:
- Prims Algorithmus
- Kruskals Algorithmus
Sehen wir uns eine kurze Beschreibung der beiden oben aufgeführten Algorithmen an.
Prims Algorithmus - Es handelt sich um einen gierigen Algorithmus, der mit einem leeren Spanning Tree beginnt. Es wird verwendet, um den minimalen Spannbaum aus dem Diagramm zu ermitteln. Dieser Algorithmus findet die Teilmenge der Kanten, die jeden Scheitelpunkt des Diagramms umfasst, sodass die Summe der Gewichte der Kanten minimiert werden kann.
Minimal Maximal
Um mehr über den Algorithmus des Prims zu erfahren, können Sie auf den folgenden Link klicken: https://www.javatpoint.com/prim-algorithm
Kruskals Algorithmus - Dieser Algorithmus wird auch verwendet, um den minimalen Spannbaum für einen verbundenen gewichteten Graphen zu finden. Kruskals Algorithmus folgt auch dem Greedy-Ansatz, der in jeder Phase eine optimale Lösung findet, anstatt sich auf ein globales Optimum zu konzentrieren.
Um mehr über den Algorithmus des Prims zu erfahren, können Sie auf den folgenden Link klicken: https://www.javatpoint.com/kruskal-algorithm
Das ist also alles über den Artikel. Ich hoffe, der Artikel ist hilfreich und informativ für Sie. Hier haben wir Spanning Tree und Minimum Spanning Tree zusammen mit ihren Eigenschaften, Beispielen und Anwendungen besprochen.