1. Was ist Baum und Wald?
Baum
- In der Graphentheorie a Baum ist ein ungerichteter, zusammenhängender und azyklischer Graph . Mit anderen Worten: Ein zusammenhängender Graph, der nicht einmal einen einzigen Zyklus enthält, wird Baum genannt.
- Ein Baum stellt eine hierarchische Struktur in grafischer Form dar.
- Die Elemente von Bäumen werden als Knoten bezeichnet und die Kanten des Baums werden als Äste bezeichnet.
- Ein Baum mit n Eckpunkten hat (n-1) Kanten.
- Bäume bieten viele nützliche Anwendungen, von einfachen Stammbäumen bis hin zu komplexen Bäumen in Datenstrukturen der Informatik.
- A Blatt In einem Baum gibt es einen Scheitelpunkt vom Grad 1, oder jeder Scheitelpunkt, der keine Kinder hat, wird Blatt genannt.
Beispiel
Im obigen Beispiel handelt es sich bei allen um Bäume mit weniger als 6 Eckpunkten.
Tojson Java
Wald
In der Graphentheorie a Wald Ist ein ungerichteter, unzusammenhängender, azyklischer Graph . Mit anderen Worten: Eine disjunkte Ansammlung von Bäumen wird als Wald bezeichnet. Jeder Bestandteil eines Waldes ist ein Baum.
Beispiel
Das obige Diagramm sieht aus wie zwei Unterdiagramme, es handelt sich jedoch um ein einzelnes, nicht zusammenhängendes Diagramm. In der obigen Grafik gibt es keine Zyklen. Daher ist es ein Wald.
2. Eigenschaften von Bäumen
- Jeder Baum, der mindestens zwei Spitzen hat, sollte mindestens zwei Blätter haben.
- Bäume haben viele Charakterisierungen:
Sei T ein Graph mit n Eckpunkten, dann sind die folgenden Aussagen äquivalent:- T ist ein Baum.
- T enthält keine Zyklen und hat n-1 Kanten.
- T ist zusammenhängend und hat (n -1) Kante.
- T ist ein zusammenhängender Graph und jede Kante ist eine Schnittkante.
- Zwei beliebige Eckpunkte des Graphen T sind durch genau einen Pfad verbunden.
- T enthält keine Zyklen und für jede neue Kante e hat der Graph T+e genau einen Zyklus.
- Jede Kante eines Baumes ist beschnitten.
- Das Hinzufügen einer Kante zu einem Baum definiert genau einen Zyklus.
- Jeder verbundene Graph enthält einen Spannbaum.
- Jeder Baum hat mindestens zwei Knoten vom Grad zwei.
3. Spanning Tree
A Spannbaum In einem zusammenhängenden Graphen ist G ein Untergraph H von G, der alle Eckpunkte von G enthält und außerdem ein Baum ist.
Beispiel
Betrachten Sie die folgende Grafik G:
Aus dem obigen Diagramm G können wir die folgenden drei Spannbäume H implementieren:
Java-String eines Arrays
Methoden zum Finden des Spanning Tree
Wir können den Spanning Tree systematisch finden, indem wir eine von zwei Methoden verwenden:
- Reduziermethode
- Aufbaumethode
1. Reduziermethode
- Beginnen Sie mit der Auswahl eines beliebigen Zyklus in Grafik G.
- Entfernen Sie eine der Kanten des Zyklus.
- Wiederholen Sie diesen Vorgang, bis keine Zyklen mehr vorhanden sind.
Beispiel
- Betrachten Sie einen Graphen G,
- Wenn wir die Kante ac entfernen, die den Zyklus a-d-c-a im obigen Diagramm zerstört, erhalten wir das folgende Diagramm:
- Entfernen Sie die Kante cb, die den Zyklus a-d-c-b-a aus dem obigen Diagramm zerstört, dann erhalten wir das folgende Diagramm:
- Wenn wir die Kante ec entfernen, die den Zyklus d-e-c-d aus dem obigen Diagramm zerstört, erhalten wir den folgenden Spannbaum:
2. Aufbaumethode
- Wählen Sie nacheinander die Kanten des Diagramms G aus. So dass keine Kreisläufe entstehen.
- Wiederholen Sie diesen Vorgang, bis alle Eckpunkte enthalten sind.
Beispiel
Betrachten Sie den folgenden Graphen G:
- Wählen Sie die Kante ab ,
- Wählen Sie die Kante von ,
- Wählen Sie anschließend die Kante aus ec ,
- Wählen Sie als Nächstes die Kante aus cb , dann erhalten wir schließlich den folgenden Spannbaum:
Schaltungsrang
Die Anzahl der Kanten, die wir aus G löschen müssen, um einen Spannbaum zu erhalten.
Spannender Baum G = m- (n-1) , das heißt Schaltungsrang von G.
Where, m = No. of edges. n = No. of vertices.
Beispiel
Im obigen Diagramm sind die Kanten m = 7 und die Eckpunkte n = 5
öffne eine Datei mit Java
Dann ist der Schaltungsrang:
G = m - (n - 1) = 7 - (5 - 1) = 3