Diskrete Mathematik - Bäume überspannen

Ein Spanning Tree eines verbundenen ungerichteten Graphen $ G $ ist ein Baum, der minimal alle Eckpunkte von $ G $ enthält. Ein Graph kann viele überspannende Bäume haben.

Beispiel

Minimum Spanning Tree

Ein Spanning Tree mit einem zugewiesenen Gewicht, das kleiner oder gleich dem Gewicht jedes möglichen Spanning Tree eines gewichteten, verbundenen und ungerichteten Graphen $ G $ ist, wird als Minimum Spanning Tree (MST) bezeichnet. Das Gewicht eines Spannbaums ist die Summe aller Gewichte, die jeder Kante des Spannbaums zugewiesen sind.

Beispiel

Kruskals Algorithmus

Der Kruskal-Algorithmus ist ein gieriger Algorithmus, der einen minimalen Spannbaum für einen verbundenen gewichteten Graphen findet. Es wird ein Baum dieses Diagramms gefunden, der jeden Scheitelpunkt enthält, und das Gesamtgewicht aller Kanten im Baum ist kleiner oder gleich jedem möglichen Spannbaum.

Algorithmus

Step 1 - Ordnen Sie alle Kanten des angegebenen Graphen $ G (V, E) $ in aufsteigender Reihenfolge nach ihrem Kantengewicht an.

Step 2 - Wählen Sie die kleinste gewichtete Kante aus dem Diagramm aus und prüfen Sie, ob sie mit dem bisher gebildeten Spannbaum einen Zyklus bildet.

Step 3 - Wenn es keinen Zyklus gibt, fügen Sie diese Kante in den Spanning Tree ein, andernfalls verwerfen Sie sie.

Step 4 - Wiederholen Sie Schritt 2 und Schritt 3, bis $ (V-1) $ Anzahl der Kanten im Spanning Tree verbleibt.

Problem

Angenommen, wir möchten den minimalen Spannbaum für den folgenden Graphen G unter Verwendung des Kruskal-Algorithmus finden.

Solution

Aus der obigen Grafik konstruieren wir die folgende Tabelle:

Rand Nr. Scheitelpunktpaar Kantengewicht
E1 (a, b) 20
E2 (a, c) 9
E3 (Anzeige) 13
E4 (b, c) 1
E5 (Sein) 4
E6 (b, f) 5
E7 (c, d) 2
E8 (d, e) 3
E9 (d, f) 14

Jetzt werden wir die Tabelle in aufsteigender Reihenfolge in Bezug auf das Kantengewicht neu anordnen -

Rand Nr. Scheitelpunktpaar Kantengewicht
E4 (b, c) 1
E7 (c, d) 2
E8 (d, e) 3
E5 (Sein) 4
E6 (b, f) 5
E2 (a, c) 9
E3 (Anzeige) 13
E9 (d, f) 14
E1 (a, b) 20

Da wir in der letzten Abbildung alle 5 Kanten erhalten haben, stoppen wir den Algorithmus. Dies ist der minimale Spannbaum und sein Gesamtgewicht beträgt $ (1 + 2 + 3 + 5 + 9) = 20 $.

Prims Algorithmus

Prims Algorithmus, der 1930 von den Mathematikern Vojtech Jarnik und Robert C. Prim entdeckt wurde, ist ein gieriger Algorithmus, der einen minimalen Spannbaum für einen verbundenen gewichteten Graphen findet. Es wird ein Baum dieses Diagramms gefunden, der jeden Scheitelpunkt enthält, und das Gesamtgewicht aller Kanten im Baum ist kleiner oder gleich jedem möglichen Spannbaum. Prims Algorithmus ist in dichten Graphen schneller.

Algorithmus

  • Initialisieren Sie den minimalen Spannbaum mit einem einzelnen Scheitelpunkt, der zufällig aus dem Diagramm ausgewählt wird.

  • Wiederholen Sie die Schritte 3 und 4, bis alle Scheitelpunkte im Baum enthalten sind.

  • Wählen Sie eine Kante aus, die den Baum mit einem Scheitelpunkt verbindet, der sich noch nicht im Baum befindet, sodass das Gewicht der Kante minimal ist und die Einbeziehung der Kante keinen Zyklus bildet.

  • Fügen Sie die ausgewählte Kante und den Scheitelpunkt hinzu, den sie mit dem Baum verbindet.

Problem

Angenommen, wir möchten den minimalen Spannbaum für den folgenden Graphen G unter Verwendung des Prim-Algorithmus finden.

Solution

Hier beginnen wir mit dem Scheitelpunkt 'a' und fahren fort.

Dies ist der minimale Spannbaum und sein Gesamtgewicht beträgt $ (1 + 2 + 3 + 5 + 9) = 20 $.