Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Herzlich willkommen zur heutigen Vorlesung.

Nachdem es gestern ein bisschen durcheinander kam mit Vorlesungen ja, nein, hin und her.

Also gestern war Feueralarm. Ich weiss nicht, wer noch im Haus war.

Jetzt wurde der Sicherungskasten des Notstromaggregats durchgebrannt

und damit geht der Notstromversorgung nicht und damit die Notstrombeleuchtung nicht.

Und deswegen hatte dann derjenige, der erstmal verantwortlich ist für das Haus,

kam der Sicherheitsdienst und hat gesagt, es kann nichts stattfinden, weil wenn das Licht ausfällt

und gerade in so Räumen wie hier, wo kaum Licht einfällt und dann geht die Notstrom- oder die Beleuchtung nicht,

dann kann keine Vorlesung stattfinden. Also wurde erstmal alles abgeblasen,

aber dann kam um 11 Uhr nochmal die Mail vom ganz oben, vom Kanzler, der gesagt hat,

ne, es geht trotzdem, wenn Sicherheitspersonal ist da und sollte der unwahrscheinliche Fall eintreten,

dass es jetzt heute ein zweites Ereignis kommt, weil häufig ist das so, das kann man in der Wahrscheinlichkeitstheorie ja zeigen,

ein seltenes Ereignis kommt selten alleine. Also sollte so etwas passieren,

dann gibt es genügend Sicherheitspersonal da, wo wir schnell und fluchtartig dann wieder den Raum verlassen können.

Also deswegen findet jetzt doch Vorlesung statt, Obersticht Unter nach dem Motto,

wenn der Ober sagt, es ist Vorlesung, dann ist Vorlesung, auch wenn der Unter sagt, es ist keine.

Und genauso machen wir das auch heute. Man sieht jetzt schon an der Beteiligung,

dass wahrscheinlich nicht alle heute Nacht noch E-Mail gelesen haben.

Aber es wird ja alles aufgezeichnet, von daher ist es ja in unserem Fall gar kein wirkliches Problem,

kann man sich ja zu Hause im Sofa nochmal reinziehen sozusagen.

Gut, inhaltlich haben wir uns gestern beschäftigt mit aufspannen Bäumen oder Wäldern,

maximal Wäldern minimalen Gewichts und da haben wir sozusagen den ersten,

in Anführungszeichen nicht trivialen Algorithmus kennengelernt für Algorithmen auf Grafen

und das war der Kruskal-Algorithmus für maximale Wälder minimalen Gewichts,

was wir in der Übung noch sehen werden, was im wesentlichen Äquivalent dazu ist,

auch zur Bestimmung minimal aufspannender Bäume. Und die Idee war sozusagen,

die Gewichte einfach zu sortieren und gemäß dieser Sortierung so lange reinzupacken,

solange das eben ein Wald bleibt. Und der Beweis hat gezeigt, dass das geht.

Und ich habe dann kurz angedeutet, was der Grund dafür ist, das hat nämlich letztendlich was damit zu tun mit Matroiden.

Also das sind solche Objekte, wo jede, wenn ich eine zulässige Lösung habe,

auch jede Teilmenge davon eine zulässige Lösung ist und die die Eigenschaft haben,

dass zwei maximal unabhängige Mengen immer gleiche Kardinalität haben.

Sie kennen das aus der linearen Algebra mit linearer Unabhängigkeit, das ist genauso.

Jetzt haben Sie hier einen komplett anderen Kontext, wo das genau die gleichen Eigenschaften hat.

Ein Wald ist immer eine Teilmenge vom Wald, das ist wieder ein Wald.

Und die maximalen Wälder, Inklusionsmaximalen Wälder haben alle Kardinalität N-1, wenn der Graf zusammenhängend ist.

Und diese zwei Eigenschaften, das sind die entscheidend für diese, dass diese Art von Algorithmen funktioniert

und das, wenn wir später noch charakterisieren, dass es genau diejenigen sind und genau nur die.

Das ist auch eine interessante Tatsache, dass man ein Problem über einen Algorithmus charakterisieren kann.

Also wann funktioniert denn ein Algorithmus tatsächlich optimal?

Das sind genau diejenigen, die genau diese beiden Eigenschaften haben, aber das schauen wir uns wie gesagt später oder nochmal genauer an.

Gibt es bis dahin noch Fragen zu gestern?

Gut, wenn das nicht der Fall ist, dann schauen wir uns heute nochmal also zwei alternative Algorithmen an,

die aber eigentlich alle auf dem selben Prinzip aufbauen.

Wir machen das erstmal in diesem allgemeinen Kontext, da werden wir wieder sehen, dass genau dieses Austauschargument funktioniert,

wie wir das gestern gemacht haben und dann schauen wir uns von diesem etwas allgemeineren Verfahren einen Spezialfall an,

der sogenannte Prim-Algorithmus. Das sind so die beiden Klassiker, wenn es um aufspannende Bäume geht, Kruskal und Prim,

die von der Idee her ein bisschen unterschiedlich vorgehen, aber am Schluss sozusagen dasselbe rauskriegen.

Und wir fangen eben an mit diesem erstmal allgemeineren Framework, das ist der Algorithmus 6.8.