Optimal Trees and Branchings
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| 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 | |
| Identifiers | 10.5446/21476 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
2
3
4
5
7
8
9
10
11
12
13
14
00:00
Connectivity (graph theory)Graph (mathematics)SequelMaß <Mathematik>Function (mathematics)SequenceProof theoryInductive reasoningLaufzeitGradientKanteGraph (mathematics)TrailGrand Unified TheoryInvariant (mathematics)State of matterQuoteMandelbrot setComputer animation
09:38
Proof theoryInductive reasoningConnectivity (graph theory)Graph (mathematics)Vertex (graph theory)Zusammenhang <Mathematik>Connected spaceLaufzeitList of anatomical isthmiPlatteKanteRecursive languageZahlGraph (mathematics)Moment (mathematics)Direction (geometry)QuoteSet (mathematics)Network topologyCalculationCloningGradientSpanning treeIterationComputer animation
19:06
Connectivity (graph theory)Graph (mathematics)Mathematical optimizationAreaVertex (graph theory)Sign (mathematics)Connected spaceNetwork topologyMaxima and minimaEnumerated typeEstimationExponential functionFactorizationLaufzeitKanteSet (mathematics)MinimallösungNetwork topologyExponentiationGreat circleGreatest elementOrder of magnitudeStress (mechanics)Universe (mathematics)CalculationSpanning treeEnergieQuoteSubsetVertex (graph theory)KantenmengePrime idealPerspective (visual)Engineering drawingComputer animation
26:43
Enumerated typeLinear mapFunction (mathematics)Transformation (genetics)ForestWeightSocial classEquivalence relationMaxima and minimaSign (mathematics)Mathematical optimizationEstimationLineare TransformationSpanning treeLösung <Mathematik>Greatest elementStructural equation modelingEckeOptimumLength of stayMaximum (disambiguation)LaufzeitFunction (mathematics)Computer animation
34:08
Mathematical optimizationMaxima and minimaEquivalence relationForestWeight functionNetwork topologyComplementarityWeightAiry functionChainProof theoryEstimationGraph (mathematics)KanteSpanning treeDirection (geometry)WeightZahlComplete graphDesire pathNetwork topologyLösung <Mathematik>Equivalence relationSign (mathematics)LaufzeitGraph (mathematics)MomentumLengthMaximum (disambiguation)SummationComputer animation
42:38
Sign (mathematics)Graph (mathematics)Connected spaceInvariant (mathematics)Mathematical optimizationCategory of beingRule of inferenceMaximaler BaumKanteFilm editingDirection (geometry)Spanning treeNetwork topologyConnected spacePrime idealInvariant (mathematics)LaufzeitIterationGraph (mathematics)ZahlSocial class
51:08
Category of beingInvariant (mathematics)Rule of inferenceMathematical optimizationChain complexKanteNetwork topologySpanning treeFilm editingGreatest elementPoint (geometry)Invariant (mathematics)IterationZusammenhang <Mathematik>Stress (mechanics)Physical quantityTriadeConnected spaceCoefficient of determinationComputer animation
59:38
Invariant (mathematics)Rule of inferenceMathematical optimizationCategory of beingVertex (graph theory)KanteNetwork topologyFilm editingInvariant (mathematics)IterationMathematical inductionSpanning treeSet (mathematics)SubsetMathematical inductionSpanning treeMathematicsMoment (mathematics)Invariant (mathematics)EnergieComputer animation
01:09:20
Mathematical optimizationInvariant (mathematics)ForestVertex (graph theory)Network topologySpanning treeFilm editingNetwork topologyStress (mechanics)Chain complexKanteMoment (mathematics)LogicSubsetForestInvariant (mathematics)IterationCoefficient of determinationComputer animation
01:19:03
Rule of inferenceNetwork topologyVertex (graph theory)Invariant (mathematics)ForestMathematical optimizationSubsetPhysical systemMatroidElement (mathematics)Independence (probability theory)Category of beingFunction (mathematics)Greedy algorithmNetwork topologyEuclidean vectorSet (mathematics)LinieForestWeight functionFinite setSubsetFinite setKanteEquivalence relationLogicMatrix (mathematics)Moment (mathematics)MinimallösungPhysical quantityInfinite setLuminous energyMatroidWeightPrime idealFilm editingTheoremLinear independenceKantenmengeAlgebraSpanning treeComputer animation
01:28:45
Proof theoryPhysical systemMatroidSubsetMathematical optimizationElement (mathematics)Independence (probability theory)Function (mathematics)ForestMatroidEuclidean vectorAlgebraNetwork topologySpanning treeDirected graphGraph (mathematics)Computer animation
Transcript: German(auto-generated)
00:01
präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits, ich darf Sie herzlich für heute begrüßen. Ich mache mal die Tür zu, sonst ist es noch ein bisschen laut hier draußen. Vorab nochmal, wer gerne noch Hausaufgaben
00:26
abgeben möchte, hier ist ein Stabel, können Sie jetzt tun oder vielleicht nicht vergessen, wenn Sie es erst am Ende machen wollen. Auch für Sie Hausaufgaben sind hier abzugeben, wenn Sie es nicht per E-Mail verschicken. Sie haben mitbekommen, dass sich der Übungstermin
00:41
geändert hat. Okay, gut. So, gibt es noch etwas organisatorisches zu besprechen von Ihrer Seite aus? Scheint nur humorvolle Dinge zu besprechen zu geben. Dann können wir ja wieder zu etwas
01:00
Ernsthaftem kommen, zum Beispiel zu effizienten Grafenalgorithmen, wenn Sie nichts dagegen haben. Hier waren wir stehen geblieben und was noch aufsteht ist der Beweis der Korrektheit beziehungsweise der Laufzeit. Da hatte ich ja das letzte Mal gesagt, gut, dass die Stunde vorbei ist, dann kann ich nochmal Gelegenheit, weil mich etwas irritiert hat, da werde ich dann drauf
01:22
zu sprechen kommen. Sie erinnern sich nochmal, worum es eigentlich geht. Die Problemstellung, um die es geht, ist eine ganz einfache. Sie haben einen Grafen, der praktischerweise in
01:41
jedem einzelnen Knoten einen geraden Grad haben sollte. Um den geraden Grad hinzukriegen, machen wir am besten nochmal hier hin. So, hier kriegen wir jetzt geraden Grad. 1, 2, 3, 4, 5 haben wir immer noch keinen geraden Grad. Dann machen wir es anders. So, hier
02:09
geraden Grad, 1, 2, 3, 4 hat geraden Grad, also so. Das gibt mir nochmal Gelegenheit die Kamera zu justieren. Ja, genau, gute Idee, dass das auch wirklich genau das Bild ist.
02:26
Gutes Bild? Kann man nichts sagen. Ja, okay, gut. Und die Aufgabe besteht darin, einen geschlossenen Weg zu finden, der jede Kante genau ein einziges Mal enthält, der genau
02:43
durch jede Kante ein einziges Mal durchläuft. Wir haben diesen Algorithmus hier schon beim letzten Mal gesehen. Vielleicht nochmal zur Grundidee. Wir laufen in gewisser Weise durch, den Grafen durch, so ähnlich wie das ist das Haus von Nikolaus, haben aber festgestellt
03:02
beim letzten Mal, dass das nicht ausreicht, dass wir dabei durchaus Teile des Grafens nicht sehen, wenn wir einfach so nach der Manier, dass es das Haus von Nikolaus einmal so durchlaufen. Deshalb haben wir hier diese recursiven Aufrufe an dieser Stelle nochmal
03:23
ganz kurz durchgegangen. Wir fangen an mit einem Weg, der aus dem einzelnen Startnoten besteht und unser aktueller Knoten X ist auch dieser Startnoten. Und solange wir am jeweils aktuellen Knoten noch Kanten haben, sie erinnern sich, Kanten werden immer gleich rausgeschmissen, weil sie später nur stören. Wenn wir sie durchlaufen,
03:45
haben wir die Kante rausgeschmissen. Dann holen wir uns eine Kante, solange wir vom aktuellen Knoten aus noch weiter kommen können über eine Kante, holen wir uns eine Kante, fügen die ein, den anderen Knoten fügen wir ein und dieser andere Knoten ist dann der aktuelle Knoten. Das heißt also, wir gehen von einem Knoten zum anderen und schmeißen dabei diese
04:03
Kante, die wir jetzt eingefügt haben, aus dem Grafen raus. Und wenn wir jetzt mittendrin irgendwo diesen bisher konstruierten Weg haben, rufen wir noch mal Euler mit jedem Zwischenknoten auf, um genau dieses Phänomen zu vermeiden, dass wir an Kanten vorbeigehen,
04:26
die wir nicht erwischen. Ich denke, es ist einsichtig, auf diese Art und Weise erwischen wir alle Kanten, wenn wir das hier machen, erwischen wir alle Kanten, die von diesem
04:42
Weg ausgehen. Wir haben momentan diesen Weg, der geht irgendwie kreuz und quer und mit jedem einzelnen Knoten auf diesem Weg rufen wir noch mal Euler auf, sodass alles, was wir an Kanten haben, hier, was noch nicht abgegrast worden ist, also was immer noch
05:06
im Grafen drin ist, noch nicht gelöscht worden ist, an jedem dieser Knoten passiert dann noch mal, dass sich da weiter gefressen wird. So, und das Ergebnis ist dann jeweils,
05:25
wenn wir hier überall noch irgendwie weitere Sachen rangehängt haben, das Ergebnis von dem Ganzen geben wir zurück. So, zwei Fragen, warum ist das korrekt und warum ist das
05:41
tatsächlich lineare Laufzeit? So, Korrektheit, also worüber ich etwas gestolpert bin beim letzten Mal ist, Sie sehen das hier, dass der Beweis ein bisschen kurz gehalten ist, dass der doch einiges an relevanter Information vielleicht ein bisschen vermessen lässt. Ach so,
06:01
ich sollte noch dazu sagen, ich bin letztes Mal darauf hingewiesen worden, dass ich zuerst mit einer veralteten Version der Folien hier gearbeitet habe. Jetzt arbeite ich mit der aktuellen, das sollte aber jetzt bei dem, was wir letztes Mal und vorletztes Mal betrachtet haben, kein Problem für Sie sein. So, was ist der Grund dafür, was ist das Argument
06:23
dafür, dass der Algorithmus korrekt ist? Jetzt müssen wir noch mal klären, was Korrektheit heißt. Wir müssen natürlich voraussetzen, dass der Graph zusammenhängt ist. Wenn er nicht zusammenhängt ist, haben wir keine Rundtour, keine solche Eulagetour. Klar, also der Graph ist zusammenhängt und die Invariante ist jetzt die, da beachten
06:48
Sie, dadurch, dass das Ganze rekursiv ist, was passiert dann so an so einem Knoten,
07:08
bei dem noch mal rekursiv das Ganze aufgerufen wird. Was da passiert, so, das ist dieser
07:30
Knoten. Und hier sind noch ein paar Kanten, eine gerade Anzahl müsste das dann sein, nicht? So, eine gerade Anzahl, eins, zwei, drei, vier, fünf, sechs von Kanten, die da noch abgehen, die bis jetzt nicht abgegrast worden sind, weil wir eben von hier kommt,
07:44
da lang weiter gegangen sind. So, jetzt wird irgendeine Kante genommen, zum Beispiel hier und dann wird auf irgendeine magische Art und Weise irgendwo hintenrum wieder eine Kante erreicht, zum Beispiel hier. So, gehen wir noch mal zurück zum Algorithmus.
08:17
So, wir, genau, entscheidend hier ist auch, dass wir auch für eins das aufrufen. Das
08:21
heißt also, in diesem rekursiven Schritt rufen wir wieder rekursiv für jeden einzelnen Knoten, halt, das ist kein Knoten, hier ist ein Knoten, hier ist ein Knoten, für jeden einzelnen Knoten rufen wir jetzt rekursiv auf, sodass sich so nach und nach so ein komisches Apfelmännchen, Sie kennen das von der Chaos Theory, so Apfelmännchen, hier ergibt, so mit immer weiter draufgepappten Zyklen. Aber, weil
08:43
wir das auch mit eins aufrufen, wird dann nochmal rekursiv, innerhalb dieses rekursiven Aufrufs rufen wir es nochmal mit dem ersten Knoten dieses Weges auf, den wir hier konstruiert haben, ist gewährleistet, dass wir hier auch nochmal, solange hier bei diesem Knoten noch was frei ist, etwas finden und natürlich
09:06
wieder zurückkommen müssen, weil wir müssen immer zurückkommen, weil das der einzige Knoten ist momentan, der ungeraden Grad hat und solange wir geraden Grad haben, können wir immer weiter gehen. So, und in diesem
09:20
rekursiven Aufruf, ja, wir sind jetzt hier, erster Aufruf, hier haben wir zweiten Aufruf, darin wieder rekursiven Aufruf, hier drin, von diesem rekursiven Aufruf auf den, geht es wieder weiter, im vierten Aufruf, jetzt alles am Ende abgegrast sein wird. Das heißt also, dass keine Kanten mehr
09:45
übrig bleiben, die von hier aus, von diesem Knoten aus überhaupt erreichbar sind. Und weil zusammenhängend erreicht, erreichbar, denke ich, ist einsichtig, dass damit der gesamte Graf alle Kanten erreicht werden durch diese Rekursion. Widerspruch angenommen, es ist nicht,
10:04
es werden irgendwelche Kanten, es bleiben irgendwelche Kanten stehen. Naja, dann muss es auch irgendwo, wegen des Zusammenhangs, muss es auch irgendwo Kanten gegeben haben, die stehen geblieben sind, die aber inzidenz zu Knoten auf diesem bis dahin gefundenen Weg sind und die
10:23
wären, das ist ein Widerspruch, die wären 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 lineare Laufzeit, wenn wir jetzt, wie Sie sehen, hier auf den
10:44
Folien jedes Mal hier den ganzen bisher konstruierten Pfad durchgehen, sämtliche Knoten durchgehen, das habe ich mich noch mal in einer anderen Quelle schlau gemacht und siehe da, es ist natürlich nicht so, wie es jetzt zunächst einmal hier so aussieht, dass wir sämtliche Knoten noch mal durchgehen, sondern wir verwalten einfach in einer
11:04
Liste beispielsweise die Menge der zu diesen Knoten incidenten Kanten, die noch nicht gelöscht worden sind, diese Kanten laufen wir durch, diese Liste laufen wir durch und damit ist natürlich klar, dass wir jede Kante nur einmal angefasst haben, denn in dem Moment, wenn wir sie in dieser Liste angefasst haben, löschen wir sie sofort in
11:22
dieser Iteration. Das war der Punkt, wo ich letztes Mal in der Liste die Schwierigkeiten gekommen bin, mit dieser Laufzeit und Sie sehen, wenn in der letzten Version von Herrn Schiller erstellt, ich bin natürlich unschuldig, wenn der Beweis so relativ knapp gehalten ist, dann werden Sie mir nachsehen,
11:42
dass ich in dem Moment nicht so richtig wusste, wie ich das jetzt zu interpretieren habe, aber dafür hat man ja immer noch mal eine Woche Zeit, um das noch mal nachzuschauen und dadurch, dass wir diese Veranstaltung aufnehmen, ich hoffe, das funktioniert auch alles, dadurch können wir das auch
12:06
nachvollziehen, was eben nicht auf den Folien so hundertprozentig genau aufgeführt ist. Nochmal was zu den Aufnahmen, ich habe jetzt angefangen damit die Videos zu rendern, habe aber festgestellt, dass das ein irrer Zeitaufwand ist,
12:21
bzw. ich tue eigentlich in der Zeit nichts, aber ich muss dann immer, Sie kennen das von der Milch im Kochtopf auf der Herdplatte oder so, dass man dann immer mal dabei sein muss, also das funktioniert so nicht im Zusammenhang mit meinem Zeitplan, sodass ich mir da jetzt Assistenz suchen muss,
12:41
dass jemand, der sowieso im Gegensatz zu mir die ganze Zeit den ganzen Tag am Rechner sitzt, der das dann eben so nebenher machen kann ohne Zeitverzögerung. Tut mir leid. So, das hatten wir schon mal glaube ich gesehen das letzte Mal, für gerichtete Grafen gehen wir natürlich
13:01
nur immer in die Richtung der Orientierung der Kante und deshalb betrachten wir nur für jeden aktuellen Knoten immer nur die rausgehenden Kanten. So, historische Bemerkung hatten wir glaube ich das letzte Mal auch gesehen, er hat gezeigt, da wo er gelebt hat in
13:22
Königsberg, die Brücken, die sieben Brücken, hat er Glück gehabt, dass er nicht in Venedig gelebt hat, da hätte er ein bisschen mehr rumzählen müssen, dass die, wobei ich mal gelesen habe, beispielsweise Berlin hat mehr Brücken als Venedig. Ich hab's gelesen, ich weiß nicht, ob's stimmt, ich nehme man zu seiner Zeit noch nicht. Also
13:42
Venedig wahrscheinlich schon, aber Berlin war zu Eulers Zeit glaube ich, ja, es war kein Kuhdorf mehr, aber es war noch nicht so eine Metropole wie Venedig. Sie haben eine Frage? Ja? Sie meinen zu dieser Zeile?
14:02
Zu dem hier vermutlich. Also das ist das letzte Bild, was ich noch zeigen kann. Okay, also die Frage war
14:20
jetzt, wenn hier so rekursiv aufgerufen wird, warum kommt man wieder zurück, also warum bildet sich so ein Kreis? Gut, Argument, zu jedem Zeitpunkt, oder mal, ja,
14:47
dieser Knoten, wenn diese Kante gelöscht wird, dann hat dieser Knoten und dieser Knoten ungeraden Grad. So, wenn jetzt diese Kante gelöscht wird, dann hat dieser Knoten und dieser Knoten ungeraden Grad und so weiter, ja. So, wenn jetzt, was ist die Argumentation
15:06
genau? Wenn Sie auf einen Knoten stoßen, der gerade Grad hat, können Sie immer weiter gehen, ja, Sie kommen rein, also bevor Sie reinkommen, hat er gerade Grad, das heißt, er hat mindestens Grad 2, sonst können Sie ja nicht reinkommen. Sie kommen rein über eine Kante und das heißt, Sie können auch über eine Kante wieder rausgehen und das heißt, Sie können immer weiter
15:22
gehen, bis Sie zum Knoten mit Grad 1 kommen, ungeraden Grad. Und damit, mit diesem Argument, ist vielleicht ein bisschen von hinten durch die Brust ins Auge, aber wenn Sie sich das nochmal mit dem Haus vom Nikolaus in diesem kleinen Beispiel, sorry, aber das ist nun mal das Standardbeispiel dafür, wenn Sie sich das nochmal
15:41
klarmachen mit den, dieses Beispiel hat ja gerade genau zwei ungerade Knoten, deshalb ist es auch wichtig, dass Sie bei dem einen ungeraden Knoten anfangen, sodass Sie dann bei dem anderen ungeraden Knoten aufhören. Wenn Sie bei einem der anderen Knoten anfangen, können Sie das Bild nicht in einem Bezug hinzurechnen. Hat sich die Frage damit geklärt oder? Gut, Sie haben noch eine Frage. Laufzeit, okay.
16:22
Okay, also die Frage war, oder sagen wir mal so allgemein ist das die Problematik, Anzahl der Kanten, Anzahl der Knoten. So, eigentlich steht hier zu viel. Wir haben ja einen zusammenhängenden Grafen. Erinnern Sie sich noch bei einem
16:41
Minimal, nein, ein spannender Baum ist ein zusammenhängender Graf mit minimaler Kantenzahl vergebene Knotenzahl. Erinnern Sie sich nicht noch an die Kantenzahl, die ein Minimal spannender Baum auf n Knoten hat? Ja, an Knotenzahl minus eins, genau. Das heißt also, in einem zusammenhängenden
17:00
Grafen ist die Kantenzahl bis auf eins mindestens so groß wie die Knotenzahl. Das heißt also, die Knotenzahl ist asymptotisch dominiert durch die Kantenzahl. Eigentlich könnte man hier das n streichen und es wäre dieselbe Aussage, da der Graf zusammenhängt ist. Also ich bin jetzt nicht direkt auf Ihre Frage eingegangen, aber ich
17:21
glaube, ich habe Sie trotzdem beantwortet. Gut. Ich denke, das hat Herr Stiller einfach nur, bzw. ich glaube, in der Literatur wird es auch häufig so gemacht, einfach um es nochmal genau hinzuschreiben. Aber eigentlich ist es redundant. Wenn Sie, Sie können sich natürlich auch vorstellen, Eulers Rundtour auf
17:50
mehreren Zusammenhangskomponenten zu machen. Aber ich glaube, da haben wir das Argument, dadurch, dass das ja alles zyklisch ist, muss es immer noch die Kantenzahl asymptotisch mindestens so groß wie die Knotenzahl sein.
18:01
Im Allgemeinen, wenn der Graf zusammenhängt ist, muss die Kantenzahl natürlich nicht mindestens so groß asymptotisch wie die Knotenzahl sein. Betrachten Sie den Grafen ohne Kanten. Eine Million Knoten, gar keine Kanten. Da ist die Kantenzahl natürlich nicht asymptotisch so groß wie die Knotenzahl. Aber wenn wir keinen isolierten Knoten haben, dann haben wir ja alles in Zyklen,
18:20
dann muss das mindestens genauso groß sein. Da müsste es immer noch diese Laufzeit stimmen, wenn wir für jede einzelne Zusammenhangskomponente das machen. Ich glaube, ich habe jetzt mehr beantwortet, als Sie gefragt haben. Ob das positiv ist, weiß ich jetzt nicht. So, jetzt kommen wir endlich zu diesem
18:41
Bild. Das ist natürlich nicht mehr, fällt natürlich nicht mehr unter Urheberrecht, versteht sich. Dafür ist dieses Bild zu alt und wer immer das gezeichnet hat, hat sicherlich keine Erbengemeinschaft mehr, die hier Rechte angeben kann. So,
19:05
damit sind wir mit dieser Problematik durch und wir kommen jetzt zu einer neuen Sache, die für Sie nicht neu ist. Wir
19:20
werden ziemlich viel noch mal am Anfang dieses Kapitels, werden wir noch mal zu ungerichteten Grafen kommen und zu einer Problemstellung, die Sie aus der GDE 2 kennen, nämlich minimalspannende
19:43
Bäume. Wir werden sehen, Sie kennen daraus Prim und Kruskar, sollten Sie kennen. Wir werden jetzt hier ein Allgemein- und Schema kennenlernen, wo Prim und Kruskar, obwohl die so extrem unterschiedlich sind, einfach nur zwei Beispiele sind dieses Allgemein- und Schemas. Also es geht nicht darum, neue Problemstellungen,
20:01
ganz tolle neue Algorithmen kennenzulernen im ersten Teil dieses Kapitels, im zweiten Teil dann schon, wenn es um gerichtete Grafen geht, da wird das Ganze viel komplizierter und haariger, sondern es geht darum, einfach einen abstrakteren Blick aus der Adler Perspektive auf ein Thema, was Sie
20:21
schon aus der GDE 2 kennen, minimalspannende Bäume, Algorithmen von Prim und Kruskar beziehungsweise allgemeine Schema, dass man auch ganz anders als wie Prim und Kruskar konkretisieren kann. Ja, hallo?
20:47
Ja, hallo? Hallo? Super! Ah, er hat eine kleine Denkpause gebraucht, das ist alles.
21:02
Okay, so, Sie wissen, das haben sicherlich in der GDE 2, bei wem Sie es auch gehört haben, kurz thematisiert worden. Ich habe mir sagen lassen, dass in Vorlesungen wie Einführung in Netcentric Systems und darauf aufbauenden Vorlesungen, dass da MST
21:22
und kürzeste Wege, dass das dann auch wieder thematisiert wird. Weiß ich jetzt nicht, aber ich habe es von den Dezenten gehört, also wird das wohl stimmen. So, Sie kennen die Problemstellung, können wir ganz schnell durchgehen, weil Sie aus der GDE 2 ganz sicherlich
21:40
eine ganz frische Erinnerung haben, auch wenn Sie vielleicht schon vor drei Jahren das gehört haben. Sie haben einen ungerichteten, aber zusammenhängenden Grafen mit positiven Kantengewichten und was Sie suchen, ist eine Teilmenge der Kantenmenge, also wir identifizieren diesen minimal spannenden Baum mit seinen Kanten, wir drücken ihn durch seine
22:00
Kantenmenge aus. So, was ist die Zielsetzung? Was ist das Ganze? Dass der Graf mit der ursprünglichen Knotenmenge und dieser spezifischen Kantenmenge, also alles was nicht zu T gehört, haben wir aus E rausgeschmissen und dieser Graf ist immer noch zusammenhängt. Und unter diesen Umständen, also dass es ein spannender Baum ist, soll das Gesamtgewicht
22:24
dieses Baumes minimiert werden. So, und wenn es tatsächlich ein Baum ist, dann nennen wir es auch ein minimal spannender Baum, das ist dadurch gerechtfertigt, wir haben ja positive, strikt positive Kantenkosten. Sehen Sie hier oben, jede Kante
22:40
hat strikt positive Kosten. Das heißt, eine minimale Lösung kann keine Zügel enthalten, denn wenn es eine Zügel enthält, kann ich mir irgendeine Kante hernehmen, rausnehmen und habe dadurch das Gesamtgewicht vermindert, also kann das vorher keine minimale Lösung gewesen sein. Es muss zusammenhängt sein,
23:00
das ist die Forderung, es muss zykelfrei sein, sonst wäre es nicht optimal, also ist es ein Baum. So, natürlich die erste Idee, an die man denken könnte, dass man einfach mal alle spannenden Bäume berechnet und den nimmt, der minimales Gewicht hat. Letztendlich ist die Formel,
23:21
die hier steht irrelevant, weil Sie können sich vorstellen, es ist vollkommen wurscht, wie genau die Formel aussieht, es funktioniert nicht, es sind viel zu viele spannende Bäume, die es haben kann. Nur, falls es Sie interessiert, das ist der Satz von Cayley, dass in einem vollständigen Grafen,
23:40
wo alle möglichen Kanten tatsächlich enthalten sind, gibt es insgesamt so viele verschiedene spannende Bäume, beachten Sie, dass diese Funktion in N sogar noch schneller wächst als die Fakultät. Die Fakultät wächst schneller als jede Exponentialfunktion, also jede 2 hoch n oder eine Million hoch n
24:02
oder so etwas, und diese Funktion wächst sogar noch schneller als die Fakultät. Also keine guten Ausgangsbedingungen dafür, dass wir das einfach enumerieren und den optimalen Bau nehmen, das hat Hersteller hier nochmal zusammengefügt,
24:20
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 Universen weiter, bis die Lösung endlich vorliegt, also kein guter Ansatz.
24:43
Und beachten Sie auch, wenn die Laufzeit eines Algorithms mindestens exponentiell ist, dass es nicht viel bringt, dann mehr Rechenpower zu haben, weil selbst wenn Sie die Rechenpower um den Faktor 10 erhöhen, oder Faktor 100,
25:02
oder Faktor 1000, ist egal, der Exponent wächst nur additiv, wenn Sie zum Beispiel
25:24
in einem Menschen leben, oder in einer Nacht, oder was immer Sie sich als Zeitvorgabe hernehmen, wenn Sie die Größenordnung N, Sie haben einen Algorithmus, das ist eine Komplexität des 2 hoch N, und Sie können mit dem großen N, können Sie,
25:42
kommen Sie in einer Nacht durch mit Ihrem Algorithmus, ja? Und jetzt haben Sie tausendfache Beschleunigung Ihres Rechners. Wie ändert sich das Ganze? Das ändert sich dahingehend, dass Sie jetzt 2 hoch N plus
26:00
10 diese Größenordnung hinbekommen. Ja, das heißt also, dramatische, multiplicative Änderung der Rechenpower bringt nur eine additive Änderung der Problemgröße, die Sie mit dieser zusätzlichen Rechenpower in der selben Zeit bewältigen können.
26:20
Das heißt also, bei so einem, bei so einem Problem, bei einem Algorithmus, dessen Laufzeit exponentiell oder sogar noch schlimmer ist, brauchen Sie nicht zu warten, dass die Rechner schneller werden, viel bringt das nicht. So, passiert jetzt was? Ja. So.
26:44
Minimalspannender Baum, maximalspannender Wald. Wenn Sie bei mir GD2 gehört haben, letztes Semester, haben Sie gesehen, ich habe es genauso beides zusammen eingeführt. Ich denke,
27:01
in früheren Semestern vielleicht auch, weiß ich jetzt nicht. Zunächst einmal, was wir zeigen wollen, ist, dass diese beiden Problemstellungen finde einen minimalen spannenden Baum mit positiven Kantenkosten in einem zusammenhängenden Grafen
27:20
und finde einen maximalspannenden Wald in einem ungerichteten Grafen, der nicht zusammenhängend sein muss, dass die beiden Problemstellungen Äquivalent sind im Sinne dieser Definition. Ich will kurz,
27:44
ich will das kurz anhand einer Zeichnung darstellen, was man sich darunter vorzustellen hat, so eine lineare Transformation, dass man ein Problem überführen kann in das andere Problem
28:01
durch so eine lineare Transformation. Wir haben zwei Probleme, Problemstellungen P und Q. Wir sind hier oben, betrachten wir das P und unten das Q. Wie sieht es jetzt
28:21
aus? Schon wieder reingefallen. Andere Seite. Oder Sie sehen es, ist gut. Sie haben jetzt hier ein Beispiel Input, oder sagen wir, ein Input, irgendein
28:42
i aus dem Problemstellung P. Und das transformieren Sie, das ist jetzt hier auf der Folie die Funktion f. Ach so,
29:02
hier ist es x genannt, dann nenne ich es auch x. Hier. Das ist die Funktion f, die transformiert das. Also, wenn wir von Funktion reden, dann meinen wir natürlich, wir implementieren das. Das heißt, ein Algorithmus, der einen Input aus P hernimmt und daraus einen Input
29:21
aus Q macht. Input f von x aus Q. So. Jetzt haben Sie einen Lösungsalgorithmus
29:40
für Q. Und jetzt haben Sie noch eine weitere Transformation. Also dieser Lösungsalgorithmus liefert Ihnen natürlich eine Lösung
30:04
z für f von x. Immer noch alles drauf? Wie oben rechts in die Ecke? Also wenn ich hier eine Ecke schreibe und es ist nicht drauf, dann müsste es doch hier auch nicht drauf sein.
30:21
Ach so. Also ich muss ein bisschen runter. So. So ziemlich alles. Aha. Wie hier oben rechts? Da ist doch gar nichts. Ah, okay. Also das, was fehlt, ist gar nicht da. Es würde fehlen, wenn es da wäre.
30:42
Okay. Nicht weiter drüber nachdenken. So, jetzt kommen wir aber in die gefährliche Ecke langsam hin. Hier ist diese Funktion g, die eine Lösung z wieder zurück verwandelt in eine Lösung g von z
31:02
für na, bleiben wir mal lieber auf der Seite, für Q. Und das hier konstituiert im Prinzip einen Algorithmus für das Ursprungsproblem P. Also das ist
31:21
genauer gesagt keine Lösung für Q, sondern für dieses Beispiel X sogar. Ich schreib's doch mal auf die andere Seite. Das ist, auch wenn wir da langsam in den gefährlichen Bereich kommen. So. Hier. Und
31:41
über diesen Umweg haben wir damit praktischen Algorithmus für unser Ausgangsproblem P gebaut. das ist das Bild, was ich ganz hilfreich auch für mich finde, um sich sowas vorzustellen, wovon wir hier gerade reden. So. Und warum es geht, ist jetzt zu zeigen,
32:01
wenn wir einen Löser haben, wenn wir einen Algorithmus haben, mit irgendeiner Laufzeit, mit irgendeiner asymptotischen Komplexität, für MaxForest, dann können wir über so eine Transformation auch Minimum Spanning Tree damit lösen und umgekehrt, wenn wir einen Algorithmus für Minimum Spanning Tree haben, können wir einen Algorithmus, können wir
32:23
damit auch MaxForest lösen. Und zwar mit derselben Laufzeit, beides, weil die beiden Transformationen sind linear und damit spielen die natürlich für die asymptotische Komplexität keine Rolle. Weil besser als linear kommt man sowieso nie hin.
32:42
Allein das Einlesen der Daten wäre ja schon Linearlaufzeit. So. Also F transformiert, das ist das, was wir links sehen, G transformiert zurück auf der F auf der Seite der Instanzen, der Beispiel Input, G auf der Seite der Lösungen
33:03
und genau. Das habe ich jetzt noch vergessen dazu zu sagen. Wenn das eine optimale Lösung ist, die der hier produziert hat, der Algorithmus, dann soll das auch eine optimale Lösung sein. Also letztendlich läuft das darauf hinaus, dass die, dass diese,
33:21
dass diese Funktion monoton, Strecken monoton ist, diese Funktion G. Das heißt, je größeren Wert diese Lösung hier hat, umso größeren Wert hat diese Lösung hier auch. Und damit ist natürlich klar, Optimum wird transformiert in Optimum. Achso, ich muss umgekehrt sagen,
33:40
weil wir ja ein Maximum und ein Minimums Problem haben. Ja, je größer die Lösung hier ist, umso kleiner wird der Lösungswert hier, umso größer wird der Lösungswert hier. Und umgekehrt, je größer hier, umso kleiner hier. War das jetzt soweit klar, oder habe ich das? Wem ist das noch nicht so richtig klar? Ich sehe keinen
34:04
Finger. Ich gehe davon aus. Achso, das ist ihm klar. Ist gut. Können wir ein bisschen schneller vorwärts gehen, nicht? So, die Behauptung ist also jetzt, wie ich eben gesagt habe, dass die nach diesem Schema Äquivalenz sind. Und da haben wir natürlich wie immer zwei Richtungen.
34:23
Die erste Richtung ist, wir haben einen Algorithmus gegeben für Max Forest und wollen MinSpanningTree mit diesem Algorithmus lösen. Das heißt also, wir brauchen solche Transformationen. Inputs von MinSpanningTree werden in Inputs von Max
34:40
Forest umgewandelt. Und Outputs von Lösungen von Max Forest werden in Lösungen von MinSpanningTree umgewandelt. Und das ist ganz einfach, das haben Sie mit großer Wahrscheinlichkeit in der GDI 2 schon mal gesehen, also bei mir ganz sicherlich, dass wir im Grunde negieren wir
35:02
die Kosten alle, denn wir nehmen das negativ, aber weil wir am Ende mit positiven Gewichten rauskommen wollen, müssen wir noch, addieren wir noch einen Wert drauf, der dafür sorgt, dass alle diese negativen Gewichte garantiert wieder in den echt positiven Bereich rauskommen.
35:22
Was nehmen wir da für einen Wert? Wir nehmen den Maximalwert aller Kantengewichte und setzen noch eins drauf. Das heißt, egal welcher Wert hier steht, diese Differenz M-ce ist garantiert positiv. Für die größte Zahl ce hier, für die größte
35:40
Kantengewicht, kommt hier gerade ein plus eins raus. Nämlich dieses plus eins, was wir hier drauf addiert haben. So, hier ist ein wichtiger Punkt zu bemerken, der, glaube ich, auf den Folien auch nicht so genau klar rauskommt. So eine Transformation
36:01
funktioniert nur deshalb, machen wir vielleicht noch einen Schritt weiter, erstmal. So, wir setzen die so um, wir definieren neue Gewichte, das ist diese Transformation F, wir lösen jetzt das Max-Forest-Problem da drauf, der Graf ist zusammenhängt, das heißt,
36:21
Max-Forest liefert tatsächlich einen Baum, nicht einen allgemeinen Wald, weil die Kantengewichte größer null sind und weil wir ein Maximierungsproblem haben auf positiven Kantengewichten, ist das Ergebnis nicht ein beliebiger Wald, sondern ein Wald mit maximal viele Kanten drin,
36:43
nämlich ein Baum. Und hier kommt jetzt ein wichtiger Punkt dabei hinein, wo Sie sich klar machen müssen, das funktioniert bei mir in Spanning Tree, aber das funktioniert beispielsweise bei Kürzesten Wegen nicht. Der wichtige Punkt an der Sache ist der, alle spannenden Bäume haben dieselbe
37:02
Kantenzahl. Das heißt, wenn wir jetzt eine Lösung, wenn wir jetzt, das bedeutet, das Gewicht hier,
37:21
das maximale Gewicht, da haben wir N-1 mal M draufgesetzt. Egal welcher Baum das ist, es ist immer N-1 mal M, was die Gesamtänderung der Gewichte angeht. Anzahl der Knoten minus 1 in Klammern mal M.
37:49
Minussumme der CE. Das ist die Gesamtgewicht jedes Baumes, also der Kanten, die hier in dem Baum drin sind.
38:01
Das bedeutet, die einzelnen Bäume, deren Kosten haben sich alle gleich viel geändert. Das ist beispielsweise bei Kürzesten Wegen nicht der Fall, weil wenn Sie sich zwei Wege anschauen, von einem Knoten zu einem anderen Knoten,
38:31
die müssen ja gar nicht im Allgemeinen die selbe Länge haben. Einer hat 387.000 Kanten,
38:41
die habe ich jetzt nicht alle eingezeichnet. Der zweite hat eine andere Anzahl der Kanten. Wenn Sie jetzt eine Transformation machen, so wie eben, man könnte denken, das ist doch wunderbar. Bei Dijkstra haben wir das Problem, nur positive Kantengewichte, wenn wir auch negative Kantengewichte haben, heben wir sie alle einfach, genau so wie hier,
39:00
um so ein großes M hoch. Problem an der Sache ist, dass dieser hier um 3x M hochgehoben worden ist, und der Weg hier, 1, 2, 3, 4, 5, 6, um 6x M hochgehoben worden ist. Das heißt, hier haben wir die Kantenlängen verfälscht.
39:22
Weil verschiedene Kanten eben, verschiedene Pfade eben verschiedene Kanten zahlen. Während beim Mint Spanning Tree kann das nicht passieren, alle Lösungen haben dieselbe Kantenzahl.
39:41
So, und das steckt noch hinter diesem letzten Spiegelstrich. So, jetzt drehen wir es um. Jetzt gehen wir davon aus, wir haben einen Algorithmus für Mint Spanning Tree und wollen umgekehrt sehen, ob wir nicht eine solche
40:01
Konstruktion finden, so eine lineare Transformation, dass wir damit auch den Max Forest lösen können. So, wir machen dasselbe wieder, allerdings einen Schritt
40:21
weiter. Wir vervollständigen den Graphen. Also es wird jetzt nicht linear die Transformation. Das hatte ich jetzt immer falsch gesagt. Also wir werden etwas an der Laufzeit bekommen. Wir vervollständigen den Graphen
40:41
zu einem vollständigen Graphen. Und setzen M richtig groß. Also was hier letztendlich steht, auch wenn hier eine komplizierte Formel steht, das was Sie aus kürzesten Wege her, aus der GDE 2 her kennen, da steht unendlich. Eine etwas komplizierte Form unendlich auszudrücken.
41:03
Aber da steht einfach M ist eine ausreichend große Zahl, dass uns Kanten mit der Kantengewicht M nicht stören.
41:22
Hier muss M minus, das ist glaube ich ein Fehler, hier muss M minus C stehen, so wie eben auch wieder. Wir brauchen ja positive Kantengewichte am Ende. Gut, also so groß M minus zu E und ansonsten M. Kann auch ein beliebiger Wert
41:41
größer als M sein, der hier steht. Also bei den Kanten, die gar nicht existieren, die wir zur Vervollstellung eingefügt haben, setzen wir einen ausreichend großen Wert drauf. So, wir berechnen die Kantengewichte. Wenn wir jetzt nur die
42:01
Kanten betrachten, die ursprünglich schon drin waren und die jetzt in diesem minimal spannenden Baum drin sind, warum machen wir das Ganze mit der Vervollstellung? Wir machen das Ganze einfach deshalb, weil der Graf ja zunächst einmal nicht zusammenhängt
42:22
sein muss bei Max Forest. Da gibt es gar überhaupt keinen Grund, dass der Graf zusammenhängt sein muss. Weil wir eh nur den Anspruch haben, einen maximalen Wald zu finden und nicht einen maximalen
42:41
Baum. Also können wir gleich auch erlauben, dass der Graf nicht zusammenhängt ist. So, das sind die Zusammenhangskomponenten wieder mal. Sie sind das ja von mir gewöhnt, dass ich da so Knubbel zeichne. So, und was wir machen ist, diesen Grafen zu vervollständigen.
43:01
Da gibt es schon ein paar Kanten hier zwischendurch, die wir zusätzlich addieren, aber weil die so hohes Gewicht haben, werden die dann keine Rolle spielen. Aber, was wichtig ist, ist, dass jetzt natürlich die Riesenanzahl von Kanten hier rein kommt. Und Sie sehen schon, wie man das dann tatsächlich
43:20
linear kriegen kann, indem man es nicht zu einem Kn vervollständigt. Das muss gar nicht sein. Sondern indem man es einfach zu einem zusammenhängenden Grafen vervollständigt. Ja, dann bleibt die Kantenzahl linear, die am Ende rauskommt. So, na, da fehlt einer.
43:40
So, zusammenhängt irgendwie irgendwelche Kanten von hier irgendwo nach hier irgendwo und so weiter. jetzt, wenn der Graf zusammenhängt
44:00
ist, können Sie MST anwenden. Sie kriegen hier jeweils, was kriegen Sie vom Raum raus, plus Kanten hier raus. Warum? Weil es
44:20
diese Kanten haben größeres Gewicht als die ursprünglichen Kanten hier drin. Das heißt also, diese Kanten werden höchst ungern genommen. Die werden nur genommen, wenn es unbedingt sein muss. Oder sogar so machen, sogar noch weiter reduzieren, dass die insgesamt nur
44:41
dass diese Kanten keinen Zykkel bilden. So, die Kanten werden genommen im minimal spannenden Baum, weil es gar keine Alternative gibt. Und innerhalb von jedem Einzelnen hier haben wir einen minimal spannenden Baum. Das ist das Ergebnis von MST.
45:01
Und wenn hier jeweils ein minimal spannender Baum nach dem Modifizierten Kantengewichten drin ist, dann heißt das, hier ist jeweils ein maximal spannender Baum nach den ursprünglichen Kantengewichten drin, weil es ja genau umgedreht worden ist. Und wenn wir die Kanten
45:21
jetzt wieder rausnehmen, hier, aus der Lösung, dann bleibt übrig ein maximaler Wald auf dem ursprünglichen Grafen. Das ist die Transformation hin und zurück. Also, wenn Sie tatsächlich linearer Laufzeit haben wollen, linearer Transformation, dann dürfen Sie es nicht so machen, wie es jetzt gerade hier auf der Folie steht, dass Sie das
45:40
vollständigen zu einem vollständigen Grafen, damit haben Sie ja sofort eine Explosion der Kantenzahl drin, unnötigerweise, sondern es reicht, dass Sie es so weit vervollständigen, gerade so, dass der Graf zusammenhängt wird. Wie man die Zusammenhangskomponenten finden kann in linearer Zeit, haben wir letztens mal betrachtet.
46:01
Wir könnten es auch von vornherein einfach in dieser Richtung einfacher machen, dass wir jede Komponente für sich betrachten. Aber so oder so, diese beiden Problemstellungen, die zunächst mal ähnlich, aber doch nicht spiegelsymmetrisch aussehen, sind trotzdem identisch. So, jetzt kommen wir zu den Algorithmen.
46:22
Wir kommen hier auch zu Prim und Kruskal, sagen das aber noch nicht, sondern wir kommen zu einem allgemeinen Schema, wo wir dann feststellen, Prim und Kruskal sind nur zwei spezielle Fälle von diesem allgemeinen Schema. Kanten werden gefärbt.
46:40
Zu meiner Zeit, als ich das mal in der Vorlesung gehört habe, waren das noch Rot und Grün. Inzwischen sind es Rot und Blau, weil sich doch die Erkenntnis herumgesprochen hat, dass Rot-Grün-Blindheit eine sehr typische, sehr häufig vollkommende Seestörung ist, deshalb überall da, wo sie es
47:00
hingesprochen hat, vermeidet man Rot und Grün, obwohl es eigentlich schade ist, weil es ja genau die meistbeabsichtigte Signalwirkung hat, so auch hier. Grün eigentlich heißt gut, prima, klasse, Rot heißt nein.
47:22
So, das allgemeine Schema beginnt mit einem Grafen, wo keine einzige Kante gefärbt ist und hört mit einem Grafen auf, wo jede Kante gefärbt ist, entweder Rot oder Blau, nicht beides, aber eins
47:41
von beidem. Und dieses Schema, der Algorithmus, den wir gleich sehen, dieser allgemeine Algorithmus, hat diese Invariante, also diejenigen von Ihnen, die bei mir gehört haben, sind von vorne bis hinten, glaube ich, bedient mit Invarianten.
48:01
Nichtsdestotrotz kommen sie wieder. Die Invariante ist folgende. Es gibt eine Minimalspannende Baum. Beachten Sie, denken Sie daran, der Minimalspannende Baum muss nicht eindeutig sein. Es kann durchaus mehrere
48:21
Minimalspannende Bäume in einem ungerichteten Grafen mit Kantengewichten geben. So, aber unter denen gibt es einen, der alle Kanten enthält und keine Rote. Der Algorithmus wird in jeder Iteration eine weitere Kante Rot oder Blau färben und er wird diese Invariante
48:41
dabei beibehalten. Nach jeder Iteration gilt das wieder. Wenn er eine Kante Blau gefärbt hat, dann gilt wieder, auch mit dieser zusätzlich Blau gefärbten Kante, dass es einen Minimalspannenden Baum gibt, der alle Blau gefärbten Kanten und keine Roten enthält. Und wenn er eine Kante Rot gefärbt hat, zusätzlich zu den schon
49:01
bis dahin gefärbten Kanten, wird das auch wieder gelten. Es gibt einen Minimalspannenden Baum, der alle Blauen und keine Rote Kanten enthält. wie sieht das aus? Das möchte ich, ich gehe mal davon aus, dass Sie noch eine dunkle Vorstellung
49:20
von Prim und Kruskal haben. Ach so, sagen Sie doch was oder können Sie das gut lesen auf der Tafel? Es geht so. Okay, jetzt brauchen Sie jetzt können Sie es mal kurz lesen ohne Tafel, aber ich brauche gleich die Tafel wieder.
49:58
So, Sie erinnern sich an den Algorithmus von Prim.
50:03
Welcher von den beiden war das jetzt noch? Wenn das Ihr Graf ist, dann war Prim der Algorithmus, Sie haben einen Startknoten und fangen an, von dem aus so langsam, schrittweise, immer einen Knoten hinzuzunehmen,
50:21
um den Baum aufzubauen. So, jetzt ist hier blaue Regel von einem Cut, von einem Schnitt die Rede, der keine blauen Kanten enthält und von allen Kanten da drin soll der kleinste genommen werden und der wird dann auch blau gelabelt. So, diese Kanten,
50:42
die wir schon hinzugenommen haben, die sind alle blau. Kann ich jetzt leider nicht zeichnen, weil wir hier keine farbige Kreide haben, oder haben wir doch farbige Kreide? Ja, rote haben wir. Das hilft jetzt nicht viel, das wäre verwirrend,
51:02
wenn ich jetzt der Farbe rot die Semantik blau geben würde. So, von welchem Cut ist hier die Rede? Naja, von diesen Knoten, die wir bisher hier haben, gibt es natürlich Kanten, die aus dem Baum rausgehen, solange wir noch nicht fertig sind. Am Ende, wenn wir fertig sind, gibt es die Kanten natürlich nicht mehr.
51:22
Ja, und dieser Schnitt, der durch diese Kanten durchschneidet. Von diesem Cut ist hier jetzt ganz konkret bei Prem die Rede. Was die blaue Regel sagt, ist, wir nehmen einen Schnitt, der keine blauen Kanten enthält, das ist bei dem hier der Fall,
51:42
weil alle blauen Kanten auf der einen Seite von diesem Schnitt sind, hier, so wie ich es gezeichnet habe, auf der inneren Seite, aber bei einem beliebigen Grafen, gibt es natürlich keinen innen und keinen außen. Und von denen nehmen wir die kleinste Kante, die Kante mit dem kleinsten Gewicht, und geben ihr auch blau. Und das ist genau das,
52:02
was Prem macht. Nehmen wir mal an, das hier ist die Kante mit kleinstem Gewicht, von den allen, dann wird die genommen, und wir sind jetzt einen Schritt weiter damit gegangen. Das ist der Algorithmus von Prem. Sehr in der Sicht dunkel. Prem ist der, der so ähnlich aussieht wie Dykstra.
52:21
Der Algorithmus von Kruskal, der sieht etwas anders aus.
53:00
So ein Schnappschuss mitten drin
53:03
sieht eher so aus. Sie haben einzelne Zusammenhangskomponenten, so vielleicht so, wo sie jeweils schon teilweise
53:23
so, wo sie jetzt jeweils schon innerhalb der Zusammenhangskomponenten einen Gemmbaum gebaut haben, und zusätzlich haben sie in der Regel auch noch einzelne Knoten als weitere Zusammenhangskomponenten, triviale Zusammenhangskomponenten. Das ist ein Schnappschuss vom Algorithmus von Kruskal.
53:41
Und sie gehen die Kanten bei Kruskal in einer gewissen Reihenfolge durch, nämlich von der mit kleinstem Gewicht bis zu der mit größtem Gewicht. Nehmen wir mal an, wir haben jetzt eine, was könnte jetzt die nächste Kante sein? Also nehmen wir beispielsweise mal an Fall 1.
54:01
Das wäre die nächste Kante mit kleinstem Gewicht, die noch nicht betrachtet worden ist. Diese Kante verbindet zwei unterschiedliche Zusammenhangskomponenten. Deshalb wird sie reingenommen, dann wird sie blau, zusätzlich zu den anderen blauen Kanten, die wir schon haben.
54:21
Oder, andere Situation ist, dass sie zwei Knoten verbindet, die zur selben Zusammenhangskomponente gehören, dann wird diese Kante nicht in den Baum aufgenommen. Und wir sagen hier in diesem Schema, dass sie dann rot gelabelt wird.
54:43
Das ist die zweite Variante, das war die blaue Regel. Jetzt kommt die rote Regel. Blaue Regel bei Schnitten, rote Regel bei Zyklen. Wo war das jetzt? Da, hier bei
55:04
Zyklen. Wenn in einem Zykel, sagt die rote Regel, kann ich immer die schwerste Kante rot färben, und die Variante ist erhalten. Also, ich brauche mich nicht darum zu kümmern, dass diese Kante,
55:21
also ich brauche mich nicht darum zu gräben, dass ich diese Kante weggeschmissen habe, nicht den Baum eingefügt habe. Ich brauche sie nicht. Es gibt einen spannenden Baum, der diese Kante nicht enthält, und auch alle anderen rot gefärbten Kanten nicht enthält. So, warum ist das jetzt die schwerste Kante, die hier rot gefärbt ist? Naja, alle anderen Kanten hier, sind vorher berücksichtigt worden.
55:41
Also, wir gehen die ja in aufsteigender Sortierung durch, also sind alle anderen Kanten auf diesem Zykel leichter, oder höchstens gleich schwer. Also ist das die schwerste Kante. Die letzte, die wir finden, die einen Zykel schließt, ist immer die schwerste Kante dieses Zykels. Die können wir dann rausschmeißen, nach dieser
56:01
roten Regel. Wenn wir einen Zykel haben, der bis jetzt noch keine rote Kante hatte, alle anderen Kanten waren blau, nehmen wir die längste Kante, nämlich die letzte betrachtete bei Kruskal, und färben sie rot.
56:20
So, wie ist der Algorithmus? Der ist in allgemeiner Betrachtung ganz einfach. Wir beginnen damit, dass alle Kanten kein Label haben, und solange es eine Kante gibt, die nicht gelabelt ist, ganz allgemein wählen wir aus, welche Kante wir nehmen, also ob
56:40
wir die blaue und die rote Kante, die blaue oder die rote Regel anwenden, und wir wählen bei der blauen Regel beliebig aus, welchen Schnitt wir hernehmen. Wenn wir immer diesen besagten Schnitt hernehmen, sind wir bei prim. Wenn wir einen beliebigen Schnitt hernehmen, sind wir bei irgendwo. Oder wir haben die Wahl, entweder die blaue oder die rote Regel, und beliebiger
57:01
Zykel hier, beliebiger Schnitt hier. Und am Ende, until all edges are labeled, bis alle einen blau oder einen rot erhalten haben, am Ende, der Output, den Sie rausgeben, sind die blauen Kanten. Wir haben schon gesehen, Kruskal und
57:20
prim sind nichts anderes als zwei Spezialfälle dieses allgemeinen Schemas, was Sie da unter den Punkten eins bis drei hier lesen können. Die Behauptung ist, das ist jetzt eine stärkere Behauptung als nur die Behauptung, dass prim oder Kruskal korrekt ist, die Behauptung ist, dass dieser
57:41
Algorithmus, egal wie wir hier vorgehen, egal wie es uns gefällt, wann wir die blaue, wann wir die rote Regel anwenden, sofern es noch Kanten gibt, wo wir sie anwenden können, das Endergebnis ist immer, egal wie wir es machen, ein minimal spannender Baum. Das bedeutet insbesondere als Korrelar, da ja prim
58:01
und Kruskal nichts anderes als Spezialisierung dieses Algorithmus ist, ist damit auch bewiesen, dass prim und Kruskal korrekt ist. Und tatsächlich, wenn Sie zum Beispiel, weil ich habe die Beweise der Korrektheit bei prim und Kruskal in meiner Vorlesung GD2 gemacht, wenn Sie sich das, sind Sie interessiert, wenn Sie sich das nochmal anschauen wollen, dann sehen Sie, dass diese Beweise verdammt
58:21
ähnlich sind zu dem, was jetzt hier kommt. So, wir zeigen, dass die Invariante gilt. Also, was muss man beweisen, um zu beweisen, dass ein Algorithmus korrekt ist und einen minimal spannenden Baum konstruiert?
58:42
Man muss beweisen, erstens, der Algorithmus tut nichts dämliches, teilt nicht durch null, greift nicht auf ein falsches R-Element, tut das gar nicht existiert und so weiter. Das denke ich ist einsichtig, dass man dieses Schema so implementieren kann und die ganzen Subprozeduren so implementieren kann,
59:00
dass das nicht der Fall sein wird. Zweitens muss der Algorithmus terminieren. Er muss tatsächlich zu einem Ende kommen. Das ist offensichtlich auch der Fall, weil wir in jeder Iteration ja eine Kante labeln und irgendwann sind alle Kanten gelabelt und wir sind fertig. Drittens, und das ist natürlich meistens das Komplizierte an der Sache, dass das, was
59:20
am Ende herauskommt, bei Termination tatsächlich das ist, was wir wollen, in diesem Fall ein Minimum spannender Baum. Und der Königsweg, um zu beweisen, dass das, was herauskommt, ein minimal spannender Baum ist, ist, wenn man es wirklich sauber machen will, wir gehen zurück zur Invariante,
59:41
diese Invariante mit vollständiger Induktion zu beweisen. Induktion über die Anzahl der schon durchlaufenden Iteration, sprich über die Anzahl der schon beibelten, gefärbten Kanten. wenn diese, denn schauen Sie, wenn
01:00:00
Schauen Sie sich diese Invariante an. Wenn der Algorithmus fertig ist, wenn sämtliche Kanten gelabelt sind, und wir haben es geschafft, bis zu diesem Zeitpunkt, inklusiver, diese Invariante durchzuhalten, dann sagt diese Invariante, die blauen Kanten sind ein minimaler
01:00:23
spannenden Baum und die roten Kanten sind die anderen, die nicht in diesem minimal spannenden Baum drin sind. Das haben Sie bei mir in der GD2 immer wieder gesehen. Wer von Ihnen war denn bei mir in der GD2? Eine. Okay. Gut, die anderen müssen sich also an
01:00:41
dieser Schema gewöhnen, weil es, glaube ich, in früheren Jahren sowieso nicht so viel mit Beweisen da passiert ist. Die Aussage dieser Invariante geht zum Zeitpunkt der Termination, wenn alle Kanten gelabelt sind, in die Aussage über, die blauen Kanten
01:01:01
sind der minimal spannenden Baum, die roten Kanten sind der Rest. Wir müssen also nur in Anführungszeichen zeigen, dass diese Invariante durchgeschleppt wird, immer erhalten bleibt, durch den Algorithmus und durch, von Iteration zu Iteration. So, falsche Invariante beginnt mit der Induktionsverankerung, Ausgangssituation, keine Kante ist gelabelt. Damit wird auch die Aussage der Invariante trivial, wenn
01:01:28
es keine blauen und keine roten Kanten gibt, dann wird, ja, jeder MSD enthält die leere Menge als Teilmenge. Diese Aussage ist trivialerweise erfüllt am
01:01:42
Anfang, wenn wir keine Kanten gelabelt haben. So, was wir also zeigen müssen ist den Induktionsschritt, das kennen Sie aus der Mathematik, dass meistens nicht immer der Induktionsanfang das einfache ist und der Induktionsschritt, das etwas kompliziertere, wir müssen zeigen, wenn wir in Schritt zwei hier in einer Iteration
01:02:04
die blaue oder die rote Regel korrekt angewandt haben, dass dann die Invariante nach dieser Iteration immer noch erfüllt ist, wenn, Induktionsvoraussetzung, wenn sie vorher erfüllt war. Soweit klar? Also Sie sind wahrscheinlich eher
01:02:25
Induktionsbeweise 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 vollständigen Induktionen die Korrektheit eines Algorithmus beweisen, also erstmal die Korrektheit einer Invariante, woraus dann die Korrektheit des Ergebnisses folgt. So,
01:02:47
es ist entweder die blaue Regel oder die rote Regel, wenn es die blaue Regel ist, haben wir hier nicht ein Bild, genau. So, wir haben die blaue Regel angewandt, das heißt wir haben einen Schnitt im Grafen identifiziert, der
01:03:03
ist hier so angedeutet durch diese gepunkteten Linien, da mögen natürlich noch viel mehr Kanten drin sein als nur diese beiden, wir haben eine Kante herausgenommen, gewählt, wir haben einen Schnitt gewählt, genau gesagt, und wir haben die Kante mit kleinsten Gewicht in diesem Schnitt hergenommen, einen Schnitt, der keine blauen Kanten bisher
01:03:26
enthält, das war die blaue Regel, wir müssen einen Schnitt wählen, der noch keine blauen Kanten enthält, wir nehmen in diesem Schnitt die kürzeste Kante und die fügen wir hinzu, machen sie zu einer blauen Kante. So, wie ist jetzt die Argumentation, dass das korrekt ist?
01:03:41
Jetzt machen wir eine Pfeilunterscheidung, T ist dieser für uns, jetzt wird es abstrakt, wir wissen nach Invariante, nach Inuktionsvoraussetzung, es gibt einen Minimalspannendem Baum T, der bisher alle bisherigen blauen Kanten enthält und alle bisherigen grünen Kanten nicht enthält, das ist
01:04:01
die Inuktionsvoraussetzung, dass die Invariante vor diesem Schritt gilt, wir wollen zeigen, dass sie auch nach diesem Schritt gilt, dass es einen Minimalspannend Baum gibt. So, das ist dieser T, Baum T, wenn diese Kante, die wir
01:04:21
ausgewählt haben, in T drin ist, ist gar nicht zu zeigen, wir haben eine neue blaue Kante eingefügt, die auch in diesem ominösen Baum T ist, den wir gar nicht kennen, wir wissen nicht, wie dieser Baum aussieht, wir wissen, er existiert, fügen diese Kante ein und wenn die tatsächlich in diesem Baum
01:04:47
drin ist, den wir uns vorstellen gedanklich, von dem wir nur wissen, dass er existiert, dann ist alles paletti, dann ist die Invariante trivialerweise fortgesetzt worden, alle blauen Kanten inklusive der neuen sind in diesem ominösen Baum T. Jetzt, andere Situation, wir fügen
01:05:05
diese Kante ein, aber in diesem ominösen Baum, den wir gar nicht kennen, von dem wir nur wissen, dass er minimalspannend ist und dass er existiert, in dem Baum ist er nicht drin. So, was machen wir denn da?
01:05:26
Ups, erst mal drücken wir auf den Knopf und dann kommt da mehr. Dann, wenn E nicht drin ist, dieser Minimalspannende Baum T ist
01:05:44
besonders ein Baum, das heißt, es gibt irgendwo einen Weg zwischen diesen beiden Endknoten in diesem Baum, weil es zwischen je zwei Knoten des Grafen jeweils einen Weg in diesem Baum gibt. Ja, irgendwo hier hinten rum, gibt es einen Weg, der die beiden Endknoten von unserer ausgewählten Kante E verbindet und natürlich muss dieser Weg auch
01:06:01
irgendwo mindestens einmal, er könnte mehrfach so hin und her zick und zack gehen, aber mindestens einmal muss er diesen Schnitt überwinden, in einer Kante E Strich wie der hier. So, wir haben aber die Kante E besonders ausgewählt, nämlich die in diesem Schritt minimale.
01:06:25
Das bedeutet, dass diese Kante E Strich, die ja auch über diesen Schnitt rübergeht, nicht leichter, kürzer sein kann, als die von uns ausgewählte Kante E. Das bedeutet, wir können in,
01:06:45
dieses E Strich gehört zu diesem ominösen Baum, E nicht, aber wir können E Strich rausschmeißen aus dem Baum, falsch, E Strich rausschmeißen aus diesem Baum und dafür E einfügen. Damit können wir keine Verschlechterung haben, weil ja E
01:07:03
leichter ist als E Strich oder gleich leicht. Wir kriegen wieder einen neuen Baum raus, der E enthält, aber nicht mehr E Strich und damit sind wir wieder auf der Situation, die wir vorher waren. Wir haben einen neuen Baum, der nicht schlechteres
01:07:25
Gewicht haben kann als dieser ominöse, von dem wir wissen, dass er alle blauen Kanten enthielt, die wir bis dahin gewählt haben. Wir haben einen neuen Baum konstruiert, der diese hinzugenommene Kante E mit enthält zusätzlich zu diesen blauen Kanten
01:07:46
und damit haben wir wieder kein Problem mehr. Wir haben wieder einen Baum gefunden, wir wissen nicht, wie er aussieht, aber wir haben ihn trotzdem gefunden, der alle blauen Kanten und keine rote Hände enthält. Das ist vielleicht ein bisschen starve Kartobag jetzt für den ein oder anderen von Ihnen.
01:08:03
Vielleicht verstehen es auch Leute sofort, muss jetzt nicht unbedingt sein, dass sie es sofort verstehen. Nein, die ist nicht blau, weil sie darf auch gar nicht blau sein, weil der Schnitt, den wir gewählt haben, zum Protokoll für
01:08:21
die Aufzeichnung, die Frage war, ob die Kante E Strich nicht schon blau sein müsste. Nein, der Schnitt enthält ja nach Voraussetzung keine blauen Kanten. Wir haben einen Schnitt gewählt, der noch keine blauen Kanten enthält. E Strich ist nicht in den blauen Kanten enthalten. E Strich ist in diesem ominösen Baum enthalten, der wiederum alle
01:08:40
blauen Kanten plus noch ein paar weitere enthält. Wir wählen die kleinste Kante, das ist E. E Strich ist nicht kleiner. Sie ist im Schnitt, sie ist nicht kleiner. Sie ist größer oder gleich. Sie kann nicht größer sein, das ist
01:09:03
hier noch auf der Folie gesagt, weil nach Annahme ist dieser Baum minimal. Ja, wenn E Strich schwerer wäre als E, hätten wir durch Wegnahme von E Strich und hinzufügung von E einen einen kleineren, einen leichteren Baum gefunden.
01:09:22
Widerspruch zur Annahme, dass dieser Baum minimal war. Es kann nur so sein, dass E Strich und E tatsächlich gleiches Gewicht haben, sodass wir also von einem minimal spannenden Baum zu einem anderen minimal spannenden Baum gekommen sind. Ist ein bisschen abstrakt jetzt vielleicht, aber versuchen Sie es noch mal nachzuvollziehen
01:09:41
im stillen Kämmerlein, vielleicht auch die Aufnahme denn, sofern sie mal dann irgendwann mal fertig ist und und abrufbereit ist, diese Aufnahme mit hineinzunehmen und dann denke ich wird ganz schnell der Gräuschen auch fallen und wenn der Gräuschen bei Ihnen nicht fällt,
01:10:01
dann können wir gerne noch mal vielleicht darüber reden und versuchen den Gräuschen fennigweise fallen zu lassen. So, rote Regel ist jetzt ähnliche Situation. Nur umgerät anstelle von Schnitten betrachten wir Zykel. So, wir
01:10:20
haben jetzt die Situation, wir haben uns ein Zykel ausgewählt. Irgendwie, ja, bei Kruskal haben wir gesehen, wie wir da auf diese Züge gekommen sind, aber allgemein sagt ja die rote Regel, wir suchen uns irgendeinen Zykel her, der noch keine rote Kante enthält,
01:10:41
nehmen von dieser Kante, nehmen von diesem Zykel die schwerste Kante und färben die Rot. Also dieser Zykel darf blaue Kanten enthalten, aber er darf keine roten Kanten bisher enthalten. So, auch hier wieder dasselbe Strickmuster der Argumentation. Wir haben einen Baum, den wir Gros T nennen, von dem wissen wir nach Induktionsvoraussetzung,
01:11:01
wir können ja immer davon ausgehen, dass das, was wir beweisen wollen, bis dahin korrekt ist. Wir müssen nur zeigen, dass es im nächsten Schritt auch die Korrektheit erhalten bleibt. Das ist die Logik von Induktionsvoraussetzung. So, wir haben diesen Baum T, der bis dahin, bevor wir diese Kante rot gefärbt haben, alle blauen Kanten
01:11:21
enthält und noch keine rote Kante enthält. So, wenn diese wieder dieselbe Logik umgedreht, wenn diese Kante tatsächlich nicht in diesem ominösen Baum ist, ist trivialerweise die Invariante erhalten geblieben.
01:11:42
Es gibt diesen, dieser ominöse Baum enthält alle blauen bisherigen, nach Induktionsvoraussetzens alle, enthält keine bisherige rote und auch diese neue rote nicht. So, also hier ist wieder genau spiegelsymmetrisch der schwierige Fall, wenn die Kante in diesem Baum
01:12:02
ist. Wir haben jetzt plötzlich eine Kante, die wir rot färben, obwohl sie in diesem ominösen Baum drin ist. So, was ist hier die Logik?
01:12:26
Gut, genau, das ist die Logik. Wenn E tatsächlich eine Baumkante ist, dann wissen Sie, wenn Sie eine Kante rausnehmen, zerfällt der Baum in zwei Teile. Der eine Teil, wenn es gerade eine Kante zum Blatt ist, dann ist der eine Teil trivial, besteht
01:12:41
nur aus einem Knoten, allgemein besteht er aus zwei gewichtigeren Teilbäumen. So, wir nehmen die Kante raus, der Rest zerfällt in zwei Teile. Daher wissen wir, in diesem ominösen Baum T, da das ja ein Baum ist, muss es eine andere Kante gegeben haben, die diese beiden Teile miteinander verbindet. Das ist die
01:13:01
Kante E Strich. Sie sehen, es ist völlig spiegelsymmetrisch. Und wieder dieselbe Logik gilt. Wir haben ja jetzt umgedreht die schwerste Kante genommen, das heißt diese Kante E Strich, die im Baum drin ist, kann nicht schwerer sein als die Kante E, die wir rot gelabelt haben. Und wenn wir
01:13:21
also diesen ominösen Baum hernehmen, der E Strich enthält, aber nicht E und wir nehmen E Strich raus und packen E rein. Dann, nee umgekehrt, Entschuldigung, wie rum denn jetzt? Nehmen E raus und packen stattdessen, Moment halt,
01:13:42
ich hab's jetzt selber verwirrt. Also wir sind in dem Fall, dass E in dem Baum drin ist. Ach so, genau, der Zykel, der muss natürlich, Entschuldigung, ich weiß, was ist durcheinander gekommen. Der Zykel, der muss natürlich auch eine Kante
01:14:01
enthalten, der diese beiden Teile miteinander verbindet, sonst wäre es ja kein Zykel. Das ist die Kante E Strich. Und wenn wir jetzt E rausnehmen aus dem Baum und E Strich reinfügen, können wir keine, haben wir damit das Gewicht höchstens
01:14:21
reduziert oder gleich gelassen? Wir müssen es gleich gelassen haben, wir können es nicht reduziert haben, denn nach Voraussetzung war das ja die Ausgangskonfiguration ein minimal spannender Baum. Also muss das Gewicht, da das neue auch ein spannender Baum ist, muss das Gewicht gleich geblieben sein. Wir sind von einem minimal spannenden Baum zu einem
01:14:40
minimal spannenden Baum gekommen und haben mit diesem neu konstruierten minimal spannenden Baum wieder die Invariante erfüllt. Das ist jetzt einer der Punkte, wo ich sagen würde, ist nicht so dramatisch, wenn Sie das jetzt noch nicht so richtig ganz hundertprozentig durchschaut haben. Ich bin zuversichtlich, dass das gut möglich ist, das dann im stillen
01:15:01
Kämmerlein so weit nachzuvollziehen, dass die Glühbirne über dem Kopf anfängt zu schichten. Wir haben jetzt noch nicht gesehen, dass der Algorithmus tatsächlich terminiert.
01:15:23
Da war ich vorhin etwas salopp, ich habe einfach gesagt Termination, das sehen Sie ja, in jeder einzelnen Iteration wird eine Kante blau oder eine Kante rot gefärbt. Wir haben nur endlich viele Kanten, also nach endlich vielen Schritten haben wir Termination, nur ich habe dabei natürlich noch eine Kleinigkeit
01:15:41
ausgelassen, nämlich ob wirklich in jeder Iteration auch eine Kante existiert, auf die wir die blaue oder die rote Regel anwenden können. Also ich habe Ihnen, falls Sie mir bis eben geglaubt haben, dass Termination kein Problem ist, habe ich Ihnen da jetzt etwas untergejubelt, wo eigentlich ein bisschen
01:16:02
kritisches Nachfragen dann angebracht wäre, wobei ich natürlich nicht erwarte, dass Sie jetzt hier in der Situation der Vorlesung unbedingt diese kritischen Nachfragen sich stellen, aber später im schnellen Kämmerlein spätestens sollten Sie sich diese Nachfragen stellen. So, warum ist in jeder Iteration
01:16:25
entweder die blaue oder die rote Regel anwendbar? Mindestens eine von beiden, sodass wir also immer weitergehen können, dass der Algorithmus nicht mittendrin aufgeschmissen ist. Also wir sind in der Situation, dass wir noch nicht alle Kanten gelabelt haben, sonst ist ja nichts mehr zu zeigen. Wir haben noch mindestens eine Kante, die weder rot
01:16:41
noch blau ist. Die Invariante sagt uns, Inuktionsvoraussetzung wieder, dass die blauen Kanten Teil eines spannenden Baumes sind. Also mit anderen Worten, sie sind ein Wald. Teilen eines spannenden Baumes zu sein, also Teilmenge spannenden Baumes zu sein, ist ja nichts anderes, als ich auch sage, es ist ein Wald.
01:17:02
Dieser Wald könnte natürlich auch, wie ich eben schon angedeutet hatte, isolierte Knoten enthalten. Ja, das ist ein trivialer Baum innerhalb eines Waldes. So, E hat die Endknoten U und V. Jetzt machen wir eine
01:17:24
Fallunterscheidung, wo genau dann jetzt rot und wo wir jetzt sehen, im Fall eins können wir die rote Regel anwenden und dann im Fall zwei die blaue Regel und einer dieser beiden
01:17:40
Fälle wird immer auftreten. Diese beiden Fälle zerlegen die alle Möglichkeiten, überdecken alle Möglichkeiten. So, der eine Fall ist, dass die beiden momentan die beiden Endknoten von dieser Kante zum selben Baum gehören. Da sind wir genau in der Situation, die ich für Kruskal vorhin skizziert hatte.
01:18:01
Wir können jetzt die rote Regel anwenden, nämlich das muss in dem Moment die schwerste Kante sein, weil alle anderen Kanten in dem Moment blau sind und damit Teil eines
01:18:21
minimalspannenden Baums. Also muss diese Kante, die wir jetzt hier gewählt haben, die schwerste sein. Also können wir sie rot labeln, nach der roten Regel, dass wir immer die schwerste Kante in einem Fall. Das ist unterschiedliche Bäume sind, habe ich das nicht noch gezeichnet.
01:18:41
Ja, hier sehen Sie sogar noch das Bild, was ich vorhin gezeichnet habe. Für Kruskal, was jetzt hier sinngemäß eben allgemein so ist, dieses Bild ist ja, wie Sie jetzt skizziert habe, enthält natürlich auch das Bild für Algorithmus prim als Spezialfall. So, und
01:19:01
wenn Sie aber, wenn diese Kante zwei unterschiedliche Kanten, zwei unterschiedliche Bäume miteinander verknüpft, dann können wir zwischen
01:19:22
diesen beiden unterschiedlichen Bäume einen Schnitt ziehen und sind genau bei der blauen Regel, dass wir da jetzt eine Kante blau färben können.
01:19:42
Okay, hier ist noch eine Feinheit drin, die hier ausgedrückt ist. Wir nehmen uns eine ungelabelte Kante her und es sieht jetzt so aus, vielleicht für Sie, für mich auch für einen Moment, dass die Logik des Überweisers die ist. Wir zeigen, wir können diese Kante labeln, rot oder
01:20:02
blau. Klingt ja irgendwie plausibel, aber so viel müssen wir gar nicht zeigen. Wir müssen nur zeigen, wenn es eine ungelabelte Kante E gibt, dann können wir noch irgendeine ungelabelte Kante labeln. Das muss nicht aber nicht unbedingt E sein. Solange es eine ungelabelte Kante gibt, ist der Algorithmus noch nicht aufgeschmissen. Aber es muss nicht
01:20:21
diese Kante sein, die er labelt, nämlich stattdessen die leichteste Kante, die in diesem, die leichteste Kante. Und das ist dieselbe Logik hier oben auch. Es muss auch nicht unbedingt diese Kante sein, die rot gelabelt ist. Also Sie sehen, es ist eine Menge von hinten durch die Brust ins Auge. Muss man sich
01:20:41
Schritt für Schritt vielleicht noch mal auseinanderfütteln. Vielleicht, wenn Sie da gar nicht hintersteigen, machen Sie sich vielleicht mal noch Beispiele, dann wird es denke ich klarer. Gut, eine letzte Bemerkung dazu, dass dieses Labeling nicht deterministisch ist. Das bedeutet,
01:21:04
es ist nicht von vornherein spezifiziert, in welcher Reihenfolge wir Kanten wählen und ob wir jetzt die rot oder blaue Regel anwenden wollen, dafür jeweils eine passende Kante finden wollen, sondern wenn wir effizient implementieren wollen, zum Beispiel Prim oder Kruskal, dann
01:21:22
müssen wir genauer sagen, in welcher Reihenfolge, mit welchen Kanten wir welche Regel anwenden. So, damit haben wir den Algorithmus, diesen allgemeinen Algorithmus vollständig behandelt, der Prim und Kruskal als zwei Spezialfälle.
01:21:42
Jetzt kommen wir noch mal ganz kurz zu einem bösen Thema, die Sache noch mal viel allgemeiner zu sehen. Keine Sorge, man kann es verstehen. Es gibt den positiven Beweis, dass Menschen in der Lage sind, das zu verstehen, auch Studierende.
01:22:11
Der Algorithmus von Kruskal ist das, was man einen greedy Algorithmus nennt, einen gierigen Algorithmus nennt. Er geht die Kanten
01:22:23
von der billigsten Kante bis zur teuersten Kante durch und bei jeder Kante guckt, da kann ich die einfügen, wenn ja, tue ich das. Wenn Sie sich zum Beispiel vorstellen, auf die Art und Weise, ich sollte mich hier nicht aufstützen auf der
01:22:43
Steuerung der Anlage, sonst geht gleich hier alles aus. Wenn Sie sich vorstellen, Sie gehen auf die Art und Weise vor, bei kürzesten Wegen immer die billigste Kante zu nehmen, passt, ja, passt nicht, nein, das funktioniert natürlich nicht. Da kommt irgendein Blödsinn dabei raus, kommt wahrscheinlich nicht mal ein Weg raus, geschweige dann kürzester Weg. Das liegt da, dass das bei
01:23:04
MST funktioniert so primitiv, dass wir uns sicher sein können, wir gehen einfach die Kanten in dieser Reihenfolge durch und das, was im Ende rauskommt, ist garantiert und unter allen Umständen eine minimale Lösung. Das liegt daran,
01:23:20
dass MST, Minimalspannung und Baum, eine bestimmte strukturelle Eigenschaft hat und diese strukturelle Eigenschaft nennt man Matroid. Und alle Problemstellungen, die diese spezifische strukturelle Eigenschaft haben, für die gilt, dass dieser GRIDI-Algorithmus immer zusammensammeln, vom billigsten zum teuersten, dass der immer die optimale Lösung liefert. So ein
01:23:43
schönes Werkzeug. Der Name Matroid kommt daher, dass die Spalten einer Matrix im Sinne linearer Unabhängigkeit auch ein Matroid bilden. So was ist ein Matroid? Das ist eine Menge, eine endliche Menge, das ist hier nicht
01:24:02
verzeichnet, aber es ist immer eine endliche Menge. Matroid ist nie definiert auf unendlichen Mengen und wir haben jetzt was blödes hier. Was wir haben, ist eine Menge von Teilmengen von dieser Grundmenge. Die gehen wir
01:24:21
mal durch. Ne, den brauchen wir noch nicht. So. Was bedeutet diese Bedingung? Was bedeutet das alles an dem konkreten schönen Beispiel spannende Bäume, spannende Wälder?
01:24:41
Also die Grundmenge E ist bei uns, bei unserem minimalen Spannungsbaum Problem, tatsächlich die Kantenmenge. U ist die Menge aller Wälder. So, was für Eigenschaften hat die Menge aller Wälder auf einer gegebenen Kantenmenge in einem gegebenen Grafen? Naja, die Lederkantenmenge
01:25:02
ist natürlich auch ein Wald, ein trivialer Wald oder der triviale Wald. Wenn ich einen Wald B habe und A ist eine Teilmenge von B, ich nehme mir einen Wald B her und ich nehme noch Kanten raus, dann ist das Ergebnis natürlich auch wieder ein Wald. Das sagt diese zweite
01:25:22
Bedingung. Wenn A eine Teilmenge B ist und B ist ein Wald, dann ist A auch ein Wald. Wobei übrigens dann die erste Bedingung natürlich redundant ist. Aus der zweiten Bedingung folgt natürlich sofort das erste. So, jetzt kommt das fiese. Das müssen wir dann anhand
01:25:42
des Beweises auch genau klären, was da eigentlich steht, was das eigentlich bedeutet. Ich weiß nicht, inwieweit Sie da in der Linie algebra eingestiegen sind, aber bei einer endlichen Menge von, auch bei einer unendlichen Menge, aber uns interessiert nur eine
01:26:00
endliche Menge, bei einer endlichen Menge von Vektoren, ist diese Eigenschaft, die da unter Punkt 3 steht, gerade das steinische Austauschlämmer, falls Ihnen das begegnet ist in der Linie algebra. Wohl eher nicht. Okay, vergessen Sie wieder, was ich gesagt habe. Oder
01:26:20
vergessen Sie es nicht und gucken Sie sich bei Gelegenheit mal an. Wie gesagt, lineaunabhängige Vektoren sind ein anderes Beispiel für Matroide. So, was steht da? Das lassen wir mal links liegen, was hier in Punkt 3 steht, weil das ist ein schönes Beispiel dafür, dass
01:26:41
man Dinge manchmal durch den Beweis besser versteht oder überhaupt erst gut versteht, als wenn man nur versuchen wollte, das Theoremen selber für sich zu verstehen. Der Beweis konstruiert praktisch ein Beispiel dafür oder konstruiert die Situation. Wir sind sowieso jetzt mehr oder weniger fertig für heute,
01:27:00
fast mehr oder weniger. So, die Aussage hier ist, die wird nicht bewiesen hier, die beweise ich in der Parallelveranstaltung Optimierungsalgorithmen. Wenn wir ein Matroid haben, dann wird dieser Gridi-Algorithmus, wo Kruskal eben
01:27:20
der Gridi-Algorithmus für minimal spannende Bäume ist, dieser kanonische Gridi-Algorithmus, dass wir alle Elemente nacheinander in aufsteigender Sortierreitenfolge durchgehen und gucken, passt rein, nehmen wir es rein, wenn nicht, vergessen wir es und gucken uns nie wieder an. So, für ein Matroid ist der kanonische Gridi-Algorithmus
01:27:41
bezüglich beliebiger Gewichte und der Gridi-Algorithmus ist besonders als Corolla, Kruskal ist optimal. Was hier nicht formuliert ist, aber was ich Ihnen gerne noch mündlich dazu sagen möchte, ist, dass das eine Äquivalenz ist. Wenn
01:28:01
es kein Matroid ist, wenn es nicht diese drei Eigenschaften mit aufsteigender Hässlichkeit hat, wenn es kein Matroid ist, dann kann man immer eine Gewichtung finden, bei der der Gridi-Algorithmus Blödsinn produziert. In dem Sinne ist Theorem 6 tatsächlich
01:28:24
über die konkrete Formulierung dieser Folie hinaus eine Äquivalenz. Wenn es ein Matroid ist, dann funktioniert der Gridi- Algorithmus für jede Gewichtung, wenn es kein Matroid ist, funktioniert der Gridi-Algorithmus für mindestens eine Gewichtung nicht. Mindestens eine heißt
01:28:40
natürlich auch, für unendlich viele andere Gewichtungen funktioniert da auch nicht. So, was hier erwiesen wird, aber dazu kommen wir heute nicht mehr, ist, dass MST, die Wälder, in einem ungerichten Graphen bilden ein Matroid. Und
01:29:01
wenn wir den Beweis durchgehen, dann wird, denke ich, klar werden, was diese hässliche dritte Zeile hier zu bedeuten hat. Werden wir vielleicht dann nochmal an einem anderen Beispiel linearunabhängige Vektorenmengen auch nochmal betrachten. Kleine Erinnerung an die linear algebra und dann haben wir dieses hässliche Thema auch ganz
01:29:21
schnell wieder hinter uns gebracht und dann können wir beim nächsten Mal konsequent von den ungerichteten Graphen weggehen und den spannenden Bäumen hin zu etwas Neuem. Gerichtete Graphen und darauf sozusagen das Äquivalent zu minimal spannenden Bäumen. Das nennt sich dann Branchings. Vielen Dank. Und denken Sie bitte
01:29:43
daran, erstens, Abgaben noch, soweit Bedarf besteht, hier, heute. Und denken Sie bitte nochmal daran, dass sich ja der Übungstermin geändert hat.