So, gute Nachrichten oder was machen Sie? Was haben Sie heute gelernt? Wenn ein System

nicht funktioniert, einfach mal neu starten. Also herzlich willkommen, wir starten mit einer

kleinen Verzögerung, das ist gut, dann haben wir hinten noch ein bisschen mehr raus, ein bisschen

mehr Zeit. Sie wollen ja sicher nicht aufs Tech-Watfest den oder wann vielleicht schon da. So,

womit beschäftigen wir uns heute. Wir befinden uns immer noch an dem wunderschönen Kapitel über

Grafen, Informatiker, Lieben Grafen, das haben wir zu Genüge diskutiert. Bitte entschuldigen Sie

diese kleine Ritation da oben. Wir haben verschiedene Dinge bei Grafen gesehen, wir haben angefangen

mit den formalen Definitionen, klar, das sind mathematische Objekte und es hilft immer zu verstehen,

was für Eigenschaften dieser haben, das werden wir heute auch wieder brauchen. Und heute beschäftigen

wir uns insbesondere mit dem Thema der Spannbäume. Und wie der Name schon sagt, wir werden wir gleich

sehen, dass Spannbäume Grafen vollständig aufspannen und das Ziel ist natürlich, dies mit,

ja, mit möglichst wenig Gewicht zu tun. Morgen haben Sie das wunderschöne Kapitel der abstrakten

Datentüpen und das da findet keine Vorlesung statt, sondern es ist ein Selbststudium abschnitt,

die Unterlagen finden Sie wie immer online. Also was ist ein minimaler Spannbäume? Wir haben hier ein

einfaches Beispiel eines ungerichteten Grafens und dieser ungerichtste Graf verbindet beispielsweise

mehrere Städte. Also, Sie können sich vorstellen, dass jeder Knoten eine Stadt repräsentiert und jede

Kante dazwischen eine Verbindung. Jetzt ist es so, dass wir natürlich auch noch viel mehr

Kanten haben könnten, aber wir gehen einfach mal von diesen Beispiel aus. Und wir wollen jetzt ein

Grafen finden, der diese Struktur hier vollständig aufspannt. Das heißt, wir wollen ein zusammenhängenden,

ein zusammenhängenden Grafen finden, der jeden Knoten umschließt. Also zum Beispiel so was.

Also wir sehen das verschiedene Kanten wegfallen, wie zum Beispiel diese hier, ist nicht schlimm,

weil wir von jedem Knoten immer noch alle erreichen könnten. Typische Fragestellungen sind,

wenn wir Glasfaseigen, das für seine Zweck aufbauen wollen zwischen großen Städten, dann versuchen wir

im ersten Schritt überhaupt erst mal dieses Infrastruktur herzustellen und optimieren das in wesentlichen

danach. Und man kann sich hier zu überlegen, wie groß sind die Gesamtkosten, die wir haben.

Na ja, das adieren wir einfach zusammen. Da haben wir 10 aus der ersten Kante, 4 plus 8 plus 5 plus 1 plus 2

und das sollten dann wahrscheinlich 30 sein. So, zunächst definieren wir einmal was wir unter

einem minimalen Spannbaum verstehen, damit wir eine Basis haben und dann überlegen wir und

sie können wir das eigentlich algorithmisch realisieren. Natürlich gucken wir jetzt auch ein paar

Anwendungen an, damit ich sie überzeugel, alles was sie ermachen ist natürlich höchstgradig

Praxis-Rellwand. Also, wir schauen uns einen Grafen an, es sei G, V, E mit der Menge der Knoten und der

Kanten einen ungerechte Tagraf und wir sind an einem Teilgrafen interessiert, wie wir das gerade gesehen

haben. Der Teilgraf T von G ist ein Spannbaum. Der muss verschiedene Eigenschaften erfüllen,

als allererstes muss es natürlich zusammenhängen sein und darf keine Kreise enthalten,

näher warum darf er keine Kreise enthalten, weil in dem Moment, wenn wir einen Kreis enthalten

würden, dann gäbe es quasi eine Möglichkeit, einen Knoten unterschiedlich zu erreichen und

werden eine gewisse Rundanz. In anderen Worten T ist ein Baum. Die Eigenschaft, dass T ein Baum

ist, reicht natürlich nicht aus, weil es könnte passieren, dass wir nicht alle Knoten einsammeln

und deswegen brauchen wir noch, falls T ein Baum ist und alle Knoten von G enthält.

Es ist ganz klar, das heißt, wir haben hier wie hier abgebildet eine Struktur ein Baum,

der alle Knoten enthält und zusammenhängend ist, so dass wir die Intenne Struktur des Grafen

abbilden können. Und das Ziel, was wir machen wollen, ist im Wesentlichen ein Spannbaum mit

einem Gewicht finden. So wie am Ehrensbeispiele, ein Beispiel ist natürlich die Vernetzung

von Computersystemen, gerade in größeren Firmenstrukturen, gleiches gilt natürlich auch für

die Etablierung neuer Kommunikationsnetze. Wie gesagt, mehr Stritt werden wir versuchen,

überhaupt erst mal das ganze System abzudecken und erst im zweiten Schritt kann man sich überlegen,

wie kann ich die Kommunikationen optimieren, indem ich gezielt weitere Kanten hinzufüge.

Aber für den ersten Schritt brauchen wir natürlich die Minimalspannbaum. Die Verfahren werden

in bildsegmentierungsalgerutmen verwendet, sowie in Clustering bei genetischen Distanzen und auch

innerhalb von verschiedenen anderen Algorithmen werden Spannbäume benutzt. Das heißt,