Hallo, in dieser Vorlesung sprechen wir über einen konkreten Algorithmus, der in der Lage ist minimale

ausspannende Bäume zu finden und das ist der Algorithmus von Kruskal. Wir gehen mal kurz zurück

und erinnern uns daran, was wir eigentlich machen wollen. Der ganz allgemeine Algorithmus

sieht so aus, dass wir mit einer leeren Menge von Kanten starten und dann so lange sichere

Kanten hinzufügen, bis wir bei einem minimalen aufspannenden Baum angelangt sind. Und eine

sichere Kante wird so definiert, dass sie, eigentlich dadurch ist sie definiert, dass

wenn wir sie hinzufügen zu der bisherigen Teilmenge eines minimalen aufspannenden Baumes,

dass wir wieder eine Teilmenge eines mehrmalen aufspannenden Baumes finden. Und dazu hatten

wir ein Theoren bewiesen und vor allem ein Coronar bewiesen, dass wir es dann gleich

benutzen werden. Jetzt sprechen wir aber zuerst mal über die allgemeine Idee von dem Algorithmus

von Kruskal und das sieht folgendermaßen aus. Wir haben darüber gesprochen, dass wir

diese, den aktuellen Zustand a, das sind die Kanten, die wir uns bisher angeschaut haben,

dass wir den interpretieren können als einen Wald. Also angenommen, das hier sind jetzt

hier die Knoten. Ich meine jetzt nicht die Kanten von dem Grafen rein, sondern nur die

Kanten, die jetzt auch in a drin liegen. Also angenommen, diese Kanten, die Knoten ein bisschen

größer, also die Kanten, die ich jetzt einzeichne, das sind die Kanten in a. Also zum Beispiel

das hier, so könnte ga aussehen. Also a inhaltet jetzt hier diese ganzen eingezeichneten

Kanten und das bedeutet ga ist ein Wald, weil er eine Menge von disjunkten Bäumen ist.

Also das war jetzt ga, dieser Wald, den wir uns gerade anschauen. Und das Ziel ist jetzt

eine sichere Kante zu finden, die wir jetzt hinzufügen können. Und das Kriterium ist

jetzt die, das Kriterium ist das folgende, wir suchen die Kante mit minimalem Gewicht,

welche zwei beliebige Bäume in ga miteinander verbinden kann. So, welche Bäume haben wir?

Naja, wir haben sogar vier Bäume. Wir haben diesen Baum und wir haben natürlich diesen

Baum, aber wir haben auch zwei weitere Bäume, nämlich auch noch diese beiden Bäume mit

nur einen Knoten und keiner Kante. Und die Idee ist jetzt, wir suchen nach der wohldefinierten

Kante, also es gibt ja endlich viele Kanten hier, also dieser Graf, der hat natürlich

eigentlich auch noch Kanten, die ich hier nicht eingezeichnet habe, nicht nur für jeden

Weise, jeder Knoten ist mit jedem anderen Knoten verbunden und so weiter, aber die sind

eigentlich so bestrichelt rein. Wir suchen jetzt nach den erlaubten Kanten im Grafen,

die zwei beliebige Bäume in gra wieder miteinander verbindet. Also zum Beispiel nicht erlaubt

ist zum Beispiel ein Loop mit sich selbst, dann haben wir ein Zyklus, das wäre dann

kein arztzykluscher Graf mehr. Wir können auch nicht diese beiden Knoten verbinden,

weil die verbinden auch nicht zwei beliebige Bäume in ga miteinander. Aber erlaubt wäre

zum Beispiel diese Kante oder diese Kante, weil sie diesen Baum hier mit diesem Baum

verbindet. Also wir suchen in dem Grafen, in der Kantenmenge des Grafen, nach allen Kanten,

die verschiedene Bäume miteinander verbinden in diesem Wald und wir nehmen die Kante mit

minimalem Gewicht oder wir nehmen eine Kante, wenn es mehrere mit minimalem Gewicht gibt.

Und diese Ecke ist eine sichere Kante für A. Das ist natürlich jetzt hier eine Aussage,

ist diese Ecke wirklich eine sichere Kante für A, das müssen wir kurz begründen und

das machen wir jetzt. Also jetzt nehmen wir mal an, dass wir diese Kante hier ausgewählt

haben, weil es die mit minimalem Gewicht ist und wir nennen die beiden Bäume, die sie

verbindet, also diesen Baum hier und diesen Baum hier, nämlich C1 und C2. Und wenn wir

jetzt C1 nennen, dann können wir Corolla 2 anwenden. Was ist Corolla 2? Das war hier

das hier, wenn wir eine Teilmenge eines minimal aufspannenden Baumes haben und wenn C, also

in dem Fall C1, eine zusammenhängende Komponente, also ein Baum in diesem Wald ist und wenn

UV eine Kante mit minimalem Gewicht ist, ist die C, also C1, mit irgendeiner anderen Komponente

von GA verbindet, also in dem Fall C2, dann ist UV eine sichere Kante. Wir haben da ein

bisschen Arbeit reinstecken müssen, um wirklich zeigen zu können, dass es eine sichere Kante

ist, aber jetzt haben wir dieses Corolla und wir können es einfach anwenden. Das ist tatsächlich

ja für C gleich C1, das ist jetzt genau die Bedingung für dieses Corolla, dass es stimmt,