Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Informatik: Minimaler Spannbaum
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 50 Zeilen
- hallo und herzlich willkommen zu diesem Video zum Thema minimaler Spannbaum das klingt jetzt ziemlich abgefahren ist aber gar nicht so wild man stelle sich
- vor du bist in einer Stadt und du musst Versorgungsleitung legen also hier so Rohre oder Stromkabel und so weiter und so fort jetzt wenn du ein Unternehmen
- bist oder ganz allgemein versuchst du ja natürlich so viel wie möglich zu sparen das heißt möglichst kurze Wege gehen wenn wir hier in der Stadt sind dann
- gibt es immer ganz viele lange Straßen und kürzere Straßen es muss aber jedes Haus oder jede Kreuzung sagen wir mal jedes Haus jeder Ort erreicht werden und
- das gelingt halt mit einer mit der Hilfe von der grafentheorie und zwar dem Erstellen von dem Spannbaum ja was ist ein Spannbaum ein Spannbaum ist ein
- teilgraph also nur von einem normalen Grafen der sieht ganz normal aus und davon ein teilgraph also nur ein Ausschnitt davon und der ist ein
- Ausschnitt von einem ungerichteten aber von einem gewichteten Grafen wenn der Graf nicht gewichtet wäre dann würde es auch keinen Sinn er geben einen
- Spannbaum zu erstellen das siehst Du auch gleich was macht der der verbindet alle Knoten von diesem Grafen aber nur mit den Kanten die wirklich benötigt
- werden oder die benötigt werden um das zu tun da gibt's dann verschiedene Varianten wir wollen ja den minimalen Spannbaum uns anschauen so das King
- jetzt noch ziemlich theoretisch gucken wir uns ein Beispiel an also hier ist unsere Karte hier blenden wir mal ein paar Häuser Gebäude an und dazu die
- Straßen jetzt wollen wir einen Spannbaum haben da haben wir gesagt das ist ein teilgraph der nur die Kanten beinhaltet die man benötigt um alle Knoten
- miteinander zu verbinden das heißt hier kann ich ein Haufen kN Kanten verschwinden lassen und du siehst trotzdem jedes Gebäude ist angebunden an
- den Grafen also dieser teilgraf von dem Grafen den wir vorher hatten den gesamtgraf das ist ein sogenannter Spannbaum dann kann man noch mit einer
- relativ leichten Formel ausrechnen wie viele mögliche spannwäume es denn gibt von einem Grafen man kann ja unterschiedliche Kanten weglassen und
- trotzdem sind noch alle miteinander verbunden das hier ist die Formel also die Anzahl der spannbäume der möglichen kannst du ausrechnen mit der Anzahl der
- Knoten hoch der Anzahl der Knoten -2 machen wir ein konkretes Beispiel hier ist wieder unser Graf diesmal wieder mit allen Kanten drin man kann ja
- unterschiedliche weglassen das heißt es gibt unterschiedliche Möglichkeiten die alle miteinander zu verbinden jetzt hier haben wir wie viel
- Knoten one two 3 f F si s actually und die kann ich halt unterschiedlich miteinander verbinden und insgesamt gibt's halt eben
- 16807 Möglichkeiten also die Formel Anzahl der spannbäume ist gleich Anzahl der Knoten hoch Anzahl der Knoten - 2 also 7 Knoten hoch 5 und wenn man das
- ausrechnet kommt eben 16807 raus sprich es gäbe 16807 Möglichkeiten die miteinander zu verbinden und eine davon das ist quasi
- der minimale Spannbaum der minimale Spannbaum was soll das also sein gucken wir mal weiter hier ist wieder unsere Karte die
- Karte im Hintergrund nehmen wir mal weg dann wird es vielleicht ein bisschen eindeutiger also jetzt haben wir natürlich auch noch gesagt das es einmal
- ein ungerichteter aber ein gewichteter Graf dann wollen wir den mal Gewichten das heißt diese Zahlen das sind jeweils die Abstände zu den oder von den
- jeweiligen gebäunden zueinander jetzt bin ich die versorgungsfirma und will Rohre und Kabel verlegen dann möchte ich natürlich
- den Spannbaum aus wählen also die Straßen auswählen mit denen ich am wenigsten Materialkosten habe heißt es würde sich nicht lohnen wenn ich jetzt
- hier den 1000er den 800er den 500er nehmen das war ja von vorhin unsere Runde da bin ich ja super hohen Materialkosten unterwegs weil so eben
- die langen Straßen sind ich will ja lieber die kurzen Straßen nehmen dann sind ja aber trotzdem alle miteinander verbunden und ich habe gleichzeitig ein
- bisschen gespart jetzt haben wir gesagt sind 16000 Möglichkeiten das heißt das könnte ein bisschen aufwendig werden dazu um das einfacher zu machen gibt es
- den sogenannten kruskal Algorithmus und wie der funktioniert das zeige ich dir jetzt mal an diesem Beispiel also hier haben
- wir unseren gewichteten Graf jetzt fangen wir erstmal mit den kürzesten Strecken an wenn wir hier so schauen erster Überblick ist 200 die kürzeste
- Strecke das heißt der diese stße darf auf jeden Fall bleiben oder die wird eben benutzt zum Verlegen und da hinten die darf auch bleiben wunderbar jetzt
- habe ich aber ja noch lange nicht alles miteinander irgendwie verbunden gucken wir was die nächst größere Straßenlänge ist da haben wir
- eine 300er Straße und also hier unten und da oben haben wir auch noch mal eine 300er Straße jetzt stellen wir fest ah guck hier oben würde sich ja ein Kreis
- ergeben ein Kreis brauche ich nicht weil diese drei Gebäude der Leuchtturm das Kolosseum und das Museum die sind ja schon miteinander verbunden das heißt
- diese Straße die 500 Straße die muss ich nicht bebauen oder die muss ich nicht benutzen um meine Leitung zu verloren zu verlegen das wäre ja quasi doppelt
- gemoppelt wunderbar also haben wir jetzt diese hier schon mal ausgeschlossen und hier eine Verbindung gut jetzt können wir
- weitermachen 300 haben wir verbraucht jetzt was ist die nächst größere hier oben ist noch eine 400er Straße die kann ich benutzen so und dadurch ist jetzt
- hier schon allerhand miteinander verbunden also der leuchtturum ist abgedeckt das Kolosseum das Museum das Denkmal hier dann haben wir den
- Uhrenturm und hier unten das Industriegebiet ist miteinander verbunden das heißt diese drei Straßen hier die brauche ich gar nicht weil ich
- habe ja alle Gebäude alle Knoten hier schon miteinander verbunden dann schauen wir mal hier links da ist noch der Bahnhof der muss noch
- angeschlossen werden der Bahnhof da gibt's drei Möglichkeiten ich kann ih an das Denkmal anschließen das 1000 m ich kann
- das Fabrik anschließen 800 m od ein Glockenturm der ist 600 m also nehme ich doch den weil das ist die kürzeste Strecke das heißt hier unten die Strecke
- zum Industriegebiet und da oben die Straße zum denk mal die brauche ich beide nicht so und wenn ich die jetzt mal rauslösche diese Straßen die ich so
- wieso nicht benutzen möchte dann sehe ich ich habe alle Knotenpunkte miteinander verbunden und das waren jetzt jeweils die kürzesten oder ist
- insgesamt die kürzeste Verbindung das heißt hier haben wir den minimalen Spannbaum und so funktioniert der Algorithmus das heißt wir machen
- schrittweise die Kanten mit dem geringsten Gewicht die werden ausgewählt und zu dem Spannbaum hinzugefügt also wir fangen mit dem kleinsten an dann
- machen wir mit dem nächsten weiter und so weiter Kanten die durch durch die sich dann geschlossene Kreise bilden würden die werden ausgespart und nicht
- hinzugefügt zwar immer nach jedem Schritt also ich füg die 200 hinzu gibt's ein Kreis dann die Straße weg mach die 300 gibt's ein Kreis Straße weg
- die ein Kreis bilden würde und so mache ich immer weiter bis alle Kanten entweder hinzugefügt oder weggelassen wurden und dann habe ich meinen
- minimalen Spannbaum