Logo TIB AV-Portal Logo TIB AV-Portal

Optimal Trees and Branchings

Video in TIB AV-Portal: Optimal Trees and Branchings

Formal Metadata

Title
Optimal Trees and Branchings
Title of Series
Part Number
4
Number of Parts
15
Author
License
CC Attribution - ShareAlike 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Identifiers
Publisher
Release Date
2012
Language
German

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Kanten Sequel states Graph functions Laufzeit component Quote unite sequence
Kanten track Graph Graph moment Laufzeit sets undecidability sequence zusammenhängende functions component Quote Mandelbrot-Menge Inductive proof
Kanten Zahl Graph Graph directions moment Laufzeit Brücken connections Platten Calculation zusammenhängende topology component clone vertices Quote Inductive proof
Great circle Graph topology Spanning Trees component optimal
Kanten Graph Spanning Trees sets area subset sign connections Energie topology vertices Quote optimal
Zuge Graph exponents Laufzeit Spanning Trees maximal enumeration orders of magnitude area sign Calculation connections exponential topology Schätzung Minimallösung topology Universal vertices optimal Faktoren
Kanten bottom Zahl momentum NET directions maximal Lösungen functions Gewicht <Mathematik> equivalence topology weighted sum linear complement Maximum Laufzeit Lineare Transformation enumeration Transformers Forest sign Schätzung functions topology Ecken classes Optimum optimal
Kanten Zahl NET Graph directions maximal Lösungen Gewicht <Mathematik> chain connections invariants topology Summe Länge weighted sum classes proof Graph complement Spanning Trees Laufzeit Airy Functions connections Forest sign invariants Schätzung topology optimal Maximaler Baum
Kanten rules Zuge connections invariants invariants Cut zusammenhängende topology iterations Triade optimal category
Kanten point rules Zuge Spanning Trees optimal großer
rules Dogs bottom topology Spanning Trees iterations optimal
Kanten rules Energie invariants invariants topology iterations Invarianz optimal vollständige Induktion
Kanten rules mathematics invariants iterations optimal category subset
Kanten Zuge Cut invariants logic topology moment Spanning Trees vertices optimal
Kanten rules Zuge moment sets großer subset Forest Dogs invariants topology logic topology Forest iterations vertices optimal
Kanten rules sets elements subset independent Forest subset infinite invariants Matrix topology Minimallösung topology Matroids finite vertices Linie optimal systems
Kanten subset Forest topology Matroids sets optimal category systems elements subset independent
Greedy components Lichtmenge sets elements independent subset Äquivalenz finite sets functions topology Matroids optimal category systems weighted sum
subset Algebra components functions Forest topology Matroids optimal systems elements proof independent
so genau sind die anderen immer so seine Haftstrafe Lernmaterialien an der TU Darmstadt so hallo
allerseits ich darf Sie herzlich für heute begrüßen ich mache mal die habe ich für 2 sonst das ist ein bisschen laut hier draußen vor Ort noch mal wer gerne noch Hausaufgaben abgeben möchte Stapel können Sie jetzt tun oder vielleicht nicht dann vergessen wenn sie es erst am Ende machen wollen auch für sie Hausaufgaben sind hier abzugeben wenn sie nicht per Email verschicken sie habe mitbekommen dass sich der Übungs- Termin wer geändert hat okay gut so gibt es aber das Auge satorischen zu besprechen von Ihrer Seite aus scheint nur humorvolle Dinge zu besprechen zu geben dann können wir ja wieder zu etwas ernsthaft und kommen zum Beispiel zu effizienten Grafen Algorithmen wenn sich dagegen haben ja waren wir stehen geblieben und was noch aussteht ist der Beweis der Korrektheit beziehungsweise der Laufzeit staatlicherseits mal gesagt gut das die Stunde vorbei ist immer die kann ich noch mal Gelegenheit weil mich etwas irritiert hat aber ich dann darauf zu sprechen kommen werden sich noch mal worum es eigentlich geht die Problemstellung um die es geht ist eine ganz einfache sie haben einen Grafen der praktischerweise in jedem einzelnen in jeder als in jedem einzelnen Knoten geraden gerade haben sollte so um den geraden gerade hinzukriegen machen am besten noch mal hier hin so hier kriegen geraten gerade 1 2 3 4 5 haben immer noch keine geraden gewahrt dann machen wir es anders so so hier gerade in Graz 1 2 3 4 hat Graden gerade also so dass geht mir noch mal Gelegenheit die Kamera zu justieren dass da ja genau gute Idee das ist auch wirklich genau das Bild auch ist für das Bild und kann man nix sagen ja okay gut ohne die Aufgabe besteht darin eingeschlossenen weg zu finden war der jede Kante genau ein einziges Mal enthält der genau jede Kante genau 1 Mal durchläuft wir haben diesen Algorithmus hier schon beim letzten Mal gesehen vielleicht doch mal zur Grundidee wir laufen in gewisser Weise durch den Grafen durch so ähnlich wie das ist das Haus vom Nikolaus habe aber festgestellt beim letzten Mal dass das nicht ausreicht dass wir dabei durch aus Teile des Grafen nicht sehen wenn wir einfach so nach der Manier das ist das Haus so Nikolaus einmal so durchlaufen deshalb haben wir hier diese rekursiven Aufrufe an dieser Stelle noch mal ganz kurz durchgegangen wir fangen an mit einem aus in einzelnen Staaten wurden besteht und unser Knoten x ist auch dieser Staaten wurden und solange wir am jeweils aktuellen Knoten noch kannten haben sie einen sich kannten wenn immer gleich rausgeschmissen weil sie so später nur stören das Ende durchlaufen haben die kann rausgeschmissen dann holen wir uns eine Kante solange wir vom aktuellen Knoten aus noch weiterkommen können über bekannte wohl könnte für die einen den andern Knurren fügen wir ein und diese andere Knoten ist dann der akribisch aktuelle Knoten das heißt also wir gehen von einem Knoten zum anderen und schmeißen dabei diese kannte die wird eingefügt haben aus dem Grafen raus und wenn wir jetzt mittendrin irgendwo jetzt bei diesen bisher konstruierten weghaben rufen wir nochmal Euler mit mitgeben zwischen Quoten auf um genau dieses dieses Phänomen zu vermeiden das ist die er das wie ein kann vorbei die wir nicht erwischen ja ich denke es ist einsichtig auf diese Art und Weise erwischen wir alle kannten wenn wir das hier machen erwischen wir alle kannten D fahren diesen Weg aus gehen wir haben momentan diesen Weg der geht irgendwie Kreuz Quer und mit jedem einzeln Knoten auf diesem Weg rufen wir nochmal Eule auf so dass alles das was wir an Kanten haben ich hier was noch nicht abgegrast wurde es also was immer noch im Grafen drin ist noch nicht gelöscht worden ist alles das würde dann oder ein leicht an jedem dieser Knoten passiert noch mal was das er das ist auch gut dass sich dabei der gefressen wird so und das Ergebnis ist dann jeweils wenn wir hier über alle noch irgendwie weitere Sachen reingehängt haben das Ergebnis von dem ganzen gehen wir zurück so 2 Fragen warum ist das korrekt und warum ist das tatsächliche Jahre Laufzeit so Korrektheit also wobei ich etwas gesteuert werden beim
letzten Mal ist sie sehen dass hier das der Beweis ein bisschen kurz gehalten ist das der doch einiges an relevante Informationen vielleicht ein bisschen vermissen ist also ich sollte noch dazu sage ich will es mal drauf hingewiesen worden dass sich das mit einer veralteten Version der Folien hier gearbeitet habe haben die jetzt arbeite ich mit der aktuellen das sollte aber jetzt bei dem was wir jetzt ist man von dass man betrachtet haben ein Problem für Sie sein so was ist der Grund dafür was ist das Argument dafür dass der Algorithmus korrekt ist man müsse noch mal klären was Korrektheit heißt wir müssen natürlich voraussetzen dass der Graf zusammenhängt ist wenn wir nicht zusammenhängendes habe keine keine und keine solch Eulersche Tour klar also der Graph zusammenhängend und die invariante ist jetzt die das Betrachten beachten Sie dadurch dass das ganze rekursiv ist das was passiert dann so an so einem Knoten bei dem nochmal rekursiv das Ganze aufgerufen wird was da passiert so dass Knoten und hier sind noch ein paar kannten eine gerade zu 1 ist und sein nicht so eine gerade Anzahl 1 2 3 4 5 6 von kannten die da noch ablehnt Gesetz nicht abgegrast worden sind weil wir eben von hier kommt dann wäre gegangen sind so jetzt unbekannte genommen zum Beispiel hier und dann wird auf irgendeine magische Art und Weise irgendwo hinten rum wieder eine Kante erreicht zum Beispiel hier so immer noch mal zurück zum Algorithmus so wir genauso
entscheidend hier ist auch dass wir auch für eines das Aufrufen das heißt also in diesen rekursiven Schritt und wir wieder rekursiv für ihn als sind wurden halt das keine Quoten diesen Knoten diesen roten wenn ein sind nun um es rekursiv auf so dass ich so nach und nach so komische ist Apfelmännchen sehr Sie kennen das von der Chaos die Riesen Apfelmännchen hier ergibt somit immer weiter draufgepappt und zügeln aber weil wir das auch mit 1 aufrufen wird dann nochmal rekursiv innerhalb dieses rekursiven Aufruf so was noch mal mit dem 1. Knoten dieses Weges auf den wir hier konstruiert haben ist gewährleistet dass wir hier auch noch mal so lange hier bei diesen Knut noch was frei ist etwas finden noch und natürlich wieder zurück kommen müssen weil wir müssen immer zurückkommen weil das der einzige Knoten ist momentan der ungeraden gerade hat und solange wir gerade gehört haben können wir immer weiter so und in diesem rekursiven Aufruf wäre wie sie jetzt hier 1. Aufruf 402. auf darin wieder rekursiven Aufruf hier drin von diesen rekursive auf auf auf denen geht es wieder weiter im vierten Aufrufe zu zum bisschen unübersichtlich und so fort so dass dann alles am Ende abgegrast sein wird das heißt also dass keine Kanten mehr übrig bleiben die von hier aus von diesem Knoten aus überhaupt erreichbar sind und bei zusammenhängen da ist erreichbar denke ich es einsichtig dass damit der gesamte Graf alle kannten erreicht werden durch diese Rekursion Widerspruch angenommen ist es nicht es wär nämlich kann es beim und welche Karten stehen na ja da muss es auch irgendwo durch wegen der wegen des Zusammenhangs muss es auch irgendwo kannten gegeben haben die stehen geblieben sind die aber zu die aber in den zu Knoten auf diesem bis dahin gefunden weg sind und die während das ein Widerspruch die wäre natürlich in einem weiteren rekursiven Aufruf mit hineingenommen worden so das war das noch nicht der Punkt an dem ich letztes mal ein bisschen gestolpert bin wo ich gestolpert bin ist die Frage warum zum Teufel ist das Ganze die Jahre Laufzeit wenn wir jetzt wie Sie sehen hier auf den Folien jedes Mal hier den ganzen bisher konstruierten Fahrt durch sämtliche Knoten durchgehen da habe ich mich noch mal in einen Quelle schlau gemacht und siehe da ist es natürlich nicht so wie jetzt zunächst einmal hier so aussieht dass sämtliche Knoten noch mal durchgehen sondern wir verwalten einfach die in einer Liste der beispielsweise die Menge der zu diesem Knoten in sidenten kannten die noch nicht gelöscht worden sind diese Karten laufen wir durch dieses so laufen wir durch und damit ist natürlich klar dass weder kannte nur einmal angefasst haben in dem Moment wenn wir sie in diese Liste angefasst haben löschen wir sie sofort in dieser Interaktion das war der Punkt wo ich letztes Mal in Schwierigkeiten gekommen wären mit dieser Laufzeit und Sie sehen werden in
der letzten Version von Anschlägen darstellt ich bin natürlich unschuldig wenn das gern wenn der Beweis so relativ knapp gehalten ist dann werden Sie mir nachsehen dass ich in dem Moment nicht so richtig wusste ich das jetzt interpretieren habe aber dafür hat man ja immer noch mal eine Woche Zeit um das noch mal nachzuschauen und dadurch dass wir diese von Staat und auf nämlich auf das funktioniert auch alles dadurch können dadurch können können wir das auch nachvollziehen was eben nicht auf den Folien so hundertprozentig genau aufgeführt ist er noch mal was zu den Aufnahmen ich habe jetzt angefangen mit damit die Idee Videos zu rendern habe aber festgestellt das ist eine er Zeitaufwand ist beziehungsweise ich Tugend in der Zeit nicht aber ich musste immer also Sie kennen das von der von der mich im Kochtopf auf der Platte oder so dass man dann immer mal mal dabei sein muss also das funktioniert so nicht leben zu dem im Zusammenhang mit meinem Zeitplan also dass ich mir da jetzt Assistent suchen muss dass das jemand ist der sowieso die da im Gegensatz zu mir die ganze Zeit den ganzen Tag am Rechner sitzt der das dann eben so ne mehr machen kann ohne ohne Zeitverzögerung tut mir leid so das hat mir schon mal glaube ich gesehen das letzte Mal für gerichtete Grafen da die wir natürlich nur immer in die in die auch in die Richtung der Regierung der kannte und das er betrachten wir nur für jeden aktuellen Knoten immer nur die rausgehen in kannten so historische Bemerkungen Kg genau hat glaube ich dass mal auch gesehen und er hat es gezeigt davor den Königsberg gibt die Brücken die 7 Brücken hatte geglaubt dass er nicht in Venedig gelebt hat hat ein bisschen mehr umziehen müssen das ist die wobei ich mal gelesen habe beispielsweise Berlin hat mehr Brücken als Venedig ich habe gelesen weil sie noch stimmt ich immer zu seiner Zeit noch nicht also wie die wahrscheinlich schon aber Berlin war zu einer Zeit glaube ich er sei kein Kuhdorf mehr aber es war noch immer noch nicht eine Metropole wie Venedig sie eine Frage ja sie meinen zu dieser Zeile zu der ich ja vermutlich also verbinden sich noch zeigen kann okay also die die Frage war jetzt wenn wenn hier so rekursiv aufgerufen wird warum kommt man wieder zurück also warum bildet sich ein Kreis gut Argument in wir zu jedem Zeitpunkt so wurde er wenn Sie mal ja dieser Knoten wenn diese keine gelöscht wird da dieser Klonen dieser Klon ungeraden gerade so wenn jetzt diese Karte gelöscht wird dann hat dieser Knoten dieser Klonung geraten gerade und so weiter ja so werden jetzt was ist die Argumentation genau da wenn Sie auf ein Plus stoßen geraten gerade hat können Sie immer weiter sie komm rein also bevor sie rein comma daran gerade das heißt er mindestens gerade 2. kann rein kommt sie comma über eine könnte und das heißt sie kann auch über bekannte wieder ausgehen und das heißt dass sie kann immer weiter bis so zum Knoten mit gerade 1 kommen Ungarn gerade und damit wir diesen das Argument es vielleicht ein bisschen von hinten durch die Brust ins Auge aber wenn sich das noch mal mit dem Haus von Nikolaus in diesem kleinen Beispiel sorry aber das ist in meiner Stadt hat Beispiel dafür wie man sich das noch mal klar machen mit den der und dieses Beispiel hat ja gerade genau 2 ungerade Knoten das es so wichtig dass sie bei dem ein und können wohl Anfang so dass Sie dann bei dem andern Umfragen Knoten aufhören wenn Sie bei bei einem der Argwohn anfangen können Sie das Bild nicht in einem Zug hinzurichten also ich vor nicht geklärt oder gut sie und ohne Frage Laufzeit okay aus okay also die Frage war also oder sagen wir mal so allgemein ist dass du die Problematik Anzahl der kann die Anzahl der Knoten so eigentlich steht hier zu viel wir haben ja einen zusammenhängenden Grafen er nannte sich noch bei einem minimal sparen also minimal ein ein ein spannender bauen 1. zusammengerafft mit minimaler kann es dafür geben kann wozu er sich nicht noch an die kann es sei denn man hat Spanner Baum auf Endnoten hat ja Knoten Zahl minus 1 genau das heißt also in einem Zusammenhänge Grafen ist die Kanten Zahl bis auf 1 mindestens so groß wie Kloten Zahl das heißt also die Knoten Zahl ist also methodisch dominierte Skikanten sein eigentlich könnte man hier das Plus streichen und es wäre diese Aussage da der Graph zusammenhängend ist also ich bin jetzt nicht direkt auf Ihre Frage einiger habe ich glaube ich habe sie trotzdem beantwortet gut ich denke das hat Herr Steel einfach nur mit dem was ich glaube du würdest ob wir es auch häufig so gemacht einfach um um es nochmal genau genau in Sinsheim aber eigentlich ist es Redundanz wenn Sie Sie können sich natürlich vorstellen Oilers Rundtour O ff auf mehreren zusammen Komponenten zu machen aber ich glaube da haben wir das Argument dadurch dass das ja alles zyklisch ist muss es immer noch die Kanten soll man also tun mir so groß wie wurden als 1 Allgemeine der Graf zusammenhängt ist muss die kann sei natürlich nicht mindestens so groß also durch Reklusa seinen betrachten sie Grafen ohne Kanten 1 Million Quoten gar keine könnten dass sie keine sei natürlich nicht aus und und so groß wie Knoten Zahl aber wenn wir keine isolierten Knoten haben dann haben wir alles in zügeln dann muss es mindestens genauso groß sein dann ist es immer noch die diese Laufzeit stimmen wir wieder als wir zusammen und es kommt etwas machen ich glaube ich habe jetzt mehr waren wurde sie gefragt haben ob das positives weil sie jetzt nicht so jetzt
comma die zu diesem Bild das ist natürlich nicht mehr fällt natürlich nicht mehr unter Urheberrecht versteht sich dieses dafür ist dieses Bild zu und der wir immer das gezeichnet hat hat sicherlich keiner Erbengemeinschaft mehr die ich hier Rechte angeben kann so damit sind wir mit dieser Problematik ruhig
und wir kommen jetzt so eine neuen
Sache die für sie nicht neu ist wir
werden ziemlich viel noch mal am Anfang dieses Kapitels werden wir nochmals zu ungerichteten kann Grafen kommen und zu einer Problemstellung zu einer Problemstellung die sie aus der G 2 kennen nämlich der man wollte mal spannende Bäume Wir werden sehen kennen aus der Primor groß sollten Sie kennen wir werden jetzt hier ein allgemein schlimmer kennen lernen ob Priem und Kruska obwohl die so extrem unterschiedlich sind einfach nur 2 Beispiele sind dieses allgemeinen stehen also es geht nicht darum neue Problemstellung ganzen und tolle neue Algorithmen Kanzler nimmt 1. Teil dieses Kapitels im zweiten Teil dann schon das ungerichtete Grafen geht damit das Ganze er wie kompliziert und haariger sondern es geht darum einfach einen abstrakteren Blick aus der Adlerperspektive auf ein Thema was sie schon aus die 2 Kennemer spannen Bäume Algorithmen verbrennen und groß gerade bzw. allgemeine Schema das man auch ganz anders als im April Großkreise konkretisieren kann da er hallo ja hallo hallo sind
da erhalten keine Denkpause
gebraucht das ist alles okay so
sind Sie wissen was haben sicherlich Energie 2 bei den Sie es auch gehört haben Kuss thematisiert worden ja ich habe mir sagen lassen dass in Vorlesungen wie Einführung in Netz Systems und darauf aufbauenden Vorlesungen dass da S und kürzeste Wege dass das dann auch wieder thematisiert wird weiß ich jetzt nicht aber hat ich habe es von den dezenten gehört also wird es wohl stimmen so Sie kennen Sie kennen die Problemstellung können wir ganz schön durchgehen weil sie aus der Gidi 2 ganzjährig in ganz frische Änderung haben auch wenn sie vielleicht schon vor 3 Jahren das gehört haben sie haben Gericht ein ein ein ungerichteten aber zusammenhängen Grafen mit positiven könnten und was Sie suchen ist eine Teilmenge der Kanten Menge also identifizieren diese minimal spannen Baum mit seinem kann wir drücken ihn durch seine Kantenlänge aus so was ist die Zielsetzung der Was ist das Ganze dass der Graf auf diesen mit diesen mit der ursprünglichen Quoten Menge und dieser spezifischen kann Menge also alles was nicht zu T gehört habe aus ihr rausgeschmissen und dieser Graf ist immer noch zusammenhängt und unter diesen Umständen also das ist ein spannender Baum ist solle die das Gesamtgewicht dieses Baumes minimiert werden so und wenn es tatsächlich einen Baum ist dann nennen wir es auch eine minimal spannender Baum
das ist dadurch gerechtfertigt wir haben ja positive strikt positive könnten Kosten sehen Sie oben jeder kann dort wo es still positive kosten das heißt eine Minimallösung kann keine Züge enthalten den man sie Anzüge enthält kann ich mir unbekannte hernehmen rausnehmen und habe da würde ich das Gesamtgewicht vermindert also kann das vorher keiner Minimallösung Lösung gewesen sein es muss zusammenhängend sein das die Forderung es muss Züge frei sein sonst ist nicht optimal also ist ein einbauen so natürlich die 1. Idee gibt an die man denken könnte dass man einfach mal alle spannen Bäume berechnet und den nimmt der niemals Gewicht hat letztendlich ist die
Formel die dir steht warnt weil sie können sich vorstellen es vollkommen wurscht wie genau die Formel aussieht das funktioniert nicht es sind viel zu viele spannende Bäume dies haben kann nur falls es sie interessiert er das ist der Satz von Kelly dass die in in einem vollständigen Grafen wo alle kann alle möglichen kann tatsächlich enthalten sind gibt es insgesamt so viel mehr verschiedene mehr spannende Bollmeyer beachten Sie dass diese Funktion in allen sogar noch schneller wächst als die Fakultät die Fakultät wird schneller als jeder Exponentialfunktion als jeder 2 hoch N oder eine Million noch ein oder so etwas und diese Funktion wird sogar noch schneller als die Fakultät also keine guten Ausgangsbedingungen dafür dass der das wird das einfach enorm regieren und das den optimalen Bau nehmen das ist hat das an der Stelle mal hier nochmal zusammengefügt selbst wenn wir eine Million Bäume pro Sekunde berechnen können selbst bei 30 Knoten sind wir schon irgendwie nicht mehr im übernächsten Universum sondern schon noch ein paar und diversen weiter bist gelöst bis die Lösung endlich vorliegt also kein guter Ansatz und beachten Sie auch wenn wenn einer wenn die Laufzeit eines Algorithmus mindestens exponentiell ist das ist nicht viel bringt dann mehr Rechenpower zu haben weil man dieses für sie die Power um den Faktor 10 erhöhen um Faktor 100 oder einfach Faktor 1000 es egal der Exponent wächst nur additiv ja wenn sehe mehr wenn Sie zum Beispiel das mehr wenn Sie zum Beispiel in einem Menschenleben oder in einer Nacht oder was immer sie sich als Zeitvorgabe hernehmen wenn Sie die Größenordnung sie einen Algorithmus dessen Komplexität des 2 O N und sie kennen wir können mit dem großen können kommen Sie in einer Nacht durch mit ihrem Algorithmus der und jetzt haben sie tausendfach höher Beschleunigung Ihres Rechners wie ändert sich das ganze das ändert sich dahin gehend das sie jetzt 2 hoch N los zählen diese Größenordnung in bekommen ja das heißt also hier darum dramatische multiplikative Änderung der Rechenpower bringt Additive Änderung der Problemgröße die Sie mit dieser zusätzlichen Rechenauer derselben Zeit bewältigen können das heißt also bei so einem bei seinem Problem bei einem Algorithmus dass dessen auf das exponentiell oder sogar noch schlimmer ist brauchen Sie nicht zu warten bis der Rechner schneller werden viel bringt das nicht so was jetzt was ja
so Minimum minimal sparen aber um maximal war spannender Walz wenn sie bei geht zugehört haben letztes Semester dann haben Sie gesehen ich habe es genauso er beides zusammen eingeführt ich denke früh in früheren Semester vielleicht auch weiß ich jetzt nicht zunächst einmal als was wir zeigen wollen ist das 2 dass diese beiden Problemstellungen finde einen minimalen sparen bauen in mit positiven kannten kosten in einem zusammengelaufen und finde einen maximal spannenden Wald in einem beliebigen ungerichteten den ich zusammenhängend sein muss dass die beiden Problemstellungen äquivalent sind im Sinne dieser Definition ich will kurz mehr ich will es kurz anhand einer Zeichnungen darstellt und was man sich darunter vorzustellen hat so eine 7 Jahre Transformation dass man ein Problem überführen kann und das andere Problem nein durch seine linear Transformationen so wir haben der 2 Probleme Problemstellungen P und Q das wir sind hier um betrachten wir das B und unten das Q wie sieht's jetzt aus mit ihr schon wieder eingefallen andere Seite wie oder sie gesehen dass ist gut ja so wie sie haben jetzt hier 1 Beispiel in Porz irgend ne oder so eine in Bolz irgendeinen die aus dem Problemstellungen P mehr und das transformieren sie das ist jetzt hier auf der Folie die Funktionen der aus so hieß es Ex genannt denen es auch Ex ja das ist die Funktion f die transformiert das also wenn wir vom Funktion reden dann meine natürlich implementieren das es heißen Algorithmus deren Input aus P hernimmt und außen Input aus macht Input er von X aus so jetzt haben sie Lösungs Algorithmus für und jetzt haben sie noch eine weitere Transformation also dieser Lösungs aber Algorithmus liefert Ihnen natürlich da eine Lösung Z für f von X nur noch alles drauf wie oben rechts in der Ecke also wenn ich wenn ich hier denke schreibe und es nicht auf da muss es doch auch hier auch nicht auf sein ach so also ich muss unter so ziemlich alles aber wie hier um Recht das doch gar nichts okay also das was wir das gar nicht da es würde fehlen wenn es da wäre ok okay wir würden wir nicht weiter drüber nachdenken so ist comma aber eine gefährliche Ecke langsam hin hier ist diese Funktion geht die eine Lösung Z in einem wieder zurückverwandelt in eine Lösung die Form selbst für Erna nahe der auf der Seite für Co ja und das das hier konstituiert im Prinzip ein Algorithmus für das Ursprungs Problem P also nämlich nicht das ist nämlich wählen genau gesagt keine Lösung von für Q sondern für für dieses Beispiel X sogar ich schreibe doch mal auf die andere Seite das ist auch wenn wir dann langsam in den gefährlichen Bereich kommen so hier und über diesen Umweg kann damit praktischen Algorithmus für so Ausgangsproblem P gebaut also das das Bild was was sich ganz hilfreich auch für mich finden um sich sowas vorzustellen wovon er gerade reden so und worum es geht es jetzt das Beispiel zu zeigen wir könnten wenn wir einen Löser haben wir ein Affe Algorithmus haben mit Laufzeitende Nasenduschen Komplizität für vorbei ist dann können wir können wir über Sonne Transformationen auch Minimums bei den Three damit lösen und umgekehrt wenn er gewußt wird Minimums Petri haben können wir einen Algorithmus können wir da können wir damit auch Max Fares gelesen und zwar mit derselben Laufzeit beides 2. die beiden Transformationen sind linear und damit wir damit spielen die natürlich wir sind deutsche Komplexität keine Rolle war besser wenn er kommt man sowieso nicht hin allein das Einlesen der Daten wird immer schon in der Laufzeit so also F transformiert das ist das was wir längst die transformiert zurück auf der 11 auf der Seite der Instanzen der Beispiel in Butz die auf der Seite der Lösungen und genau das habe ich jetzt noch vergessen dazu zu sagen denn das optimale Lösung ist die der hier produzierte der Algorithmus dann sollte das auch eine optimale Lösung sein also letztendlich auf das darauf hinaus dass die dass diese dass diese Funktionen monotone Strecken monotones diese Funktion geht das heißt größeren wert dieses diese Lösung hier hat umso größeren Wert hat diese Lösung hier auch damit ist natürlich klar Optimum wird transformierten Optimum also ich muss muss umgekehrt gestern weil wir ein maximiere sondern muss Probleme haben ja je größer die Lösung hier ist umso kleiner wird der lesenswert hier umso größer würde Lösungsfeld hier und umgekehrt je größer ihr so kleiner hier war das jetzt aber klar habe ich das denn es ist noch nicht so richtig klar ich sehe keinen Finger ich gehe davon aus also sind das Gott wir müssen schneller vor das nicht so
die Behauptung ist also jetzt das wie ich eben gesagt habe dass die nach diesem Schema äquivalent sind und ihr da haben wir natürlich wie immer 2 Richtungen die 1. Richtung ist wir haben einen Algorithmus gegeben für Max Forest und wolle man es banyantree mit diesem Algorithmus lösen das heißt also wir brauchen solche Transformationen Inputs Impuls von Minds bei den trieben Import von Macs Forrest umgewandelt und Output von Lösungen von Macs Ex-Vorstände Lösungen von Münster Einträge umgewandelt und das ist ganz einfach sagen sie mit großer Wahrscheinlichkeit in der die zur schon als gesehen also bei mir und sicherlich dass wir das wie er im Grunde negieren die Kosten alle denn er wenn man das negativ aber weil wir am Ende mit positiven Gerichten rauskommen wollen müssen wir müssen wir noch ein wir noch ein Wert drauf der dafür sorgt dass alle diese negative willigte garantiert wieder in den echt positiven Bereich rauskommen aus nehme dafür ändert wir nehmen den Maximalwert aller kannten Gewichte und setzt noch 1 drauf das heißt egal welche welche steht diese Differenz N minus CE ist garantiert positiv ja für die für die größte Zahl CE hier was ist Größe kein Gewicht kommt die gerade 1 plus 1 raus nämlich dieses Plus 1 ist hier drauf erklärt haben so hier ist ein wichtiger Punkt zu bemerken wir glaube ich auf den Folien sie auch nicht so genau klar rauskommt so eine Transformation funktioniert nur deshalb Mama vielleicht einen Schritt weiter erst mal so wir setzen diese um die wir wir definieren neue Gerichte das ist diese Transformation F mehr wird das mit Forrest Problemen da drauf der Graf zusammenhängt das heißt er liefert Macs Forrest liefert tatsächlich einer er einen nicht nicht ein allgemein würde weil die Kanten Gewichte größer 0 sind und weil wir ein Maximinus Probleme haben auf positiven kann gewichten ist das Ergebnis nicht mit weit sondern ein Maximum an weit mit maximal Bildkanten drin nämlich einen Baum und hier kommt ist ein wichtiger Punkt dabei hinein wo sich klarmachen müssen das funktioniert beim ins bei den Trier aber es funktioniert beispielsweise bei kürzesten Wege nicht der wichtige Punkt einer Sache ist der alle Sparten Bäume haben sehr bekannt der Fall ist wenn wir jetzt eine Lösung wenn wir jetzt die das
bedeutet die das Gericht hier das maximale Gewicht da haben wir minus 1 x draufgesetzt egal welcher Baum das ist es immer in das einmal was die Gesamtänderung der Gewichte angeht Anzahl der Klon minus 1 in kann man mal zur minus Summe der CD das ist die das ist die gesamte R Gesamtgewicht jedes Baumes also die der kannten die hier in den Baum drin sind das bedeutet die einzelnen Bäume und deren Kosten sie haben sich alle gleich viel geändert das ist beispielsweise bei kürzesten Wege nicht der Fall weil wenn sie sich 2 Wege anschauen von von einem Knoten zum anderen Knoten die müssen ja gar nicht im allgemein dieselbe Länge haben ja einer hat 387 Tausend könnten die habe ich es nicht eingezeichnet der zweite hat der andere beantragen können wenn sie jetzt nur Transformation machen so eben ja man kann denke so wunderbar damit viel bei der extra das Problem nur positive könnten Gerichte wenn wir auch negative kann Gerichte haben hinter sie alle einfach genauso wie er und so ein großes m hoch das Problem an der Sache ist dass dieser ich hier um dreimal hoch gehoben worden ist und Weg hier 3 die also 3 4 5 6 um 6 sechsmal Amoco um wollen ist das heißt hier habe die kann man verfälscht wären bei einem weil weil verschiedene bekannten eben welche vor dem verschiedene kann Alarm wären bei dem man es wenn nicht wie kann das nicht passieren alle Lösungen haben dieselbe kann so und das ist Norderstedt noch hinter diesen letzten dash hier so jetzt drehen wir es um
jetzt gehen wir davon aus wären Algorithmus für meines Berning Tri und wollen umgekehrt sehen ob wir nicht eine solche Konstruktion finden so eine längere Transformation dass wir damit auch den 1 den Macs Forrest lösen können so wir machen das selbe wieder allerdings einen Schritt weiter wir bitten wir vervollständigen den Grafen also es wird jetzt nicht mehr linear die Transformation des habe ich es immer falsch gesagt also wir werden der so Laufzeiten kommen wir vervollständigen den Grafen zu dem falschen ständigen Grafen klar und setzen setzen richtig groß also was hier letztendlich steht auch wenn diese ihre komplizierte Formel stellt das was sie aus kürzesten Wege der SED zu erkennen da steht unendlich etwas komplizierte Form unendlich auszudrücken aber da steht ein einfach eine ausrei- ist eine ausreichend große Zahl dass sie uns nicht das uns kannten mit der mit der kein Gewicht nicht stören mehr so hier muss er mir ist das glaube ich schon viel erreichen muss minus 10 stehen so wie eben auch wieder der positive wir kannten Gewichte am Ende kann gut also so groß er Minister E und ansonsten keine wir weit größer als in sein der hier steht also bei den kann die gar nicht existieren die wir vor zur Ver Vorschlägen eingefügt haben setzt man ausreichen großen der drauf so wie berechnen die Kanten Gerichte wenn wir jetzt die nur den nur die Kanten betrachten die ursprünglich schon drin waren und jetzt in diesen in diesem immer spannen Baum drin sind kann warum machen wir das Ganze mit der Vorschläge machen das ganz einfach deshalb weil der Graf ja zunächst einmal nicht zusammen sein muss bei Macs ist da gibt es da überhaupt gar keinen Grund dass der Graph zusammenhängend sein muss weil wir eh nur den Anspruch haben einen maximalen Wald zu finden nicht magst maximalen Baum des also können wir gleich auch erlauben es ergab ich zusammenhängt ist so dass die zusammen es Komponenten wieder mal sind sehr vor mir gewöhnt dass sich da so Knobel zeichne so und was wir machen ist diesen Grafen zu vervollständigen da geht schon bald könnten wir zwischendurch die wir zusätzlich addieren aber weil die so hohes Gewicht haben wenn die dann keine Rolle spielen aber was wichtig ist ist dass das jetzt natürlich die Riesenanzahl von kannten hier reinkommt und sie sich an wie man das dann tatsächlich ja kriegen kann in dem man nicht zum KN vervollständigt das muss gar nicht sein sondern indem man es einfach zu einem zusammenhängenden Grafen vervollständigt ja dann der bekannten Zahl linear wie am Ende rauskommt so war das Bild einer so zusammenhängt irgendwie an welche kannten von hier irgendwo nach irgendwo und so weiter und jetzt aber gar zusammen das können Sie MST anwenden sie kriegen nicht hier jeweils was kriegen Sie raus sie kriegen jeweils Mensch bei Baum raus Plus könnten hier raus warum wollen es der Allgewalt diese kannten haben haben größtes Gewicht als als die ursprünglichen kannten hier drinnen das heißt also diese Karten werden höchst ungern genommen werde nur genommen wenn es unbedingt sein muss oder werden sogar so machen sogar noch weiter reduzieren dass die insgesamt nur das dass der dass diese kannten keine Zügel bilden so die Karten werden genommen im minimal spannen Baum es gar keine Alternative gibt und innerhalb von jedem einzelnen hier haben wir einen jemals spannen Baum das ist das ist das Ergebnis von MSC und wenn ich hier jeweils ein minimal von der Baum nach dem modifizierten kann gewichten drin ist dann heißt das hier ist jeweils ein maximal spannender Baum nach den ursprünglichen kann gewichten und also genau umgedreht worden ist und der mir die kann jetzt wieder rausnehmen hier aus der Lösung dann bleibt übrig maximaler Wald auf dem ursprünglichen Grafen das Transformation hin und zurück also wenn sie tatsächlich wir Laufzeit haben wollen wie Anfangsformationen dürfen sie nicht so machen wie es jetzt gerade hier auf der Folie steht dass sie das vor Vorschlägen zu den vollständigen Grafen damit haben Sie sofort Explosion der kann drehen unnötigerweise sondern es reicht das sie so weit vervollständigen gerade so dass der Graph zusammenhängend wie man die zusammen es comma Komponenten finde keine Lehrer Zeit habe letztes Mal betrachtet wir könnten so von vornherein ein natürlich und ich hier in diese Richtung einfacher machen dass für jede Komponente für sich betrachten aber so oder so dieser beiden Problemstellungen die zunächst mal ähnlich aber doch nicht aber doch nicht spiegelsymmetrisch aus aussehen sind trotzdem identisch so jetzt kommen wir zu den Algorithmen wir kommen hier auch zu Bremen Kruska sagen aber noch nicht sondern bekommt im allgemeinen Schema wo wir dann feststellen Premont Kruska nur 2 spezielle Fälle von diesem allgemeinen Schema kannten werden gesperrt als zu meiner Zeit als ich das mal in der vorlesen gehört habe war das noch Rot und Grün inzwischen sind es rot und blau weil sich doch die Erkenntnis herumgesprochen hat dass Rotgrünblindheit 1 sehr typische sehr häufig vorkommenden Sehstörung ist deshalb über Alter wo sehen gesprochen hat dann vermeidet man Rot und Grün obwohl es eigentlich schade ist sehr genau geht die richtige Sie diese die in meinem meist beabsichtigte Signalwirkung hat so auch hier also grün Blue Grün eigentlich heißt gut prima Klasse rot heißt Nein so das allgemeine Schema beginnt mit mit dem Grafen wo keine einzige könnte gefärbt ist und wird mit dem kann im Garten auf wo jeder kannte gefärbt ist entweder Rot oder Blau nicht beides aber 1 von beidem und dieses Schema der Algorithmus den wir gleich sehen diese einige Algorithmus hat diese Invariante also diejenigen von Ihnen die bei mir geht's 2 gehört haben sind von vorne bis hinten glaube ich bedient mit den Varianten nichtsdestotrotz kommen sie wieder
die invariante ist folgende es gibt eine und minimal spannende und beachten Sie denken Sie daran der minimal spannen Bau muss sich eine Liste 1 kann durch das mehrere minimal spannen Bäume in einem ungerichteten Grafen mit kannten Gerichten geben so arbeiten unter denen gibt es einen der alle kannten enthält und keine rote der Algorithmus wird in jeder Iteration eine weitere kannte rot oder blau färben und der wird diese Invariante dabei beibehalten suche nach jeder Iteration gilt das wieder wenn er eine kann der blau gefärbt hat dann geht wieder auch mit dieser zu blau gefärbten kannte das es einen immer spannen Baum gibt der alle blau gefärbten kann keine roten enthält und wenn eine Kanne rot gefärbt hat zusätzlich zu den schon bis dahin gefärbten kannten wird es auch wieder gelten es gibt eine spannen Baum der alle blauen und keine Rote Karte enthält so wie sieht das aus das möchte ich ich gehe mal davon aus dass sie noch eine dunkle Vorstellung die von Priem und Kruska haben also sagen Sie doch was oder Gesetz gut lesen auf der Tafel es geht okay jetzt brauchen Sie es kann sich mal kurz lesen ohne Tafel aber ich brauche gleich die Tafel wieder der so Sie erinnern sich an den Algorithmus von Bremen welche von den beiden war das jetzt noch wenn das ihr Graf ist dann war Priem der Algorithmus sie haben statt Noten und von einen von dem aus so langsam schrittweise immer ein Knoten zuzunehmen um den um den Grafen um den Baum aufzubauen so jetzt ist hier blauer Regel von einem Katz von einem Schnitt die Rede der keine blauen kann teilt und von von allen könnten da drinnen soll der kleinste genommen werden und der wird dann auch blau ist so diese kannten die wir schon zugenommen haben die sind alle blau kann ich jetzt leider nicht zu rechnen weil wir hier keine farbige Kreide haben und damit auch farbige Kreide ja mit ja rote haben war das wir jetzt nicht wieder sehr verwirrend wenn ich jetzt der Farbe Rot Semantik blau geben würde so von welchen Karte sie die Räder mehr von diesen Knoten die bis wir bisher hier haben gibt es natürlich kannten die aus dem Baum raus gehen solange wir noch nicht fertig sind am Ende wenn wir fertig sind gibt es die kann natürlich nicht mehr ja und dieser Schmerz der durch diese der diese durch diese kannten durchschneidet von diesen Karte ist hier jetzt ganz konkret bei Priem die Rede was die blauer Regeln sagt ist wir nehmen Einschnitte keine blauen kann enthält das ist bei dem wir die volle weil auf der Fall weil alle blauen Karten auf der einen Seite von diesen Schnitt sind hier so wies gezeichnet habe auf der inneren Seite aber bei den beliebigen Grafen ist natürlich kein Ende und kein Außen und von den im werden in denen die kleinste kannte sie keinen blassen Gesicht und nach ja auch blau und das genau das was Prell macht immer mal an das ist die Kante mit kleinsten Gewicht von den in dem wir die genommen und wir sind jetzt einen Schritt weiter geht damit gegangen dass deren Sohn Prinz der Sichtung eines der der so ähnlich aussieht wie der Xtra der Algorithmus von Crystal mehr der sieht etwas anders aus so ein Schnappschuss mitten drin wie sieht er so aus sie haben einzelne Zusammenhangs Komponenten so vielleicht so wo jeweils wo sie wird schon teilweise so vor sie jetzt jeweils schon ein innerhalb des Sommers comma der in Baum gebaut haben und zu sehr sich haben sie in der Regel auch noch einzelne Knoten als weitere zusammen auskommen 1. Triade zusammen Kohle mehr so das ist das das Schnappschuss vom Algorithmus von Kuske und sie gehen die Kanten bei Kruska in einer gewissen Reihenfolge durch nämlich von der von der von der mit weißen sich bis zu der mit großem Gewicht kann nehmen wir mal an wir haben jetzt einer was könnte jetzt die nächste kannte sein also dem man beispielsweise mal Anfall 1 das wäre die nächste kannte Mitleids mich nicht betrachtet worden ist diese Kante verbindet 2 unterschiedliche Zusammenhangs Komponenten das hat wird reingenommen dann wird sie blau zusätzlich zu den andern blauen kann die wir schon haben oder andere Situation ist das ist 2 Knoten verbindet die zur selben Zusammenhangs Komponente gehören dann wird diese kannte nicht in dem Baum aufgenommen und wir sahen in diesem Schema das Sie dann ausgehebelt wird das ist die zweite Variante das war die blaue jetzt kommt die rote Rede blaue bei schnitten oder Regel bei Zyklen wo was jetzt da hierbei Zyklen und wenn in einem Züge sagt die rothaarige kann ich immer noch die schwerste kannte rot färben und die Variante ist erhalten also ich brauche mich nicht darum zu kümmern dass diese kannte also ich brauche mich der nicht darum zu gehen dass sich diese Kante weggeschmissen habe nicht im Baum eingefügt habe ich brauche sie nicht es gibt einspannen der diese kannte nicht enthält und auch alle andern rotgefärbten kann ich enthält so warum ist dass es die schwerste kannte die rotgefärbtes na ja alle allen Karten hier sind vorher berücksichtigt worden also wir wegen der in aufsteigender Sortierung durch also sind alle andern kann auf diesen Zügel leichter oder höchstens gleich wieder also es das sicherste kannte die letzte die wir Wölfin die Anzüge schließt ist immer die schwerste kannte dieses zügelt die können wir dann rausschmeißen nach dieser roten regeln wenn deren Züge haben der bis jetzt noch keine rote kannte hatte und Alanen kann man blau dann nehmen wir die die längste kannte nämlich die letzte betrachtete beide dabei groß kahl und Fernseher Wort so
wie Algorithmus der ist in allgemeiner Betrachtung ganz einfach wir beginnen damit dass alle kann kein Leben haben und solange es eine Kante gibt die nicht geregelt ist ganz allgemein wählen wir aus welche kannte wir nehmen also ob wir die blaue und die rote Kant die oder die blaue oder die rote Regel an werden und wir werden bei der blauen Regel beliebig aus welchen Schmidt wir nehmen wenn wir mit diesen besagten später nehmen so Arbeit bringen wenn man eine beliebige später nehmen zum dabei irgendwo oder Wir haben die Wahl entweder blaue rote Riedel und beliebige Züge Züge hier bliebe schnitt hier und am Ende wenn die Antillen Orwellsches alle wird es alle eine blau oder noch unterhalten haben am Ende der Output den denn sie rausgehen sind die blauen kannten schon gesehen Gross Gaal und Bremen sind nichts anderes als 2 Spezialfälle dieses allgemeinen Schemas was sie da unter den Punkten 1 bis 3 hier lesen können so die Behauptung
ist das ist jetzt eine stärkere Behauptung als nur die Behauptung dass Priem oder Kruska korrekt ist die Behauptung ist dass dieser Algorithmus egal wie wir vorgehen egal ob wie es uns gefällt wann wir die blau von mir die rote Regel anwenden sofern es noch keinen gibt wurde sie anwenden können das Endergebnis ist immer egal wie das machen ein minimal spannender Baum das bedeutet insbesondere scolaire da ja Premont und Kruska nichts anderes als Spezialisierung ist ein robustes ist damit auch bewiesen dass bringen große korrekt ist und dass sich das zum Beispiel bei Ich habe die Beweise der Korrektheit der primum groß gerade in der meiner vorlesen geht es vorgemacht Einsicht dass das Interesse wenn sich das nochmal anschauen wollen dann sehen Sie dass diese Beweise verdammt ähnlich sind zu dem was jetzt hier kommt so
wir zeigen dass die invariant gilt also was muss man beweisen um zu beweisen dass ein Algorithmus korrekt ist und ein minimal spannen Baum konstruiert man muss beweisen 1. der Algorithmus tut nicht gut möglichst ähnlich ist halt nicht durch 0 kräftig auf ein falsches er man so das kann ich existiert und so weiter das denke ich ist einsichtig dass man diese das Schema so implementieren kann und die und die ganzen zuprostet und implementieren kann dass das nicht der Fall sein wird zweitens muss der Algorithmus terminieren er muss das sich zum Ende kommen das ist offensichtlich auch der Fall weil wir in jeder Iteration eine kann das Leben und irgendwann sind alle Kanäle werden wir sind fertig 3. und das ist natürlich meistens das komplizierte einer Sache dass das was am Ende herauskommt bei Determination tatsächlich das ist was wir wollen in diesem Fall ein Minimum Spanner Baum so und der Königsweg um zu beweisen dass das was herauskommt ein minimal spannender Baumes ist ist
wenn man wirklich saubermachen will beginnt zurück
zu Variante diese Variante mit vollständiger Induktion zu beweisen Induktion über die Anzahl der schon durchlaufen Iteration spricht über die Anzahl der schon geregelten Gefährten kannten so wenn diese dann schauen Sie wendet schauen sich diese Variante an wenn der A Algorithmus fertig ist wenn sämtliche kannten geregelt sind und wir haben findet geschafft bis zu diesem Zeitpunkt inklusiver diesen werde durchzuhalten dann sagt diese Invariante die blauen kannten sind ein minimaler spannenden bauen und die roten könnten die anderen denn ich wissen immer spannen Baum drin sind ja das haben Sie bei mir geht's 2 immer wieder gesehen wer von den beiden beim Energie zu 1 okay kurz die einer müssen sich also an sich immer gewöhnen was glaube ich in früheren Jahren sowieso nicht so viel mit Beweisen dar da passiert ist die Aussage dieser Invarianz der geht zum Zeitpunkt der Termination wenn alle kannten geregelt sind in die Aussage über die blauen kann sind immer spannend bauen und Kanten sind da heißt wir müssen also nur in Anführungszeichen zeigen dass diese in Variante durchgeführt wird immer erhalten
bleibt durch den Algorithmus sind durch von
Iteration zu Iteration so verschieden zum Beginn mit der Nations Verankerung Ausgangsituation keine kann das Gelege damit wird auch die Aussage der Variante trivial wenn es keine
blauen keine roten kannte gibt dann wird dieses Jahr jeder er müsste enthält die die die Virenmenge als Teilmenge diese Aussage es trivialerweise führt am Anfang wenn wir keine Kanten geregelt haben
so was also zeigen müssen ist den Induktion das kennen Sie aus der Mathematik das meistens der Nutzen meistens nicht immer der Nutzungs- Anfang das einfacher ist unter Induktionsschritt das etwas kompliziertere wir müssen zeigen wenn wir in in Schritt 2 hier in einer Iteration die blaue oder die rote Regel an korrekt angewandt haben das dann in Wein der nach Dieseltraktion immer noch erfüllt ist wenn ende zum Voraussetzung wenn sie vorher erfüllt war so weiter W wie das mit Ihnen also sind wahrscheinlich eher in zu uns der beweise gewöhnt für Summenformeln oder ähnliches in der Mathematik da muss man vielleicht ein bisschen Umdenken wie das dann aussieht in so einer Situation dass wir mit Edition die Korrektheit eines Algorithmus beweisen also erstmal mal die Korrektheit einen Variante Ostern die Korrektheit ist das Ergebniss ist vor
so es ist entweder die blaue oder die rote Regel wenn es die blaue Regel ist haben wir nicht im Bild genau so wir haben die Blau Regel angewandt das heißt wir haben einen Schnitt im Grafen identifiziert der sie so angedeutet durch diese gepunktete Linien das da mögen natürlich noch viel mehr kann mehr sein als nur diese beiden wir haben eine Kante herausge nur gewählt wie ein Einschnitt gewillt genau gesagt und wir haben die Karte mit kleinsten Gewicht in diesen Schnitt um eine K einen Einschnitt der Kalender blauen kannten bisher enthält das war die blauäugige wie müssen Einschnitt wegen dennoch noch keine blauen kann enthält wir nehmen in diesem Schnitt die kürzeste kannte und die für den zu machen sie zu einer blauen kannte wie sieht die Argumentation dass das korrekt ist es war Fallunterscheidung ist dieser für uns so vertraut wir wissen nach Invariante meine uns Voraussetzungen es gibt einen Baum ein minimal spannen am Baum T der bisher alle bisherigen blauen kannten enthält und alle beziehen und kann nicht enthält das ist die Nation Voraussetzung das die Variante vor diesem Schritt Geld wir wollen zeigen dass sie auch nach diesem Schritt gilt das ist immer Spannungen auf gibt so dass dieser T Baum die wenn diese kann die wir ausgewählt haben in ist es gar nicht so zeigen wir am eine neue blaue kannte eingefügt die auch er die auch in diesem ominösen Baum T ist für den der die gar nicht kennen wir wissen nicht wie dieser Baum aussieht gewisse existiert für diese Filme sie kann ein und wenn die tatsächlich in diesem Baum drin ist den wir uns vorstellen gedanklich von dem wir nur wissen existiert dann ist alles paletti dann ist die invariante trivialerweise fortgesetzt besetzt worden alle blauen kann inklusive der neuen sind in diesem ominösen Baum T E jetzt andere Situation wir fügen diese kann ein aber in diesem ominösen Baum den wir gar nicht kennen von dem man nur wissen dass ein minimal spannend ist und das existiert in dem Moment da nicht drin so was machen wir denn da Obst erst mal durchlaufen offen Knopf und dann kommt da mehr dann wenn eh nicht drin ist dieser Baum und sehr minimal spannen Baum T ist es so ein Baum das heißt es gibt irgendwo einen Weg zwischen diesen beiden Enkel und diesen Baum weil zwischen je 2 Knoten des Grafen jeweils einen Weg in diesen Baum gibt ja irgendwie rum gibt es einen Weg der die Beine in Kloten von unserer ausgewählten kannte ihr verbindet und natürlich muss dieser Weg auch irgendwo mindestens einmal er könnte mehrfach sowie in der C Konzert gehen aber mindestens einmal muss er diesen Schnitt überwinden insoweit kannte er strich wieder hier so wir haben aber die kannte E besonders ausgewählt nämlich die in diesen Schritt minimal das bedeutet dass diese kannte ich strich auch über die so schnell drüber geht nicht leichter kürzer sein kann als die von uns ausgewählte kannte jede das bedeutet wir können in der diese ihr strich gehört zu diesem ominösen bauen die nicht aber wir können ich durch rausschmeißen aus dem Baum halt falsch ich durch rausschmeißen aus diesen blau umbauen und dafür E einfügen damit können wir keine Verschlechterung haben weil ja leichter ist als ich strich oder gleich leicht wie kriegen wieder einen neuen Baum aus der er enthält aber nicht mehr strich und damit sind wir wieder auf der Situation die wir vorher waren haben einen neuen Baum der nicht schlechte das Gewicht haben kann als dieser im müsse von dem wir wissen dass alle blauen kannten enthielt die wir bis dahin hat er gewählt haben der meine neuen Baum konstruiert der dieser hinzugenommen erkannte Ehe mit enthält zusätzlich diesen blauen könnten und damit haben wieder kein Problem mehr wir haben wieder einen Baum gefunden wir wissen nicht wie er aussieht aber wir haben trotzdem gefunden der alle blauen Kanten und keine rote der enthält das ist vielleicht müsse starker Tobak jetzt für die eine oder andere von Ihnen vielleicht verstehen so auch Leute sofort muss jetzt nicht unbedingt sein dass sie sofort verstehen ja nein dies nicht blau weil es ist sie darauf auch gar nicht blau sein weil der Schnee den wir gewählt hat also zum Protokoll für die Aufzeichnung die Frage war ob die kannte ich Durchmischung blau sein müsste Nein der Schnitt enthält ja nach Voraussetzung keine blauen kann gewählt dennoch keine dauern kann enthält ich strich ist nicht den blauen kann halten ich Strich ist in diesem ominösen Baum enthalten der wiederum alle blauen kannten plus Umbau weiter enthält wir haben wir werden die kleinste kann das ist ich durch ist nicht kleiner sie
ist im Schnitt nicht kleiner siehst größer oder gleich die kann nicht größer sein das ist hier noch auf der Folie gesagt weil nach Einnahme ist der dieser Baum minimal ja wenn ich dich schwerer wäre als sie hätten wir durchweg Name von strich und Hinzufügen von E 1 einen kleinen einen leichteren Baum gefunden Widerspruch zueinander Sabor minimal war es kann nur so sein dass ich Strich und die tatsächlich gleiches Gewicht haben so dass wir also von einem minimal von dem Baum zum um andern minimal spannen umgekommen sind das ist ein bisschen abstrakt jetzt vielleicht aber wir versuchen Sie es nochmal nachzuvollziehen stillen Kämmerlein vielleicht auch die Aufnahme werden sofern sie mal dann irgendwann mal fertig ist und und abrufbereit ist diese Aufnahme mit hineinzunehmen und dann denke ich wird ganz schnell der Wunsch noch fallen unter den deutschen bei Ihnen nicht fällt denken wir gerne nochmal vielleicht darüber reden und versuchen der Groschen pfennigweise fallen zu lassen so Butterwegge es jetzt ähnliche Situationen nur ein Gerät anstelle vonstatten betrachten der Züge so wir haben jetzt die Situation wir haben 10 Züge ausgewählt irgendwie an der Kruska gesehen wie wird auf diese Züge gekommen sind aber allgemein sagte die rote Regel wir suchen uns irgendein Züge mehr dennoch keine rote Karte enthält man von dieser kannte man von diesen Zügel die schwerste kannte und werden die Ruth also ist dieser Züge das blau können enthalten aber darf keine roten kann das enthalten so auch hier wieder dasselbe Strickmuster der Argumentation wir haben einen Baum den Virus denen von dem wissen wir nach Induktion Voraussetzung die könne immer davon ausgehen dass das was wir beweisen wollen bis dahin korrekt ist wir müssen zeigen das ist im nächsten Schritt auch die Korrektheit erhalten bleibt das ist der da sind das ist die Logik von Induktion von Fasching so so wir haben diesen Baum T der bis dahin bevor wir diese Karte rot gefärbt haben alle blauen kann enthält und noch keine rote Karte enthält so da wenn die Säcke wieder dieselbe Logik umgedreht wenn diese kannte tatsächlich nicht in diesem ominösen Baum ist ist trivialerweise invariant erhalten geblieben es gibt diesen dieser ominöse Baum enthält alle blauen bisherigen Nein voraus sind alle enthält keine bisherige rote und auch diese neue rote nicht so also hier ist wieder die er ungenauen spiegelsymmetrisch die die schwieriger Fall werden die in diesem Baum ist wir haben es plötzlich eine kannte diese rot färben obwohl sie in diesem ominösen Baumwolle ist so was ist hier die Logik ab mehr gut genau dass die Logik werden E tatsächliche Baum kannte ist dann wissen Sie Sie können wenn sie eine kann daraus im Vorfeld der Baum in 2 Teile der eine Teil kann es gerade wird gerade mit kannte zum glatt ist dann ist der eine Teil trivial bestehen aus einem Knoten allgemein besteht aus 2 Gericht ihren daher wurde so in dem die kann aus der Westerfeld in 2 Teile daher wissen wir in diesem ominösen Baum Täter das Herrn Baum ist muss aber keine gegeben haben die diese beiden Teile miteinander verbindet dass die Karte Gespräch sie sehen dass es völlig spiegelsymmetrisch und wieder dieselbe Logik gilt wir haben ja jetzt umgedreht die schwerste kannte genommen das heißt diese KDE strich die im Baum wir kann ich schwerer sein als die Karte in die wir rot geredet haben und wenn wir also diesen ominösen Baum hernehmen der gestrichen hat aber nicht E und wenn ich nehme er strich raus und packen ihre einen dann umgekehrt Schädigung wir wohnen jetzt neben raus und Paten stattdessen Moment hat halt halt Ich hab's jetzt ich habe jetzt selber verwirrt wir also in diesem Fall das E in dem Baum drin ist ach so genau der Züge der muss natürlich da wie schön ich weiß das was in einer gekommen der Zügel der muss natürlich auch eine kann der enthalten der diese beiden Teile miteinander verbindet so sehr sehr keine Züge dass sie kannte er strich und wenn wenn wir jetzt Ihr aus dem aus dem Baum und ich dich einfügen können Sie keine habe damit das Gericht höchstens reduziert oder gleich gelassen wir müssen es gleich gelassen haben wir können sich reduziert haben denn der Voraussetzung war das sehr wird er die Ausgangskonfiguration einspart eine minimal spannender Baum also muss das Gewicht das neue auch entspannter Baumes muss das Gericht gleichgeblieben sein Wesen von einem niemals einem Baum zum anderen worden man bei schon Baum gekommen und habe mit diesen neu konstruierten immer spannen Baum wieder die in Bayern der Fall das ist einer der Punkte wo ich sagen würde es ist nicht so dramatisch wenn Sie das jetzt noch nicht so richtig ganz hundertprozentig durchschaut haben ich bin zuvor ersichtlich dass das gut möglich ist das dann im stillen Kämmerlein so weit nachzuvollziehen dass die Glühbirne überm Kopf anfängt zu leuchten so wir
haben jetzt noch nicht wir haben es noch nicht gesehen dass der Alkohol tatsächlich terminiert da war ich vorhin etwas ich habe einfach gesagt Determination da sehen Sie hier jeder einzelnen Iteration wird eine kann der blau oder eine Karte rot gefärbt der mir endlich viele Karten also nach endlich vielen Schritten habe Determination nur ich habe dabei natürlich noch eine Kleinigkeit ausgelassen nämlich ob wirklich in jeder Iteration auch eine kann existiert auf der Sie die bitte auf die wieder blau oder die rothaarige an den können ich hatte also ich habe ihn falls Sie mir bis eben geglaubt haben dass Determination kein Problem es habe ich ihn da jetzt etwas untergejubelt wo eigentlich ein bisschen kritisches Nachfragen dann angebracht wäre wobei ich natürlich nicht erwartet dass sie jetzt hier in der Situation der Vorlesung unbedingt diese kritische Nachfragen sie stellen aber später im stillen Kämmerlein spätestens sollten Sie sich diese Stelle der diese Nachfragen stellen und so warum ist in jeder Iteration entweder die blaue oder die rote Regel anwendbar mindestens eine von beiden so dass sie also immer weitergehen können dass er würde sich mit neuen aufgeschmissen ist so wird also wir sind der Situation dass wir noch nicht alle kann geregelt haben soll sie nicht mehr zu zeigen wir noch mindestens eine Karte diene weder Rot noch blau ist die Variante sagt uns immer zum Vorsitz wieder dass die blauen kannten Teil eines brennenden Baumes sind also mit einer Worten Sie sind ein weit ist ja nicht Teil eine Spannung Baums zu sein also Teilmenge Spannungen zu sein ist ja nicht aus als die Aussage sind ein er ist ein Wald dieser Wald könnte natürlich auch nicht immer schon andere hatte isolierte Knoten enthalten ja das ist ein trivialer Baum innerhalb eines Waldes so er hat DEN Knoten U und V er es war meine Fallunterscheidung wo genau dann jetzt Ruth und wo wo jetzt wo wir sehen im Fall eines können wie die rote Regelanwendung dann im Fall 2 die blaue und einer dieser beiden Fälle würde immer auftreten diese beiden Fälle zerlegen geben alle Möglichkeiten über der seine Möglichkeiten so der eine Fall ist das die beiden momentan die beiden in Knoten von dieser Kante zum selben Baum gehören dass wir genau eine Situation die für Groß vorhin zieht er es skizziert hatte wir können jetzt die rote Regel anwenden der nämlich das muss in dem Moment die schwerste könnte sein weil alle anderen könnten in dem Moment blau sind und damit Teil eines minimal spannen Baum also muss diese kann die wir jetzt hier gewählt haben die schwerste sein also können wir sie Rodleben er nach der roten regelt ist immer die schwerste kann in Züge der zweite Fall er ist das unterschiedliche Bäume müssen habe ich das nicht noch gezeichnet ja hier sehen sie sogar noch das Bild was ich vorhin gezeichnet habe für Cruz Gaal was jetzt hier sinngemäß im Allgemeinen der so ist dieses Bild sehr wie sie skizziert habe enthält natürlich auch den 1 er das Bild verloren muss Bremen als Spezialfall so und wenn sie aber wenn diese kannte aber 2 unterschiedliche ja die 2 unterschiedliche kannten 2 unterschiedliche schön so unterschiedliche Bäume miteinander verknüpft dann können wir zwischen diesen beiden unterschiedlichen Bäume Einschnitt sehen Unsinn genau bei der blauen Rede das wir da jetzt eine Kante blau werden können okay hier Sonderfall da drin die Idee hier ausgedrückt ist die wie die müsse ungeregelte kann der und da sieht es so aus vielleicht für Sie für mich auf den Moment dass die die Logik des Beweises die ist wir zeigen wir können diese Kante lebe Rot oder Blau klingt irgendwie plausibel aber so müssen ja gar nicht zeigen wir müssen zeigen wenn es eine ungelöste kannte E gibt dann können wir noch irgendeine ungeregelte kann der leben das muss ich aber nicht unbedingt in sein solange Sendung Label bekannte gibt ist der Algorithmus noch nicht aufgeschmissen aber es muss nicht diese kann das andere wird nämlich stattdessen die leichteste kannte die in die leichteste kannte und das ist dieselbe Logik hier auch es muss auch nicht unbedingt diese kannte sein die rot geregelt ist also sehen ist ne Menge von hinten durch die Brust ins Auge da muss man sich Schritt für Schritt vielleicht einmal auseinander Vierteln vielleicht wenn Sie da gar nicht in der steigenden machen sich vielleicht mal noch Beispiele dann denke ich klar war gut eine letzte noch Bemerkung dazu dass diese ist nämlich nicht deterministische ist das also das bedeutet es ist nicht von vornherein spezifiziert in welcher Reihenfolge wir kannten werden und ob die jetzt rot oder blau liegt in der Regel anwenden wollen und dafür jeweils eine passende kannte finden wollen sondern wenn wir effizienter mit ihren wollen zum Beispiel Priem oder Gross dann müssen wir genauer sagen in welcher Reihenfolge mit welchen kannten der welche Regel an so damit haben wir
den Algorithmus diesen allgemeinen Algorithmus vollständig behandelt der Premium groß gar als 2 Spezialfälle enthält jetzt kommen wir noch mal ganz kurz
zu einem bösen Thema hat die Sache noch mal viel allgemeiner zu sehen haben keine Sorge man kann es verstehen es ist es gibt den positiven beweist dass Menschen Lage sind das zu verstehen auch Studierende der Algorithmus von Kos K L ist ein ist das was man einen Kuli die Algorithmus denn einen gierigen Algorithmus nennt er geht die Kanten von der billigsten keine bis zur teuersten könnte durch und bei jeder kannte guckt da kann ich die einfügen wenn er tu ich das ja wenn Sie zum Beispiel sich vorstellen auf die Art und war euch sollte nicht ja nicht für die mich hier nicht aufstützen oft auf der auf der Steuerung der Anlage sind geht durch alles aus wenn sich vorstellen sie gehen auf die Art und Weise vorbei kürzesten Wegen ja immer die billigste Karte zu dem passt ja was nicht nein das funktioniert natürlich nicht bekommt im Bild sind dabei aus komme wahrscheinlich mein Weg raus geschweige den kürzesten Weg das liegt daran dass das bei die funktioniert so primitiv dass wir uns sicher sein können wir gehen einfach die könnten den in dieser Reihenfolge durch und das was am Ende rauskommt es garantiert und unter allen Umständen Christ in Spanien Minimallösung das liegt daran dass MSC minimal spannen Baum eine bestimmte strukturelle Eigenschaft hat und diese strukturelle Eigenschaften Mahnmalprojekt und alle Problemstellungen diese die diese spezifische strukturelle Eigenschaft haben für die Geld dass dieser Krieg die Algorithmus immer immer zusammensammeln vom billigsten zum teuersten dass der immer die optimale Lösung liefert sonne schönes Werkzeug mehr der Name Manfred kommt daher dass die Spalten einer Matrix im im Sinne Linie Unabhängigkeit auch Madrid so ist Madrid das ist eine Menge eine endliche Menge das ist hier nicht verzeichnet aber das aber es ist der immer eine endliche Menge Madrid nie definiert auf unendliche Mengen und wer mit was wir das hier was wir haben ist eine Menge von Teilmengen von der kann dieser Grundmenge die die man meint
gerne mal durch werden der Dämmung ich
so was bedeutet was bedeutet diese Bedingung was bedeutet das alles an den konkreten schönen Beispiel Spanne Bäume spannende Wälder also die Karte die die Grundmenge Idee ist bei uns bei unserm minimal sparen Baum Problem tatsächlich die Kanten mehr ist die Menge aller Welt sowas Eigenschaften hat die Menge aller Wälder auf einer gegebenen könnten Mengen eingeben trafen mehr die Lehre kann man es natürlich auch im Wald ein trivialer Arbeit bei der trivialen Wald wenn ich eine wenn ich einen Wald B habe und also Teilmenge von B Ja ich nehme immer ein und ich nehme noch kann raus das ist ebenso wie Wald das hat diese zweite Bedingung wenn Teilmenge B ist Besen Wald ist auch im Wald wobei übrigens dann die 1. denn natürlich Rillen dahinter ist aus der
zweiten Bedingung führt natürlich sofort das 1. so jetzt kommt das dieser da das müssen wir dann anhand des Beweises auch genau klären was da eigentlich steht was das eigentlich bedeutet ich weiß nicht inwieweit Sie da in der Regel einer Gebäude eingestiegen sind aber aber einer endlichen Menge von aber da oder Lichtmenge aber endlich Menge bei einer endlichen Menge von Vektoren denn ist diese Eigenschaft wieder als kunterbunt 3 steht gerade Steintische Austausch falls in das begegnet ist Agora oder nicht okay vergessen sie wieder was ich gesagt habe oder vergessen Sie es nicht und gucken Sie bei Gelegenheit mal an das wie gesagt wir unabhängiger Vektoren sind ein anderes Beispiel für Madrider so was steht da dass das war mal links liegen was hier im Punkt 3 steht weil das ist ein schönes Beispiel dafür dass man Dinge manchmal durch den Beweis besser versteht überhaupt es gut versteht als wenn man nur versuchen wollte das Theorem selber für sich zu verstehen der Beweis konstruierte praktischen Beispiel dafür oder diese Telekom für jede Situation wissen sowieso jetzt mehr oder weniger fertig für heute fast mehr den so die
Aussage hier ist die wird nicht bewiesen hier die Beweise sich in der bei Wahl Optimierungsalgorithmen da wenn wir in Madrid haben dann wird dieser wie Algorithmus FOCUS gerade eben der G es für minimal spannen Bäume ist diese kann und wie Algorithmus dass wir das für alle Elemente nach aufsteigender Tiere Folge durchgehen und gucken passt rein was rein wenn nicht vergessen was und kommen Sie wieder an so einmal Droid ist der Kanonenschläge Allgemeines bezüglich beliebiger Gewicht in beliebiger K erkannten die Richter optimal insbesondere Cola Kuss kann es auch gemacht er was hier nicht formuliert ist aber was ich Ihnen genommen dazu sagen möchte ist dass das nicht willens ist wenn das keiner Projekt ist das nicht diese diese 3 Eigenschaften mit aufsteigender Hässlichkeit halt wenn es keine Madrid ist dann kann man immer eine Gewichtung finden bei der Algorithmus Blödsinn produziert das in diesem Sinne ist das also nicht die optimale Lösung produziert in diesem Sinne ist Theorem 6 tatsächlich über die für die konkrete Formulierung und diese Folie hinaus eine Äquivalenz in Madrid ist dann funktionierte Chriac und muss für jede Gewichtung wenn es keine Madrid ist funktioniert der Kinder muss für mindestens eine Gewichtung nicht mehr sein heißt natürlich auch für unendlich viel für unendlich viele andere Gewichtung funktioniert auch nicht so
das was hier bewiesen wird aber dazu kommen wir
heute nicht mehr ist da ist Ernest die Wälder in einem ungerechten Grafen bilden einen Madrid uns wenn wir den Beweis
durch gehen dann wird denke ich klar werden was diese häßliche 3. Zeile hier zu bedeuten hat wenn wir vielleicht dann noch mal an einem Beispiel Länder unabhängige Vektoren man auch nochmal betrachten kleine Änderung an denen Algebra und dann haben wir dieses hässliche Thema auch ganz schnell wieder hinter uns gebracht und dann können wir beim nächsten mal konsequent von den ungerichteten Grafen weg gehen und den spannen Bäumen hin zu etwas meinen gerichtete Grafen und darauf sozusagen das Äquivalent zu minimal spannen wollen das man sich dann Brunch ins vielen Dank
und denken Sie bitte daran 1. Abgaben noch so weit Bedarf besteht hier heute und denken Sie bitte noch mal daran dass sich jeder Übungs- Termin geändert hat
Feedback