Hallo, wir machen weiter mit Grafen und zwar werden wir uns über sogenannte minimale aufspannende

Bäume unterhalten.

Dazu möchte ich mal ganz kurz wiederholen, was eigentlich Bäume nochmal sind.

Ein Baum ist ein art simplischer, ungerichteter, zusammenhängender Graf.

Also das hier ist zum Beispiel ein Graf, aber es ist kein Baum.

Also ein Baum, jetzt nehmen wir die gleichen Knoten wie hier.

Was könnte ein Baum sein?

Also zum Beispiel das hier ist ein Baum, denn der ist nicht zyklisch, weil wir hier keinen

Pfad finden können, der in Kreisen ist.

Hier können wir sehr viele Kreise finden.

Wir können hier und hier und hier rüber gehen und haben einen Zyklus gefunden.

Jetzt definieren wir einen Wald als die Vereinigung von mehreren Bäumen.

Das ist eine sehr entsprechende Definition eigentlich.

Also zum Beispiel, also das hier ist ein Baum und jetzt nehmen wir wieder die gleichen Knoten.

Und das hier, das ganze hier, diese vier Knoten und diese eine Kante nur, das ist ein Wald.

Der besteht aus drei Bäumen.

Dieser Baum hier, der besteht aus zwei Knoten, einer Kante.

Diesen Baum, der nur aus einem Knoten besteht und diesen Baum, der nur aus einem Knoten

besteht.

Wald hat drei Bäume.

Das ist ein Wald, der besteht aus mehreren nicht zusammenhängenden Komponenten, die wir

dann Bäume nennen oder die Bäume sind.

So ab jetzt sei ein Graf, den wir uns anschauen, immer ein zusammenhängender, ungerichteter

und gewichteter Graf und zu so einem Grafen G ist eine Art zyklische Teilmenge, die alle

Ecken verbindet, ein aufspannender Baum.

Und in dem, in diesem Beispiel hier ist das auch ein aufspannender Baum.

Denn das ist eine Art zyklische Teilmenge, es ist ein Baum und sie verbindet alle Ecken

oder alle Knoten in diesem Grafen, alles ist ein aufspannender Baum.

Das hier ist kein aufspannender Baum, denn er ist nicht zusammenhängt, er ist ein Wald.

So jetzt betrachten wir den Fall, dass wir wirklich einen gewichteten Grafen haben, deswegen

schreibe ich jetzt die Gewichte explizit hin.

Machen wir doch mal hier diese Kanten und vielleicht noch diese Kante hier mit Gewichten

eins, zwei, drei, vier, fünf.

Und jetzt die Frage, was ist der minimale aufspannende Baum hier von?

Und wenn wir ein bisschen überlegen, kann man sich das jetzt hier konstruieren, also

es ist klar, dass wir wohl diese Kante hier vermeiden wollen, weil die ziemlich großes

Gewicht hat.

Wenn wir aber dann diesen Knoten verbinden wollen, dann müssen wir wohl diese Kante

nehmen.

Das heißt, die ist schon mal drin und jetzt müssen wir diese beiden Knoten noch mit den

beiden anderen Knoten verbinden.

Und was ist die billigste Art und Weise, es hier alle zu verbinden, das ist diese Kombination

hier.

Dieser aufspannende Baum hat totales Gewicht, zwei plus eins plus vier, das totales Gewicht

ist so definiert, wir summieren alle Gewichte auf den Kanten auf und das ist dann das totale

Gewicht und das hier hat totales Gewicht sieben und das ist die minimale Kombination, die

wir hier wählen können.

Wenn wir zum Beispiel jetzt hier einen anderen nehmen, zum Beispiel immer diesen hier, also

da wäre ein totales Gewicht, das ist auch ein aufspannender Baum, das ist korrekt, aber

das ist nicht der minimale aufspannende Baum, weil zwei plus drei plus vier, das ist neun,