Optimal Trees and Branchings II / Shortest Paths I
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 | 6 | |
| 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/21474 (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
Mathematical optimizationMaxima and minimaEquals signSet (mathematics)SubsetNetwork topologyKanteSpanning treeChain complexSummationWeightStress (mechanics)Zusammenhang <Mathematik>Connected spaceModulformGreatest elementComputer animation
03:15
Mathematical optimizationFundamental theorem of algebraComplex (psychology)Decision theoryWeightGraph (mathematics)Graph (mathematics)SubgraphInclusion mapCategory of beingProof theoryDuality (mathematics)Inclusion mapKanteSet (mathematics)EquationCompass (drafting)Inequality (mathematics)Film editingChain complex8 (number)Lecture/ConferenceComputer animation
09:34
Graph (mathematics)WeightSubgraphMathematical optimizationGraph (mathematics)Inclusion mapCategory of beingProof theoryVertex (graph theory)AirfoilInsertion lossGroup actionKanteKopplung <Physik>Set (mathematics)Stress (mechanics)Graph (mathematics)Chain complexSubgraphComputer animation
15:51
Proof theoryFeasibility studyLemma (mathematics)Graph (mathematics)Uniqueness quantificationWeightGraph (mathematics)Maxima and minimaMathematical optimizationVertex (graph theory)Directed graphStress (mechanics)TheoryKanteConnected spaceZusammenhang <Mathematik>TheoremChain complexVertex (graph theory)Computer animation
24:22
Graph (mathematics)Alpha (investment)WeightGraph (mathematics)Maxima and minimaMathematical optimizationVertex (graph theory)TheoremProof theorySign (mathematics)Function (mathematics)Rule of inferenceBinary fileChain complexKanteStress (mechanics)Musical ensembleQuoteHausdorff spaceComputer animation
32:54
Maß <Mathematik>Equals signMathematical optimizationMach's principleGraph (mathematics)Correspondence (mathematics)Arrow of timeTransformation (genetics)KanteField extensionWeightStress (mechanics)QuoteNumberMusical ensembleCompass (drafting)Maß <Mathematik>Matching (graph theory)Chain complexComputer animation
41:25
Mathematical optimizationWeightGraph (mathematics)Vertex (graph theory)Axiom of choicePhase transitionNegative numberThermal expansionTheoremTravelling salesman problemBound stateNetwork topologyStandard deviationMaxima and minimaForestChain complexHausdorff spaceKanteRekursiver AlgorithmusSet (mathematics)Stress (mechanics)Series (mathematics)Moment (mathematics)Diagram
47:12
ForestMathematical optimizationStandard deviationGraph (mathematics)Boom barrierDirected graphLengthMaxima and minimaEnumerated typeTotal S.A.Complete metric spaceEstimationVertex (graph theory)Physical systemMatroidSubsetElement (mathematics)Independence (probability theory)Function (mathematics)Proof theoryPairwise comparisonSet theoryCategory of beingNegative numberTwin primeHamiltonian (quantum mechanics)Link (knot theory)Graph (mathematics)Reduction of orderMatching (graph theory)Bound stateDistanceSupremumMatroidKanteGraph (mathematics)Negative numberLengthSummationParallelenDesire pathWeightNormaleSpanning treeWegeproblemUniverse (mathematics)Chain complexSubsetStress (mechanics)Unit of lengthSet (mathematics)EnergieComputer animation
56:04
Mathematical optimizationIterationInfinityBound stateDistanceGraph (mathematics)LengthVertex (graph theory)Category of beingUniqueness quantificationDirected graphNetwork topologyWurzelbaumExistenceVector spaceArc (geometry)Range (statistics)Military operationDesire pathMoment (mathematics)Direction (geometry)Graph (mathematics)Network topologyKanteWurzelbaumTrailLengthComputer animation
01:04:42
DistanceMilitary operationTwin primeMereologySequenceBooby trapProof theoryDirected graphNegative numberWurzelbaumOperations researchLink (knot theory)Range (statistics)Network topologyLengthStress (mechanics)LogicLink (knot theory)KanteWeightMoment (mathematics)Military operationDesire pathQuoteP-valueComputer animation
01:13:20
LengthFunction (mathematics)Directed graphSet theoryRadical (chemistry)Term (mathematics)Proof theoryLengthStress (mechanics)State of matterEquationPerimeterIterationCoefficient of determinationP-valueComputer animation
01:21:58
Insertion lossNegative numberWeightAxiom of choiceInequality (mathematics)Proof theoryGraph (mathematics)Military operationDistanceTotal S.A.Operations researchObject (grammar)Queue (abstract data type)Maxima and minimaPriority queueIterationLaufzeitSet (mathematics)Greatest elementLengthSquareMaximum (disambiguation)MathematicsSequenceLogicEnde <Graphentheorie>EckeRoundingFactorizationTrailEigenvalues and eigenvectorsMoment (mathematics)Computer animation
01:30:35
Binary fileCategory of beingElement (mathematics)Network topologyAlgebraic structureNegative numberGraph (mathematics)Operations researchRule of inferenceMathematical structure
Transcript: German(auto-generated)
00:01
präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits. Heute, wir haben beim letzten Mal intensiv schon über die gerichtete Variante vom Minimum Spanning Tree gesprochen und werden das
00:21
heute jetzt erst einmal abschließen, bevor wir zum nächsten Kapitel kommen. Da haben wir schon eine ganze Menge dazu gesagt. Ich will nur mal ganz kurz für den Einstieg dann ein paar wesentliche Eckpunkte hier noch mal skizzieren. Was war das nochmal ein Branching? Die gerichtete Variante, das bedeutete, sie haben gegeben einen gerichteten Grafen, nicht mehr einen
00:44
ungerichteten, sondern einen gerichteten Grafen. Wie bei Minimum Spanning Tree haben sie auf den gerichteten Kanten jetzt Gewichte, die auch nicht negativ sein sollten und was sie haben wollen ist wieder eine Teilmenge der Gesamtknotenmenge, die aber zwei Eigenschaften erfüllen soll. Erstens
01:07
natürlich zykelfrei, allerdings gerichtet zykelfrei. Also wir wollen in dieser Teilmenge keinen gerichteten Zykel drin haben. Wir wollen aber auch in dieser Teilmenge keine zwei Kanten haben, die
01:24
in den selben Knoten reingehen. Was ergibt sich daraus? Daraus ergibt sich sich vorstellen können, was sie in der GDE 2 als Bäume gelernt haben mit einer Wurzel und dann geht es immer runter, die Äste runter bis zu den Blättern, dass wir mehrere davon haben. Einen so vielleicht, so, dann geht es wieder
01:49
weiter, kann natürlich auch mehr als, muss nicht binär sein, kann auch beliebig viele Nachfolger haben, aber es muss nicht nur ein solcher Baum
02:00
sein. Jetzt habe ich das Wort Baum verwendet, das natürlich hier nicht Fachterminologie ist, sondern Fachterminologie ist für ein solches Gebilde aus mehreren Zusammenhangskomponenten branching und das Einzelne heißt, das haben wir ja gesehen, aborescence, da hinten drin steckt aber doch dann wieder abor, lateinisch der Baum und natürlich kann
02:21
es kann es auch einzelne Zusammenhangskomponenten geben, die nur aus zwei Knoten oder sogar nur aus einem Knoten bestehen, das ist alles erlaubt. Im extremen Fall, ein Graf nur mit Knoten ohne Kanten wäre auch ein branching. So und was wir jetzt herausfinden wollen, ist einem gegebenen Grafen ein solches branching, eine solche Teilmenge, die so
02:42
strukturiert ist, aber maximales Gesamtgewicht hat, wieder wie üblich Gesamtgewicht heißt Summe der Gewichte der einzelnen Kanten. Wir haben schon beim letzten Mal gesehen, einfach so drauf loszumachen, so wie auf dieser Folie, bringt ein schlechtes Ergebnis, wenn wir hier als
03:01
erstes die drei nehmen, weil es die schwerste Kante ist, dann verbauen wir uns jeden Weg dahin zur einzig optimalen Lösung, nämlich dass wir die drei zweier Kanten nehmen und die dreier Kanten vergessen. Also müssen wir intelligent davor gehen und ja, das war der intelligente Mensch. Machen
03:23
wir mal einen Sprung hier hin. Kritische Grafen sind das Wesentliche, das haben wir beim letzten Mal auch schon mit, auch schon gesehen. Was ist ein kritischer Graf? Nochmal, dass das genau klar ist. Für jeden einzelnen Knoten
03:43
nehmen wir uns eine Kante her, die die schwerste Kante ist. Zum Beispiel hier, die Kante mit Gewicht sechs, ist die schwerste Kante, die in den Knoten Nummer drei hineingeht. Also eine schwerste hineingehende Kante. Hier war ein Beispiel, die zwei, dass zwei Kanten mit Gewicht drei jeweils
04:01
hineingehend, davon wählen wir uns dann eine von beiden beliebig. Ja, also wir sind schon in gewisser Weise in der Nähe von so einem Branching, aber wir sind noch nicht an einem Branching. Wir haben im Normalfall konstruieren wir damit kein Branching, sondern Sie sehen etwa hier vier, sechs, fünf ist ein Zykel oder hier null und eins ist ein Zykel,
04:23
wollen wir im Branching ja nicht haben. Was wir aber zunächst mal haben ist die Eigenschaft, dass in jeder einzelne Kante maximal ein Knoten hineingeht. So, das ist ein kritischer Graf und was wir uns zunächst mal
04:41
klar machen müssen, ist das Lemma 10. Also oben ist noch mal die Definition eines kritischen Grafen und eine kritische Kante. Was ist eine schwerste Kante, die in einen Knoten reingeht, ist eine kritische Kante für diesen Knoten. Nichts anderes steht da und der kritische Subgraf ist ein
05:04
Graf, der eben wie eben gesagt nur aus solchen kritischen Kanten besteht. Wir nehmen für jede Knoten eine schwerste Kante und das hatte ich jetzt vergessen zu sagen. Inklusionsmaximal noch mal zurück. Inklusionsmaximal heißt, wir können keine weitere Kante hinzunehmen,
05:24
ohne uns hier irgendwas zu zerstören. Egal welche Kante Sie hinzunehmen, es ist eine Kante, die in einen Knoten zeigt, wo schon eine andere Kante hinein zeigt. Wir können nichts hinzunehmen, das ist Inklusionsmaximal. So, warum das Ganze was mit Branchings zu tun hat, da nähern wir uns
05:45
erst einmal an diesem Lemma 10, wobei ich habe hin und her überlegt, ich bin mir nicht sicher, ob dieser Beweis so ohne weiteres, wie er hier steht, wirklich korrekt ist oder glaube ich nicht, aber vielleicht habe ich auch was übersehen. Ich will Ihnen sagen, was ich für Probleme mit diesem Beweis
06:04
hatte und bzw. was ich mir überlegt habe, dass es dann stimmt. Also erstmal, was steht denn hier in diesem Beweis? Wir betrachten einen Branching, nein, wir betrachten einen kritischen Grafen, der a-zyklig ist und
06:25
wir wollen beweisen, dass das ein maximales Branching ist. Maximal heißt also, hat maximales Gewicht. Also erst einmal, wenn er a-zyklig ist, ist er natürlich ein Branching, denn was waren die beiden Eigenschaften? a-zyklig und maximal eine Kante geht in jeden Knoten rein, maximal eine Kante geht rein, war schon eine Definition von kritischen
06:44
Grafen drin und a-zyklig wird jetzt hier im Lemma als Voraussetzung gefordert. So, also es ist ein Branching. Jetzt gucken wir, jetzt vergleichen wir dieses Branching H mit irgendeinem anderen Branching B und wollen zeigen, dass H nicht weniger Gewicht hat, als dieses irgendwelche
07:00
beliebige Branching B. Und der Gedanke hier ist offenbar, was hier in dieser Gleichung steht. Was steht denn hier in dieser Gleichung? Was ist das für ein Termin? Die Kosten von irgendwas B geschnitten, was ist das? B,
07:24
ein Branching geschnitten mit der Menge aller Kanten, die in V hineingehen. Wir haben einen Knoten V und wir betrachten alle Kanten, die in V hineingehen. B ist ein Branching. Das heißt also, maximal eine dieser
07:45
Kanten haben wir hier, die aus dem Branching B ist oder alternativ keine dieser Kanten ist aus diesem Branching, dann ist dieser Schnitt leer. Dann die Kosten einer leeren Menge sind per Definition Null. Wir betrachten
08:01
also einerseits dieses und andererseits noch mal der selbe Knoten V mit denselben Kanten und haben irgendeine andere Kante aus maximal eine Kante
08:24
hier raus. Und die Aussage ist, dass die eine Kante von dem beliebig gewählten Branching B höchstens so hohes Gewicht hat, wie die andere Kante von unserem kritischen Grafen H. Das klingt erst mal absolut plausibel,
08:46
denn wir wählen ja in H immer die Kante mit maximalem Gewicht. Klingt also erst einmal absolut plausibel, dass dieser Beweis das schon erledigt hat. Diese Kante ist per Definition die schwerste Kante, die
09:02
reingeht, also kann sie nicht weniger schwer sein als D. Und wenn wir das über alle Knoten haben, dann haben wir das Gesamtgewicht des a-zyklusischen Grafenes größer als das Gesamtgewicht dieses Vergleichs Branchings B. Nur, das setzt natürlich voraus, dass es diese Kante gibt.
09:24
Das scheint hier ein Beweis vorausgesetzt zu sein und das ist nicht unbedingt korrekt meines Achtens. Also vielleicht habe ich irgendwas übersehen, vielleicht ist der Beweis doch korrekt, aber ich habe es nicht gesehen. Also ist erst mal klar, wo die potenzielle Lücke in meiner
09:41
Interpretation dieses Beweises drin ist. Dann will ich Ihnen zeigen, wo ich das Problem drin sehe, nämlich in Zyklen im Grafen.
10:06
Also das einzig nennenswerte an Aktion, was diese Kamera aufnimmt, ist das Tafelwischen an Aktion. Natürlich die Standbilder, die dann immer da stehen bleiben, sind sicherlich, hoffe ich mal, auch von einem gewissen Wert. So, das Problem ist, wir gucken uns mal einen Zykel im
10:24
Grafen an. Mal gucken, ist der in der Kamera drin? Ja, ich kann ihn vage erkennen. Das ist der Zykel im Ausgangsgrafen, den wir uns
10:44
angucken. Und jetzt kann es natürlich sein, natürlich kann nicht der ganze Zykel drin sein, weder in dem Branching B noch in dem A-Zyklus, denn A-Zyklus kann auf jeden Fall nicht drin sein. Also er kann
11:04
weder in dem Branching B drin sein, noch in dem kritisch grafen H, denn H war ja als A-Zyklus gedacht. Es kann jetzt aber so sein, dass in, jetzt muss ich mal sehen, ich habe mir das vorher notiert, damit ich das jetzt nicht falsch zeichne. So, es kann jetzt zum
11:31
Beispiel so sein, dass der Graph H so aussieht, dass diese Kante hier
11:41
fehlt und umgekehrt kann es bei B so aussehen, dass diese Kante drin ist, aber beispielsweise diese Kante fehlt. Ja, dann stimmt die Argumentation von eben nicht mehr. Sie stimmt nicht mehr an der einen Stelle, wo B eine Kante hat, aber H nicht. Ja, an dieser Stelle kann
12:10
man nicht, an diesem Knoten kann man nicht mehr sagen, das Gewicht der reingehenden Kanten in H ist größer als das Gewicht der reingehenden Kante in B, denn es gibt potenziell keine reingehende Kante. Wieso
12:35
sind beide Subgraphen keine kritischen Graphen mehr? Wieso? Also B
12:44
soll ja sowieso kein kritischer Graph sein. Also mit B haben Sie kein Problem. Genau. Sie haben jetzt hier ein Problem, dass das nicht mehr maximal ist. Genau. Ach so, das könnte sein, dass wir jetzt doch
13:01
wieder dahin kommen, dass der Beweis so ist, wie er korrekt ist. Also, hier geht dann, es gibt ja mindestens eine Kante, die reingeht, aber das ist, nein, nein, nein, das ist, okay, genau, genau, genau,
13:21
diese Konstruktion, Sie haben recht, diese Konstruktion widerspricht der Voraussetzung, dass das, was ich hier auf der linken Seite habe, H, ein a-zykluscher kritischer Graph ist. Es ist zwar a-zyklusch, aber nicht mehr kritisch, denn ich kann eine Kante hinzu, ja, das ist der Punkt.
13:41
Außer die Kante kommt von hier, das könnte ja auch eine sein, aber dann geht wieder die Argumentation. Die Kante, da dieser Graph kritisch ist, kann die Kante nicht leichter sein als diese Kante. Okay, also die Argumentation stimmt, hätte ruhig natürlich auf der Folie ein bisschen
14:00
mehr Butter bei der Fische geben können, aber genau, das ist der Punkt. So wie ich es erst gezeichnet habe, kann das kein, ist zwar a-zyklusch, aber kann das kein kritischer Graph sein, denn dazu müsste man mindestens eine Kante hinzunehmen, und wenn es die Kante ist, hier, ist es egal, dann kommt es auch selber raus. Wenn es eine andere Kante ist,
14:22
dann muss das per Definition eine kritische Kante sein, muss mindestens so schwer sein wie hier. Okay, dann stimmt die Argumentation, wie es auf der Folie ist. Vielen Dank. Gut, dann haben wir das soweit geklärt, aber ich schätze mal, mit dieser kleinen 5 Minuten Aufnahme von diesem
14:41
Thema haben wir Ihnen später bei der Vorbereitung auf die Prüfung einiges an Kopfschmerzen erspart, weil wir ja jetzt nochmal genauer gesagt haben, warum dieses Argument tatsächlich stimmt. Ist das soweit klar geworden? Also mir ist es jetzt klar geworden. Okay, ja nun, ich meine,
15:03
Sie wissen, dass Professoren auch nicht allwissend sind. Wissen Sie auch, oder? Gut, aus eigener Erfahrung nehme ich an. So, also, dieses Lämmer
15:21
sagt schon mal, dass kritische Grafen eine ganze Menge mit maximalen Branchenks zu tun hat. Einfach nur durch diese Kopplung, wenn der kritische Graf schon adzyklisch ist, dann ist er das schon. Also ist die Frage, wie weit weg kommen wir? Was müssen wir noch tun, wenn wir einen kritischen Grafen konstruiert haben? Der ist ja leicht zu konstruieren,
15:42
effizient zu konstruieren. Was müssen wir noch tun, wenn der nicht adzyklisch ist? Das ist ja die Frage. So, und dann gehen wir mal so ein paar Sachen überspringen wir nochmal wieder. Irgendwo müsste jetzt demnächst ein Bild, ein Bildchen wieder kommen. Nee, erst mal kommt dieses Theorem. Also Bild kommt erst später, erst kommt Theorem. So,
16:05
habe ich auch nichts, was ich in meinem Fahrplan geschrieben habe, übersprungen? Nee, habe ich nichts übersprungen. So, ich habe jetzt einiges an mathematischer Bürokratie übersprungen. Ich will versuchen, das wieder, wie ich das schon an einen Stellen gemacht habe, mehr
16:22
hoffentlich etwas illustrativer näher zu bringen. So, wir haben eben gesagt, wenn der kritische Graf, den wir uns betrachtet haben, wenn der schon adzyklisch ist, sind wir fertig. Dann haben wir ein maximales Brandschenk. Jetzt kommen wir einen Schritt näher. Jetzt haben wir irgendeinen kritischen Grafen, der in der Regel nicht adzyklisch ist, der also solche kritischen Zügele enthält. Dann wird gesagt,
16:44
das sind wir immer noch nicht allzu weit weg. Dann gibt es ein Brandschenk B, was sehr eng an diesen kritischen Grafen gekoppelt ist durch diese Bedingung, die hier in der zweiten Zeile des Theorems steht. Und was sagt diese Bedingung, die hier steht? Jetzt will ich aber zu einem Bild. Da. Was sagt diese Bedingung? Diese
17:06
Bedingung sagt, ich kann aus jedem Zügel in meinem kritischen Grafen eine bestimmte Kante rausnehmen, kann ihn zykelfrei machen durch Wegnahme von Kanten. Und wenn ich das richtig gemacht habe, dann ist das, was übrig bleibt, tatsächlich ein maximales
17:24
Brandschenk. Ist erstmal was Schönes. Ich nehme, ich gucke mir an, wo ist der Graf nicht zykelfrei. Ich nehme eine Kante raus und das ist dann maximales Brandschenk. Problem ist natürlich, welche Kante ich rausnehme. Offensichtlich kann ich das nicht
17:41
beliebig machen. Und in diesem einfachen Beispiel hier würde es schon hinreichen, dass ich jeweils die leichteste Kante rausnehme. Das ist dann, weil diese beiden Zyklen überhaupt nichts miteinander zu tun haben. Aber stellen Sie sich vor, in einer komplexe, ineinander verschlungenen Zyklenstruktur,
18:00
bis hin im Extremfall, dass sämtliche Kanten, sämtliche möglichen Kanten drin sind im Grafen, also alles Mögliche zykelt, ist erstmal nicht mehr klar, welche Kanten man daraus nehmen soll. Und das macht jetzt noch uns diese Arbeit. Aber als Vorbereitung brauchen wir dieses Theorem 10 hier, 17, Entschuldigung, Theorem 17. Wenn ich einen
18:27
kritischen Grafen H habe, gibt es einen Brandschenk, kann ich einen Brandschenk B daraus konstruieren aus H, sodass ich für jeden Zykel in meinem konstruierten
18:43
kritischen Grafen einfach eine Kante rausnehme. Dieser kritische Zykel im kritischen Grafen, alles weggenommen, was zum Brandschenk gehört, ist eins, eine Kante rausnehmen, dann habe ich meinen Brandschenk. So, warum ist das so? Das will ich Ihnen diese drei verschiedenen Fälle, die
19:29
so wir betrachten zunächst einmal hier in dieser Formulierung gehen wir von einem maximalen Brandschenk aus,
19:45
dass sehr nah an unserem kritischen Grafen ist, nämlich so nah von allen möglichen maximalen Brandschenk nehmen wir B als einen, der so viele Kanten wie möglich gemeinsam hat mit dem kritischen Grafen,
20:00
den wir konstruieren wollen, als Trick, um irgendwo später einen Widerspruch herzukriegen. Also wir gehen erstmal von einem Brandschenk B aus und wir haben schon gesehen, wie so ein Brandschenk aussieht, das zeichnet man in der Informatik ja immer so nach unten, die Wurzel ist ganz
20:22
oben, hier ist der nächste vielleicht, ich zeichne mal noch einen größeren, so ein bisschen schematisch, so das ist eine größere Zusammenhangskomponente, geht natürlich auch
20:41
alles runter, so. Und jetzt betrachten wir uns eine Kante, die nicht zu diesem Brandschenk gehört. Oder genau gesagt, wir betrachten uns mehrere Kanten. Deshalb habe ich den
21:00
Grafen etwas schematischer, größer gezeichnet, um es möglichst allgemein zu halten. Es gibt jetzt verschiedene Arten, wie Kanten hier verlaufen können. Eine Möglichkeit ist zum Beispiel so, von einem Knoten zu einem Nachfolger
21:23
desselben Knotens. Eine andere Möglichkeit wäre genau umgekehrt, von einem Knoten zu einem Vorgängerknoten, genau umgekehrt. Eine andere Möglichkeit, die roten sind, Kanten, die nicht zum Brandschenk gehören. Eine andere Möglichkeit wäre beispielsweise hier so eine Brücke zu schlagen,
21:42
von einem Knoten zu einem anderen Knoten, die nicht in Vorgängerbeziehung zueinander stehen. Oder auch nicht zu vergessen, eine Möglichkeit wäre beispielsweise eine Kante hier hin zu zeichnen. Dann ist das ganze Bild bis oben hin drauf.
22:08
Ich hoffe, das Rot sieht man dann gut. So, eine Kante hier fällt raus von diesen Vieren, die ich eingezeichnet habe.
22:22
Ja, das sind so die vier Möglichkeiten. Die, die raus fällt, ist folgende, die uns stört. Nämlich, wenn ich zum Beispiel diese Kante hier betrachte, wenn ich die einfüge und dafür diese Kante lösche, die andere, ja, diese
22:42
Kante hier, die reingeht in diesen Knoten, ersetze durch diese Kante, dann ist das Ergebnis wieder ein Brandschenk. Ja, es ist weiterhin zügelfrei und es geht weiterhin nur eine Kante in jeden Knoten hinein. Dasselbe hier, wenn ich die Kante einfüge und dafür die andere in diesen Knoten hineingehende lösche, ist das Ergebnis wieder ein
23:02
Brandschenk. Weil hier die lösche ich dann, dann hängt dieser ganze Teil Brandschenk eben an dieser Kante und nicht nur mehr an dieser Kante. So, dasselbe hier. Hier sogar noch einfacher. Hier habe ich eine Aboraszenz an der andere angehängt. Ist weiterhin ein Brandschenk. Aber
23:22
wenn ich dasselbe hier mache, mit dieser Kante, dann funktioniert das nicht mehr. Denn wenn ich jetzt diese Kante einfüge und dafür diese Kante lösche, dann habe ich hier einen Zykel geschlossen. Kanten, die von einem
23:41
Knoten zu einem Vorgängerknoten gehen, sind speziell in diesem Sinne. Ich kann sie nicht einfügen, dafür die andere Kante, die hier reingehen, löschen, weil das dann kein Brandschenk mehr ist. Ja, so. Und das ist das, was Sie im Skript finden. Diese Kante hier hat die Eigenschaft Feasible. Also
24:04
eigentlich heißt Feasible im Englischen durchführbar. Aber in unserem Kontext hier übersetzt man das meistens mit zulässig erlaubt. Diese Kante hier ist Feasible. Diese Kante hier ist Feasible.
24:24
Und die hier ist nicht Feasible. Das ist der Begriff, den Sie in den Folien finden und auch in der Literatur dazu. So, ja, dieses Bild müssen wir uns
24:41
klar machen. Es gibt Feasible-Kanten und es gibt nicht Feasible-Kanten. Jetzt gehen wir wieder zurück zum Beweis. Keine Sorge, wir werden gleich wieder zu dieser Bild kommen. Gibt es noch eine Frage? Die hier. Ja, gemacht. Ja, Sie haben recht, das
25:05
müsste im maximalen Brandschenk drin sein. Sie haben jetzt den ersten Spiegelstrich vorweggenommen. Ja, der Unterschied ist einfach der, wenn wir jetzt die Fallunterscheidungen auf der Folie machen,
25:21
dann ist das ein eigener Fall. Deshalb habe ich diese Kante mit eingezeichnet. Sie haben voll und ganz recht. So, wir haben uns jetzt dieses maximale Brandschenk B angesehen, das so viel wie möglich gemeinsam hat an Kanten mit dem kritischen Graphen, den wir in der Hand haben. Den haben wir konstruiert und wollen
25:41
jetzt daraus so ein maximales Brandschenk B konstruieren. So, jetzt gucken wir uns eine Kante in diesem kritischen Graphen an, also eine kritische Kante, die nicht im Brandschenk drin ist. Und dann sind wir genau hier. Wir gucken uns eine Kante an, die zwar aus dem
26:04
kritischen Graphen sind, mit dem wir losgehen, aber nicht in diesem Brandschenk drin ist. Und dann muss sie eine dieser Möglichkeiten sein. So, der erste Spiegelstrich. Es gibt keine andere Kante im Brandschenk, die in denselben Knoten reingeht. Ist genau das
26:24
hier, diese Kante. Weil das eine Wurzel ist, es gibt keine andere Kante, die reingeht. Das, haben Sie zu Recht bemerkt, kann nicht sein. Denn wir waren ja davon ausgegangen, dass B ein gewichtsmaximales Brandschenk
26:42
ist. Die Kantengewichte sind alle positiv. Das heißt also, wenn wir diese Kante einfach hineinfügen, haben wir ein besseres Brandschenk bekommen. Widerspruch zur Annahme, dass B schon maximal ist. So, also, diese Kante kann gar nicht sein. Hier. So, dann betrachten wir die anderen Fälle. Jetzt haben wir eine Kante schon,
27:06
die reingeht. Und jetzt unterscheiden wir, ob diese Kante feasible ist. Also, wir betrachten die beiden noch übrig gebliebenen
27:22
Fälle, wo die Kante feasible ist. Das ist eine kritische Kante, ist ja im kritischen Grafen drin. Das heißt also, diese Kante, wenn die aus dem kritischen Grafen drin ist, dann ist sie mindestens so schwer wie diese Kante.
27:42
Aber, wir waren ja davon ausgegangen, dass das Brandschenk B, die weißen Kanten, möglichst viel gemeinsam haben mit dem kritischen Grafen. Das heißt, dieses Bild kann dann gar nicht sein, denn wir könnten diese Kante rauslöschen, diese Kante einfügen, sind nicht schlechter geworden und haben eine
28:01
Kante mehr gemeinsam mit dem kritischen Grafen. Das ist die Stelle, wo ich sagte, der Trick, wenn wir einen Brandschenk hernehmen, das möglichst viele Kanten gemeinsam hat mit dem von uns konstruierten kritischen Grafen, dann kommt irgendwo eine Stelle, wo wir einen Widerspruch haben. Genau hier. Dieses Bild kann nicht sein. Es kann keine feasible Kante weder so noch so aus dem selben
28:21
Grund geben, die außerhalb dieses Brandschenk liegen, denn keine feasible Kante, die zum kritischen Grafen gehört. Denn wir waren ja davon ausgegangen, dass das Brandschenk möglichst viel gemeinsam hat und wir könnten jetzt einfach diese Gemeinsamkeit erhöhen, indem wir diese feasible Kante hineinnehmen und die entsprechende andere Kante rausnehmen. So, das was
28:44
also übrig bleibt, ist dieser Fall hier und da sehen Sie schon, worauf das Ganze hinausläuft. Hier wird tatsächlich ein Zykel geschlossen, bei dem diese Kante der einzige Kante ist,
29:00
die nicht zum maximalen Brandschenk gehört. Ja, diese Kante ist die einzige, die sein kann und die hat tatsächlich, die ist tatsächlich auf einem Zykel, der alles gemeinsam hat außer dieser Kante mit diesem Brandschenk. Und damit ist das
29:24
17 bewiesen. Alles, was davor kommt, diese ganzen mathematischen, diese ganze mathematische Bürokratie, ist im Prinzip dafür da, um dieses Bild vorzubereiten und zu erklären. Habe ich jetzt hier mir erspart, habe ich Ihnen erspart, wenn Sie es mir nicht in der Prüfung ersparen wollen,
29:41
bin ich begeistert. Wie gesagt, dann sind Sie schon auf ein gutes Stück weit auf dem Weg zu 1,0. So, jetzt machen wir wieder einen Sprung hier hin. Wie kriegen wir jetzt die richtigen Zykel hin? Das hatte ich
30:04
beim letzten Mal schon kurz angesprochen. Gehen wir mal noch mal ein bisschen weiter. Hier. Die Idee an der Sache ist, was uns stört, rausschmeißen. Also nicht ganz rausschmeißen, nicht ersatzlos
30:21
rausschmeißen, sondern ersetzen durch einen einzelnen Knoten in dem Fall, shrinking, also die Zykel zu schrumpfen. Ja, wir wissen nicht, welcher, wir wissen nicht momentan, welche Kante von, welche Kante wir
30:40
auf die von diesem Zykel des kritischen Grafen rausschmeißen müssen. Genauso hier von diesem Zykel des kritischen Grafen. Das wissen wir im Allgemeinen nicht. In diesem einfachen Beispiel wissen wir es natürlich, weil die beiden Zykel so schön des Jungt sind, dass wir jeden für sich betrachten können. Aber wenn wir einen riesen Haufen von Zyklen ineinander verknotet haben, wissen wir das nicht mehr. So, jetzt schrumpfen wir die beiden,
31:01
alle die wir finden, zu einzelnen Knoten und lösen das Problem hier. Hier ist es ganz einfach zu lösen. In dem Beispiel sowieso, wir nehmen uns diese Kante und wir
31:22
nehmen uns beide Kanten, die da sind. A-Zyklusch, kritische Kanten, A-Zyklusch bedeutet maximales Branchenk. Jetzt kommt wieder die Frage, warum da eine Zwei statt einer Drei steht. Die warten wir schon beim letzten Mal. Das ist der fiese Trick an der ganzen Sache. Oder was heißt der fiese? Der geniale Trick an der ganzen Sache. Und zwar Folgendes.
31:44
Wir haben jetzt hier rechts eine Lösung. Im Allgemeinen wissen wir das aber nicht. Wir wollen ja im ursprünglichen Grafen eine Lösung haben. So, wir schrumpfen den Zykkel.
32:20
So, mal wieder mein sechser Zykkel.
32:24
Und hier gehen noch diverse Knoten rein. Also die reingehenden Knoten interessieren uns hier mehr. So, diesen Zykkel schrumpfen wir zu einem einzelnen Knoten, wo diese Kanten alle reingehen. So, kann jetzt
32:44
doppelte Kanten geben, zwei Kanten, die vom selben Knoten hier rein zeigen, das stört uns ja nicht. Wir nehmen einfach immer die schwerste. Hier kommt natürlich noch mehr rein. So, jetzt gibt es hier zwei
33:01
Möglichkeiten. Eine Möglichkeit ist, dass, wenn wir hier ein optimales Branching denken, wenn wir es schaffen, in diesem geschrumpften Grafen ein optimales Branching zu konstruieren, so wie wir das in diesem Beispiel ja sofort offensichtlich tun können. Der Graf ist zyklisch, optimales Branching ist trivial. Wenn wir es
33:23
hier schaffen, in diesem geschrumpften Grafen, wo natürlich nicht nur diese eine Zykkel drin ist, sondern alles mögliche andere noch drin ist, da ein optimales Branching drin zu basteln, dann wollen wir den Weg zurückgehen, wollen wir von hier das weiteren auf diese, auf diesen
33:44
Zykkel. Nur müssen wir da jetzt genau aufpassen, was wir dann tun. Es gibt jetzt zwei Möglichkeiten. Eine Möglichkeit ist, keine einzige dieser reingehenden Kanten gehört zu dem maximalen Branching, das wir hier konstruiert haben. Keine einzige.
34:01
Das kann passieren. Das ist eine Wurzel dann von einem Branching. Was ist dann das Beste, wenn wir jetzt den Zykkel wieder entschrumpfen? Was ist dann das Beste, was rauskommen kann? Wir gucken uns die einzelnen Kanten an und wenn das
34:24
hier zum Beispiel die leichteste ist von allen, dann nehmen wir die raus. Die sind alle drin. Was besseres können wir offensichtlich nicht machen. Ist das soweit? Klar.
34:44
Wenn, wenn kein einziger der reingehenden Kanten in diesem optimalen Matching ist, von dem wir glauben, dass wir es konstruieren können und wir übertragen das dann auf die ursprünglichen Zykkel, dann nehmen wir uns die leichteste Kante her. Ein schweres Branching
35:00
können wir dann gar nicht kriegen. Draußen außerhalb von diesem Zykkel bleibt alles gleich. Sie müssen sich also vorstellen, dass hier noch eine Million anderer Knoten drumherum sind. Durchaus mit Kanten verbunden mit diesem Zykkel. Der kann vollständig zusammenhängend sein, aber eben keine einzige der reingehenden Kanten in diesen Zykkel beziehungsweise in diesen
35:22
geschrumpften Knoten gehört zu diesem maximalen Branching, das wir jetzt hier für diesen geschrumpften Graphen konstruiert haben. Zweite Möglichkeit ist, es gibt jetzt eine solche Kante, natürlich höchstens eine. Bei einem Branching
35:41
geht ja in jeden Knoten höchstens eins rein. Ich bitte um Entschuldigung, dass ich das jetzt gleich wegwische, aber irgendwie kriege ich das sonst nicht alles auf ein Bild. Na ja gut, jetzt muss ich das irgendwie... irgendwie ist hier was verloren gegangen. So, der hier, so.
36:08
Jetzt gibt es die andere Situation, der geschrumpfte Knoten. Hier haben wir jetzt irgendwie auf magische Art und Weise unser maximales Branching konstruiert. Aber der hat eine Kante, die zu
36:27
diesem Branching gehört. Jetzt ist die Erweiterung darauf eine andere. Nämlich, wir haben jetzt wieder unseren Zykkel. Ups, nicht so
36:44
rum. Und diese Kante ist das da drüben, die zu dem maximalen Branching gehört. Jetzt, was bedeutet jetzt die Erweiterung auf den
37:02
gesamten Zykkel? Es bedeutet, dass wir diese Kanten reinnehmen und die hier nicht. So, jetzt nehmen wir mal die
37:22
Kantengewichte her, die wir da in diesem Beispiel haben. Auf dem Folien kann man die noch sehen. Ja gut, ich hoffe, man kann das noch halbwegs sehen. Diese Kantengewichte, ja, das ist alles ein bisschen eng. Wir nehmen uns neue
37:42
Kantengewichte her. Wir denken uns hier was aus. So, das hier hätte zum Beispiel Kantengewicht 3. Diese leichteste Kante hätte Kantengewicht, nennen wir es 1. Und diese hier hätte Kantengewicht beispielsweise 4. Ich
38:01
hoffe, dass das jetzt eine gut illustrative Wahl ist. Ja, das könnte doch sein. So, wenn Sie jetzt, hier haben wir dieselben Gewichte 4 und 1. Wenn Sie das jetzt miteinander vergleichen, was ist denn jetzt der Unterschied zwischen diesen beiden
38:20
Bildern? Hier haben wir eine 3 plus eine 1. Das ist natürlich gerade kein gutes Beispiel gewesen. So, hier haben wir eine 3 plus eine 1. Und hier haben wir anstelle dieser Kante mit Gewicht 3 und dieser Kante mit Gewicht 1, haben wir eine einzelne
38:41
Kante mit Gewicht 7. So, das heißt also, wenn wir hier die 3 hernehmen, dann kostet, und wenn das im Matching drin ist, wenn diese Kante dann gibt uns das einen Benefit von 3, aber Kosten von 6 gegenüber der
39:05
Situation, dass diese Kante nicht im Matching drin ist. Und genau das ist der Unterschied. Dieser Benefit muss mit diesen Kosten verrechnet werden.
39:22
Und das ist hier auch gemacht worden um diese 2, dass diese Kante nicht mehr 3 hat, sondern den Wert 2 hat. Nämlich, wenn diese Kante nicht drin ist im Maximal Matching hier, sie ist drin, das wissen wir, das sehen wir sofort, aber nehmen wir mal ein, würden das nicht sofort sehen. Falls diese
39:41
Kante von 2 nach 1 nicht drin ist, dann ist im Zügel das Beste, was wir machen können, die 4 rauszustreichen. Also die Kante mit Gewicht 4 rauszustreichen, die von Knoten 4 nach Knoten 3 geht. Wenn wir hingegen diese Kante hinzunehmen, ist das Beste, was wir tun können, die Kante von 1 nach 4 und die Kante
40:04
von 4 nach 3 hinzunehmen und die 5 nicht. Das kostet uns gegenüber dieser Variante, die Kante mit Gewicht 4 haben wir drin und die Kante mit Gewicht 5 haben wir nicht mehr drin. Das heißt, diese Kante von 2 nach 1 hinzunehmen bringt uns 3 Zähler,
40:23
kostet uns 1 Zähler und das ist genau hier hineinmodelliert, dass hier das Gewicht 2 vom Knoten wie 2 zum Knoten wie 1 ist. Das ist der ganze Trick. Dafür zu sorgen, dass diese Kante ein Gewicht hat, was reflektiert.
40:44
Je nachdem, ob diese Kante drin ist oder nicht. Wenn sie nicht drin ist, dann zählt es halt gar nichts. Wenn es drin ist, der Unterschied zwischen Kante drin oder Kante nicht drin, ist gerade diese zwei Einheiten,
41:00
drei Einheiten, weil die Kante drin ist, eine Einheit davon abgezogen, weil wir im Branching, weil wir das Branching im Zykel so anders gestalten müssen, dass wir da nochmal einen Zähler verlieren. Das ist alles. Nicht ganz, denn jetzt will ich, also hier sehen Sie das nochmal als Formel.
41:25
Habe ich keine Lust zu. Jetzt kommen wir nochmal zum Algorithmus. Jetzt gehen wir aber, wir haben das schon mal ein bisschen beim letzten Mal glaube ich betrachtet. Hier zu dem Bild. Ich will das Bild jetzt nicht weiter groß eingehen. Das können
41:40
Sie sich nochmal zu Hause anschauen im stellten Kämmerlein, um nochmal Ihr Verständnis zu überprüfen. Aber was dieses Bild insbesondere auch sagt, was das Beispiel bisher nicht gesagt hat, ist, wir können jetzt hergehen und den Zykel schrumpfen so viel wir wollen im Ausgangsgrafen. So, dann sind wir hier, aber wir haben immer noch Zykel. Wir haben jetzt neue Zykel. Also es reicht
42:01
nicht einmal Zykel zu schrumpfen und dann haben wir einen zykelfreien Grafen, sondern es kann sein, dass wir neue Zykel haben und dann müssen wir das Ganze wieder machen. Also Rekursiv wieder dasselbe. Mit dem neuen Grafen, da machen wir noch gar nichts. Wir haben erst mal hier von eins nach zwei in diesem Bild Zykel geschrumpft. Es sind immer noch
42:22
Zykel da. Also schrumpfen wir wieder Zykel. Solange bis das Ganze so einfach ist, dass wir es direkt lösen können. Also eigentlich müsste man es jetzt nochmal einen Schritt machen, weil hier Zykel drin sind. Nochmal das Ganze schrumpfen. Aber Sie sehen ja hier, was das optimale
42:42
Branching ist. Nämlich die Kante mit Gewicht 3 von W4 nach W3. Und das zurück zu übertragen. Hier ist Nummer eins. Diese Kante haben wir genommen. Jetzt expandieren wir die Zykel, die wir im zweiten Schrumpfungsschritt gemacht haben.
43:00
Kriegen das Bild. Will ich jetzt nicht weiter erklären. Das können Sie wie gesagt selber zu Hause nochmal genau ansehen, warum das so sein muss. Und wenn wir nochmal alles diesen Schritt, diesen ersten Schrumpfungsschritt rückgängig gemacht haben, mit diesen Operationen, Übertragung des Branchings, Auslehnung des Branchings auf die wieder aufgeblasenen
43:21
Zykel, dann kriegt man das raus ein maximales Branching. Das heißt, wir haben einen rekursiven Algorithmus. Ja, schrumpfe Zykel, ruf rekursiv auf. Also nein, falls kein Zykel mehr vorhanden, löst das Problem. Das ist der Rekursionsanker. Falls doch Zykel
43:42
vorhanden, schrumpfe Zykel, rufe rekursiv auf und expandiere die Zykel wieder und erweitere das expandierte Zykel. Das bricht ab, weil in jedem Schritt die Anzahl der Knoten kleiner wird. Und wir haben da endlich viele Knoten, also nach endlich vielen Schritten bricht das ab. Sie haben eine
44:01
Frage? Ok, die Frage war jetzt eine Folie früher. Eigentlich müsste man jetzt unter Punkt 3 das nochmal schrumpfen, weil wir Zykel drin haben, und dann hat man nur noch einen Punkt. Sie, wollen
44:22
wir sagen? Ah, genau, das ist der Punkt. Kritische, na gut, aber kritische Zykel haben wir trotzdem. Wir haben ja hier eine kritische Kante noch drin. Also er hat schon recht, das müsste man nochmal schrumpfen. So what? Was ist das maximale Branching auf einem
44:41
einzelnen Knoten? Dieser Knoten mit einer leeren Menge. Wir sehen das sofort hier in diesem Bild unter Punkt 3 sehen wir sofort, was die Lösung ist. Deshalb hat der Stiller das auch nicht mehr weitergeführt. Der Algorithmus ist natürlich dumm. Der Algorithmus muss
45:03
weiter agieren, muss diesen kritischen Zykel, der hier drinsteckt, der nicht ganz mehr eingezeichnet ist, muss diesen kritischen Zykel wieder schrumpfen, kommt zu einem Grafen, der nur noch einen Knoten enthält. Und dieser, da ist trivial. Und
45:20
jetzt diese allgemeine Routine der Übertragung funktioniert hier natürlich in dem Fall genauso wie in jedem komplexeren Fall. Also das ist dann schon wasserdicht. Gut, also der Algorithmus kann nicht bei Punkt 3 hier stehen bleiben. Der muss zu einem Bild 4 kommen, wo nur noch ein Knoten drin ist. Gut, das
45:42
ist der erste Moment, wo dieses Beispiel a-zyklig wird. Natürlich, wenn das Beispiel anders gelagert wird, es muss nicht immer auf einen einzelnen Knoten reduziert werden. Es kann auch durchaus auf einen etwas komplizierteren a-zykligen
46:00
So, und damit sind wir so mehr oder weniger fertig. Parallelekanten, hatte ich schon gesagt, interessiert uns nicht. Nullkanten oder negative Kanten können wir sofort, ah, das ist der Punkt noch, wo hier tatsächlich, ah, das ist noch ein interessanter
46:20
Punkt dabei. Eben, was ich eben vorgelesen habe, ein paar Folien weiter ist, negative Kanten oder Kanten mit Gewicht 0 können natürlich eliminiert werden. Die werden wir nie in maximales Branching machen. Damit, mit diesem Schritt, Elimination der negativen Kanten, haben wir sofort hier in Bild 3 einen a-zykligen Graphen. Wenn wir das machen, wenn wir das nicht machen,
46:42
wenn wir nicht negative Kanten eliminieren, wenn der Algorithmus so dumm implementiert ist, dass er das nicht tut, dann würde man hier noch einen vierten Schritt, also noch einen dritten Schrumpfungsschritt brauchen, um zu einem vierten Zustand zu kommen. So, ja, die
47:00
Kanten speichern wir uns natürlich und diese Anwendung, das haben wir vorher schon ausgelassen, das lassen wir jetzt auch aus. So, Literatur, wenn Sie wollen, haben Sie hier genug zu lesen und damit sind wir mit diesem Kapitel durch und kommen zum nächsten
47:20
Kapitel. Oh, schon wieder was, was wir mal kennen aus der kürzeste Wege, aber keine Sorge, da gehen wir dann schnell durch. Was das kürzeste Wegeprobleme ist, kennen Sie, ich werde jetzt viele Kanten hier mehr oder weniger schnell durch gehen, weil Sie das Ganze aus der GDE2 kennen. Sie haben einen
47:41
gerichteten Graphen, Sie haben Kantengewichte, Sie haben Knoten S und Knoten T und Sie wollen kürzesten Weg von S nach D. Kürzester Weg heißt, die Summe der Kantengewichte ist minimal. Natürlich müssen wir davon ausgehen, dass der Graph so weit zusammenhängt, dass es mindestens einen Weg gibt von S nach D, sonst können wir auch nicht von dem kürzesten Weg reden.
48:03
Gut, diese Folie wieder. Was passiert, wenn man alle möglichen Fahne enumeriert? Sehen Sie bei 100 Knoten schon, dass das ein bisschen ärgerlich wird. Wollen wir hier nicht weiter besprechen. Matroide lassen wir hier aus. Ich habe darüber lange mit
48:21
Herrn Stille gesprochen. Es war richtig, dass das Ganze hier ein Matroid ist, aber ich glaube, das ist eher verwirrend, als dass es hier Erkenntnisgewinn bringt. So, ein Punkt dabei, machen wir mal alles voll. So, Kanten haben alle Gewicht eins.
48:41
Spezialfall, alle Kanten haben Länge eins. Das heißt, der kürzeste Fahrt ist derjenige mit der geringsten Anzahl Kanten. So, wenn Sie jetzt nicht so genau hinschauen, wenn Sie so ein bisschen die Augen zusammenkneifen, dann wird Ihnen dieses Bild wahrscheinlich bekannt vorkommen. Nämlich, das wird sehr, ja genau, Augen zukneifen. Man wird langsam
49:00
müde, nicht? Dann wird Ihnen dieses Bild bekannt vorkommen. Das sieht nämlich sehr, sehr ähnlich zu extra und das ist auch überhaupt keine, kein Zufall. Wenn, was diese Folie aussagt, ist letztendlich bei Kantenlängegewicht eins, Kantenlänge eins, brauchen wir gar keine Parity
49:22
Q. Was uns ausreicht, ist eine, eine normale FIFO Q hinten rein, vorne raus. Warum? Sie erinnern sich, das hatten wir am Anfang dieses Semesters mal festgestellt. Wenn Sie Breitensuche machen, also, also in Ihrer Suche eine
49:40
FIFO Q verwenden, ich meine, das ist genau der Unterschied. Tiefensuche, Breitensuche, Dijkstra, LIFO Q, FIFO Q, Parity Q. Das ist exakt der Unterschied. Alles andere ist bis auf die exakten Berechnungsformeln
50:01
identisch. So, wir haben schon mal gesehen, wenn wir Breitensuche machen und wir gucken uns die Q an, die ist hier auch mit Q benannt, nicht? Ja, so, hier
50:23
ist vorne, hier ist hinten, vorne, vorne holen wir raus, hinten fügen wir ein, damit es, damit es keine Missverständnisse gibt, habe ich das nochmal hingeschrieben. So, und dann gibt es zu jedem Zeitpunkt, haben alle Elemente hier eine Distanz K von
50:47
S und von irgendeinem Punkt aus haben sie alle Distanz K plus eins. Das Bild hatten wir schon mal, als wir Breitensuche besprochen haben.
51:03
Zuerst, es gibt ein K, sodass erst die ersten Elemente alle K entfernt sind vom Startnoten und alle weiteren Elemente sind K plus eins entfernt. Natürlich kann diese Teilmenge mit K bzw. diese Teilmenge mit K plus eins auch mal leer sein momentan,
51:21
aber so wie dann der nächste Knoten dazukommt, haben wir wieder diese Zweiteilung. Das bedeutet also, das fungiert in dem Fall als Priority Q, weil wir wissen, es kann ja nur zwei verschiedene Distanzen geben, K und K plus eins und die mit K kommen als erstes. Das ist die Aussage dieser
51:41
Folie, die zweite Aussage ist, das Ganze hat auch noch einen Namen, nämlich Algorithmus von Moore. So, negative Zyklen ist mit Sicherheit in der GDG 2 betrachtet worden, können wir jetzt ganz schnell durchgehen. Ja, was passiert, wenn Sie negativen Zyklus haben, irgendwo auf dem Weg von S nach
52:00
T? Sie gehen rein einmal, haben Länge gespart, gehen so nochmal durch, haben wieder Länge gespart, gehen nochmal durch und nochmal durch und nochmal durch. Es gibt keinen kürzesten Weg, weil Sie können beliebig auf durchgehen und dann mit dem Weg immer kürzer machen. Jetzt könnte man sagen, okay, ist natürlich nicht das, was wir wollen. Wir wollen, falls es negative
52:22
Zyklen im Grafen gibt, wollen wir einen Pfad konstruieren, der eben zykelfrei ist. Von S nach T das Problem an der Sache ist, diese Problemstellung ist NP schwer. In Anwesenheit von negativen Zyklen einen kürzesten zykelfreien Weg zu finden von S nach T ist NP schwer. Hatte ich schon mal gesagt,
52:40
was das bedeutet? Pragmatisch bedeutet das für jeden Algorithmus, den man sich überhaupt nur ausdenken könnte. Gibt es, kann man Beispiele konstruieren von moderater Größe, bei denen dieser Algorithmus wesentlich länger braucht, als unser Universum ihm zur Verfügung stellt. So, der letzte Punkt hier.
53:04
Hamiltonische Pfade. Ein Hamiltonischer Pfad von S nach T im Grafen ist einer, der alle Knoten genau einmal durchläuft. Und wenn Sie jetzt alle Kantenlängen zu minus eins setzen im Grafen, dann sind die Stp-Pfade der Länge eins minus n
53:21
genau die, die alle Knoten, die die genau entsprechend viele n minus eins Kanten enthalten, also n Knoten enthalten, alle Knoten enthalten. Ist noch die Aussage. Hamiltonischer Pfad zu berechnen ist NP schwer. Im Allgemeinen, also herauszufinden, ob es überhaupt einen
53:41
solchen Grafen gibt, einen solchen Pfad gibt in einem Grafen, ist NP schwer. Und wenn man mit, mit diesen kürzesten Wegen tatsächlich, mit diesem kürzesten Wegeproblem tatsächlich das Hamiltonische Pfadproblem lösen kann, dann kann dieses kürzeste Wegeproblem nicht leichter sein. So, nur da extra, das
54:00
wissen Sie, keine negativen Kantenlängen. Für die anderen Algorithmen gilt das nicht. Ungerichtete Grafen, hatte ich irgendwann glaube ich auch schon mal erwähnt. Ungerichtete Grafen können Sie prinzipiell natürlich ersetzen durch gerichtete K, ungerichtete Kanten durch gerichtete Kanten. Eine ungerichtete
54:30
Kante mit Gewicht C können Sie natürlich durch sowas ersetzen. Beide haben Gewicht C. Außer das Gewicht C ist negativ.
54:41
Dann haben Sie nämlich plötzlich hier einen negativen Zykel drin. Dann geht das Ganze natürlich nicht. Aber wenn das Gewicht nicht negativ, wenn alle Gewichte nicht negativ ist, geht die Konstruktion natürlich gerade. Das ist das, was hier steht. Funktioniert nicht bei negativen Kantenlängen. Gut, das ist eine Vorausschau,
55:01
die wir uns nicht weiter betrachten wollen. Parallele Kanten ist in kürzesten Wegen Problem sowieso keine Sache. Wenn Sie zwei Parallele Kanten haben, die unterschiedliches Gewicht haben, C1 und C2, dann schmeißen Sie die Kante raus, die höheres Gewicht hat. Die bringt Ihnen ja gar nichts.
55:20
So, Sie erinnern sich bei Minimum Spanning Tree haben wir das Ganze ein bisschen abstracter gesehen. Das werden wir jetzt hier auch sehen. Unterscheidungen in Algorithmen, die Label Setting und Label Correcting heißen. Da kommen wir, Sie erinnern sich an die Distance Labels in der GDE2, die man so setzt.
55:42
äh wenn Sie vielleicht so ein bisschen noch Erinnerung haben an die Algorithmen, die da in der GDE2 betrachtet worden sind, Dykstra, Bellman-Ford, Floyd Warschall vielleicht, dann waren diese Distanz Labels für jeden Knoten immer obere Schranken. Es waren Werte, die niemals kleiner waren
56:02
als die echten Distanz Werte, weil sie ja schrittweise immer runtergesetzt wurden. Sie haben sich dann immer nur in die Richtung abwärts verändert. Und deshalb ist das notwendig, dass sie immer äh dass sie immer dass sie niemals kleiner sein dürfen,
56:22
diese Werte niemals kleiner sein dürfen als die echten Distanzen. So Label Setting, das ist zum Beispiel Dykstra, wird in jedem Schritt ein Label permanent gesetzt und dann wird es nie wieder geändert. Label Correcting, das wäre beispielsweise Bellman-Ford und Floyd Warschall. Wenn Sie sich nochmal erinnern an Bellman-Ford oder Floyd Warschall,
56:42
kein einziges Label, keine einzige Distanz, die Sie da mal zwischendurch berechnen, ist für Dauer, sondern erst im allerletzten Schritt, im allerletzten Durchlauf durch die übergeordnete Schleife, werden sämtliche Distanz Werte endgültig gesetzt. Vorher sind alle temporär.
57:02
Das meint Label Correcting. Label Setting funktioniert nur mit nicht negativen Kantenlängen. Da sehen wir gleich nochmal ein Beispiel dazu. So, was in der GDE 2 noch nicht so genau betrachtet worden ist, zumindest nicht bei mir. Ich weiß nicht,
57:21
wie es bei Herrn Gallenbacher oder Herrn Buchmann war. Wenn Sie sich die ganzen kürzesten Wege anschauen, die da von einem Startknoten aus zu allen anderen berechnet worden sind, wie bei Dykstra oder
57:42
bei All Pairs eben, wenn Sie sich alle anschauen, die von einem Knoten zu allen anderen gehen. Das ist wie üblich mein Graph. Hier ist irgendwo der Startknoten, den ich zweckmäßigerweise in die Mitte zeichne. Und Dykstra berechnet
58:01
zum Beispiel Dykstra, die anderen auch, berechnet kürzeste Wege. Aber, was er da tut, diese Wege bilden einen Baum. Genau gesagt eine Aborressenz, weil es ja ein gerichteter Baum ist.
58:22
Warum tut er das? Also zunächst mal muss man sich ja klar machen, was, Sie erinnern sich, was merkt man sich bei so einem Algorithmus eigentlich, um die Pfade hinterher zu rekonstruieren? Man merkt sich für jeden Knoten die reingehende letzte Kante dieses kürzesten Weges, nicht? Und damit haben wir schon
58:40
eine Aborressenz, die eine einzige Wurzel hat, nämlich S. Ja, also es ergibt sich automatisch eine solche Aborressenz, weil wir was anderes gar nicht gespeichert haben. Man kann natürlich immer so eine Aborressenz aufbauen, weil, wenn Sie sich vorstellen,
59:04
der kürzeste Weg zu diesem Knoten hier geht so lang und der kürzeste Weg zu diesem Knoten hier geht so lang, dann können Sie natürlich das hier raus schmeißen und stattdessen hier lang gehen, denn diese beiden Wege sind offensichtlich gleich lang,
59:22
von hier nach hier und von hier nach hier. Was hier steht, ist etwas was, denke ich, sehr, sehr schnell einleuchtet.
01:00:00
wenn sie den kürzesten fahrt haben von irgendeinem knoten zu irgendeinem andern knoten und sie betrachten sich so ein teil fahrt dazwischen so so ein intervall sozusagen zwischen zwei knoten ja da geht es natürlich auch so lang dann ist das ein das ist von s nach t
01:00:20
das ist von v nach w dann ist dieses stück natürlich ein kürzester vw fahrt denn gäbe es einen kürzeren irgendwo anders lang dann wäre natürlich das hier auch ein kürzerer st fahrt widerspruch jeder teil eines kürzesten weges ist ein kürzester weg genau das steht hier
01:00:41
und das kann man natürlich auch noch beweisen ja jetzt kommt ein die folgende einsicht dazu die sich daraus ergibt deshalb ist es ein korrelar
01:01:02
mal das bild noch mal vielleicht ein bisschen neu so wir malen jetzt noch mal das ist ein kürzester fahrt von s nach t und wir haben hier eine kante drauf
01:01:25
von u nach v und wir interessieren uns für die delta werte und was dieses korrelar sagt ist dass die delta werte die distanz werte sehr sehr strikt zueinander in beziehung stehen
01:01:42
nehme ich dass die distanz nach v exakt gleich ist der distanz von s nach u plus dem kantenlänge von u nach v logisch weil
01:02:03
die distanz von von s nach v kann natürlich nicht größer sein weil das ist ja das ist ja ein weg dann kann der kürzeste weg nicht länger sein klar die distanz von s nach v kann aber auch nicht kürzer sein denn
01:02:21
Moment halt wir muss ich jetzt beweisen wenn das ein kürzester weg ist dann ist das auch ein kürzester weg von s nach v Und dann ist das auch ein kürzester weg von s nach u ganz einfach also diese länge kürzester weg von s nach u ist gerade das hier
01:02:42
diese länge des dieses teilweges ist kürzeste länge von s nach v ist gerade das hier und der unterschied zwischen beine sind gerade die kosten dieser kante so und im allgemeinen das will ich noch mal Vielleicht neu zeichnen mit einem etwas anderen bild
01:03:22
allgemein gilt für jede kante Uv die zeichne ich mal so hier ist unser s wir haben jetzt hier zwei kürzeste wege irgendwo gehen die auseinander und
01:03:43
und die aussage dieses Corollars nummer 6 des zweiten Corollars auf dieser folie ist jetzt dass dieses delta sv der abstand die distanz von s nach v Nicht kleiner sein kann als der abstand von s nach u plus
01:04:03
Plus dem gewicht von u nach v warum ganz einfach Der kürzeste weg von s nach u plus dieser kante ist ein möglicher weg hier rein Ja, das ist die länge eines möglichen weges nach v Die länge des kürzesten weges nach v kann nicht länger sein als die länge irgendeines weges nach v
01:04:27
so warum machen wir das weil wir das jetzt plötzlich Weil wir da jetzt plötzlich auf die idee kommen eine operation durchzuführen im laufe
01:04:46
des algoritmos Die das was sie bei daigster gesehen haben und das was sie bei bellman fort und so weiter gesehen haben alles vereinheitlicht so dass diese ganzen operationen diese ganzen algorithmen Spezialfälle eines allgemeinen schemas sind so wie wir es bei bellman costco auch gesehen haben das ist natürlich etwas anders so
01:05:05
die logik ist die Wir arbeiten wir haben natürlich distanz labels im grafen das sind jetzt irgendwelche werte Und wann immer wir feststellen Dass es eine kante gibt
01:05:21
Bei der eine kante u v bei der die distanz von v der aktuelle distanz wird jetzt sind ja noch nicht die echten distanz wird Die aktuellen werte die hoffentlich irgendwann am ende die echten distanz werte werden wann immer dieser distanz wird größer ist Von v größer ist als distanz wird von u plus gewicht der kante wird das entsprechend
01:05:42
Die das der distanz wird runtergesetzt und das ist immer die die reingehende kante wird entsprechend abgedatet So was steht hier was hier steht ist Im distanz wert von v steht die länge eines pfades
01:06:01
Links rechts steht auch die länge eines pfades von s nach v also links steht die länge eines pfades von s nach v rechts steht die länge eines pfades von s nach v und die rechte länge ist kürzer als die linke länge die was gerade für v gespeichert wird Also Setzen wir doch die distanz von v
01:06:21
runter auf die länge des pfades der rechts steht nicht mehr die länge des pfades links steht wir haben einen neuen pfad gefunden der kürzer ist als der pfad vorher Der pfad wird dann hier mit dem pi auch aktualisiert genau und letztendlich ist es genau das was in diesen algorithmen in allen gemacht wird nicht so schön extrahiert
01:06:45
Initialisierung ist die distanzen Ich habe jetzt immer deltas genommen und hier auf den folien steht ein d, aber ich glaube diesen kleinen abstraktionssprung kriegen wir hin Distanzen sind alle plus und plus unendlich warum weil wir gesagt haben
01:07:02
Die distanzen soll niemals kleiner sein als die distanzwerte die wir speichern so niemals kleiner sein als die distanzen Die echten distanzen und da sind wir immer auf der sicheren seite wenn wir mit unendlich anfangen Und natürlich haben wir da noch keinen baum konstruiert das heißt also die p-werte sind alle void oder java 0
01:07:27
Ja gut diese das nehmen sie zur kenntnis die letzte zeile warum nicht zu diskutieren So die aussage die hier steht ist
01:07:41
wenn wir mit Mit unendlich großen oder mit mit mit gewichten anfangen mit kantenlängen anfangen Mit mit distanzwerten d anfangen die größer als die echten distanzwerte sind nicht kleiner jedenfalls Dann können wir so oft korrigieren korrekt anwenden wie wir wollen diese kleine korrektur
01:08:01
Wir gehen offensichtlich niemals unter die echten werte weil wir immer den den wert immer korrigieren auf die länge eines anderen fahres und In dem moment wenn wir es erreicht haben Wird natürlich nichts mehr passieren wir wissen das natürlich nicht ob wir es erreicht haben oder nicht
01:08:21
Weil wir nicht wissen ob nicht vielleicht doch noch mal irgendwann eine neue korrektur kommt aber In dem moment wenn wir das erreicht haben ob wir das wissen oder nicht passiert nichts mehr mit diesem knoten So den beweist glaube ich brauchen wir da nicht das hat sich jetzt mit dem was ich gesagt habe schon soweit
01:08:42
geklärt gut Das Ja gut diese beobachtung Wenn wir der letzten wenn wir den letzten knoten haben auf einem kürzesten v-fahrt
01:09:06
Und wir werden wir werden auf die kante von u nach v Das korrekt an ich denke dass das ist auch sofort einsichtig
01:09:23
Gut Was diese folie jetzt wenn wir sie ganz fertig haben sagt ist wir Haben keine negativen zyklen erst mal im grafen wir werden später nochmal zu negativen zyklen kommen wir haben erst mal keine negativen zyklen im grafen Und die von s aus erreichbar sind natürlich in irgendwelchen bereichen die von
01:09:44
s aus gar nicht erreichbar sind kann natürlich negative zeige sein soviel sie wollen So und wir haben die kantengewichte entsprechend initialisiert Und die und die reihen gehen in den kanten und die behauptung ist wir machen Also die behauptung ist ein bisschen schärfer als das hier formuliert ist nicht vor
01:10:05
Any sequenz sondern für eine maximale sequenz wir machen so oft korrekt wie es geht Egal aber in welcher reihenfolge deshalb vor any sequenz so oft es geht wenn so wenn wir korrekt an das heißt so oft wir da noch Gehen wir nochmal zurück
01:10:21
Hier so oft wir noch diese situation haben ein dv größer du plus kostenwert von der kante uv Solange wir noch diese situationen haben Wenn wir die korrektur schritt an und die behauptung ist egal in welcher reihenfolge wir das machen Was am ende rauskommt ist
01:10:41
eine aber essence Rooted at s also mit einziger wurzel s Per definition Haben wir natürlich immer nur eine reingehende kante das ist erst mal ein wichtiger punkt
01:11:06
Eine reingehende kante bei jedem knoten maximal eine ja Sie erinnern sich daran was was diese bezeichnung bedeutet das sind die reingehenden kanten von v
01:11:23
Das ganze ist art zyklisch Denn beweist durch widerspruch wir nehmen an es gibt einen zykl Und dieser genau dieser zykl
01:11:43
Kann nur Wie ist jetzt das argument Gut dieser zykl ist natürlich durch korrekt operationen entstanden
01:12:00
Ja genau genau der das argument ist jetzt folgendes angenommen Es entsteht dadurch ein zykl
01:12:35
Angenommen es entsteht dadurch ein zykl Das sind die knoten v1 v2 und so weiter bis vk
01:12:47
Dann wissen wir folgendes d V2 ist gleich D V1 plus
01:13:01
Gewicht von dem von v1 bis v2 Kann man das noch sehen Ich glaube ich muss da ein bisschen das kann man noch sehen
01:13:29
Dv3 ist gleich d v2 plus kostenwert
01:13:40
Und so weiter bis d V1 ist gleich d vk hier schließt sich der zykl plus kostenwert So wenn ich das jetzt wenn ich jetzt sämtliche gleichung aufsummiere die linken seiten aufsummieren und die rechten seiten aufsummieren
01:14:01
Dann Komme ich auf Hier auf null und hier Auf die länge des zykls ist aber nicht genau das was hier steht Hier wird behauptet dass es ein negativer zykl sein muss
01:14:24
Können wir sie mir so weit folgen gar nicht ne was wir gesehen haben ist doch durch die korrektur die beiden warten sie mal Was ist das argument jetzt hier an dieser stelle wenn wir einen zykl haben
01:14:41
in dieser aber was im nicht aber es sind in diesem Grafen den wir konstruieren der eigentlich die kürzesten die aber sonst der kürzesten wege werden soll wenn wir einen zykl haben Haben sie eine idee das habe ich jetzt nicht verstanden ok also hier kommen wir irgendwie von s wahrscheinlich
01:15:17
Ja ach so
01:15:28
Genau ok gut danke warum halten sie nicht die vorlesung Ich werde dafür bezahlt ja ja ok die antworte habe ich verdient
01:15:42
So genau das ist das das ist das argument das ist sicherlich ein einsichtliches argument an dieser stelle Wenn wir hier den zykl schließen hier Dann ist diese länge Hier drüber kleiner als diese länge also diese länge einmal rum ist kleiner als die länge direkt nach v1
01:16:04
Und damit muss der zykl negativ sein ich glaube es ist noch kein exakter mathematischer beweis aber ich denke es ist es einsichtig So was bleibt noch übrig
01:16:25
Also ich gehe jetzt immer so ein bisschen salopp vor wenn ich sage das ist noch kein mathematischer beweis eigentlich bin ich der meinung Das natürlich oder was heißt ich bin natürlich muss alles exakt mathematisch bewiesen werden das heißt jetzt aber nicht Dass wir uns gemeinsam mit jedem dieser exakten mathematischen beweise herum quälen müssen
01:16:43
sondern Sie tun das was sie auch vermutlich tun wenn sie mit einem finanzberater zu tun haben sie glauben ihm Mit einem versicherungsvertreter und so weiter sie glauben ihm genauso glauben sie mir ich meine die konsequenzen wenn sie mir hier glauben ist
01:17:00
Dass sie eine gute note kriegen die konsequenzen wenn sie mit einem versicherungsvertreter glauben sind deutlich schlechter Das war jetzt alles natürlich nicht wissenschaftlich Aber es war lebensnah Das soll ich ihnen jetzt beweisen Dass die konsequenzen wenn es im versicherungsvertreter glauben schlecht potenziell schlechter sind als wenn sie mir glauben
01:17:27
dass sie mit einem versicherungsvertreter glauben Okay, ich glaube ich ziehe das ganze wieder zurück So es wird kein zykel gebildet und nach s Es kann man ja eigentlich von vornherein sowieso ausschließen beziehungsweise es wird von vornherein ausgeschlossen weil
01:17:42
Kleiner als null kann es dann ja nicht werden und null ist es von anfang an initialisiert also kann bei s nie was passieren Und damit ist es eine aber resenz Jetzt fehlt aber hier noch ein punkt nicht in dem beweis ja Ach so warum
01:18:02
Warum allgemein diese p-werte sämtliche p-werte für alle knoten die von s aus erreichbar sind am ende null nicht null sind nicht das fehlt jetzt noch in diesem beweis Oder fehlt ihnen das nicht Wieso fehlt ihnen das nicht am anfang sind ja alle null was macht sie so sicher dass am ende alle
01:18:22
knoten V die von s aus erreichbar sind einen nicht null wert p von v haben Genau also ich würde das glaube ich so begründen so formulieren
01:18:45
Ja wie würde ich das formulieren also es gibt knoten von s beginnens wo er hingekommen ist die haben p-wert und gleich null Und Dann gibt es Dann gibt es irgendwelche knoten die erreichbar sind von s aber wo er nicht hingekommen ist
01:19:03
So dann gibt es aber mit sozusagen einen ersten knoten Wo er nicht hingekommen ist Auf dem weg zu diesem ja wir gehen wir gehen davon aus es gibt oder wir sagen es gibt jetzt einen knoten zum beweis der Videospruchsannahme es gibt einen knoten da irgendwo draußen in unendlichen weiten
01:19:22
Der nicht der zwar von s aus erreichbar ist aber Nicht erreicht worden ist dann gibt es einen ersten knoten hier der nicht erreicht worden ist und hier bei dieser kante haben wir Einen widerspruch denn hier haben wir noch unendlich und hier haben wir einen endlichen wert Das wäre noch hätte noch korrigiert werden müssen widerspruch also ist es alles erreicht
01:19:44
Was erreichbar ist so da extra Kennen sie Weiter behauptung ist
01:20:02
Bei termination des extra algoritmus Kommen die richtigen werte raus So ja nichts nichts zu lachen der der algorithmus terminiert Weil ja in jedem knoten in jeder iteration ein knoten permanent gelabelt wird das heißt anzahm knoten minus eins
01:20:23
Für s haben wir keine iteration für die gilt für den startknoten für jeden andern haben wir eine iteration nach n minus eins Terminierte algorithmus und wir haben zu zeigen Dass das ganze hier Dann die richtigen werte habt darf ich fragen wer von ihnen
01:20:42
Hat hat nicht bei mir die gediet so gehört okay Bei Herrn Gallenbacher ist es dort bewiesen worden dass der extra funktioniert bitte Ich verstehe nicht Ach so bei Herrn Haupt der hat es bewiesen bitte
01:21:04
Ja, aber nicht alle von ihnen. Ja sie waren tutor sie wissen das natürlich Aber nicht alle wer von ihnen hat noch nie einen beweis gesehen für ein algorithmus von da extra bitte
01:21:21
Wollen sie einen sehen Sie wollen einen sehen bitte Umfang des beweises ich versuche es in den letzten zehn minuten okay das ist ein deal Zehn minuten plus tafelwischzeit
01:21:43
So ich mache so wie in meiner gde 2 sorry aber so finde ich das ein bisschen angenehmer Als als die typischen art und weise wissen wie es in der trattur und so auch in den folien hier gemacht wird und zwar Leider habe ich jetzt nicht die richtigen farben da
01:22:03
Da gibt es zwar in grün aber wenn ich damit auf der tafel rum male mit dem edding dann gibt es ärger So das ist wieder mal mein graf so Und das ist es Zu jedem zeitpunkt Gibt es eine zweiteilung in da extra eine zweiteilung der knoten
01:22:26
Also in mündlichen prüfungen habe ich dann schon öfters mal gefragt spitz das zauberwort mündliche prüfung Stellen sich vor sie haben eine millionen knoten und der algorithmus hat jetzt 300.000 iterationen hinter sich beschreiben sie doch mal
01:22:41
Was was wir jetzt über den den aktuellen zustand sämtlicher gespeichert der werte wissen wer den algorithmus verstanden hat sollte in der lage sein das zu beantworten nicht so Die hier drin die sind schon fertig da haben wir schon die aber es sind die haben schon die richtigen werte
01:23:05
Die da draußen Haben folgende folgende de werte folgen ist tanz werte Die die haben den als distanz aktuellen ist tanz wert den kürzesten weg die länger eines kürzesten weges
01:23:23
von s Dahin und alle anderen knoten gehören hier zu der fertiggestellten menge Das heißt also ein knoten der direkt anschließend kommt hier an diesem bereich Der hat dann einen endlichen wert nämlich die länge eines kürzesten weges von hier durch und den knoten der weiter weg ist der keine
01:23:43
direkte kante von hier hat Der hat weiterhin den wert unendlich was ja auch stimmt die länge eines kürzesten weges der der nur kanten In diesem inneren bereich enthält es gibt keinen solchen Die menge die menge ist leer die menge an solchen wege ist leer und das minimum über die leere menge ist unendlich
01:24:04
Ja es sind das Bewusst wo mache ich das hin minimum leere menge Ist immer plus unendlich Maximum der leeren menge ist minus unendlich das ist so in der mathematik gesetzt worden aber das funktioniert immer auch
01:24:23
So Was jetzt passiert ist Das ist die invariante ja dass die invariante die knoten haben die richtigen werte und die knoten haben Kürzeste weglängen von von wegen die nur innere knoten enthalten bis auf den letzten knoten natürlich
01:24:45
So was passiert jetzt in da extra wir nehmen uns jetzt einen knoten her Den nehmen wir zu die innere mit zu der innere menge hinzu sozusagen wir beulen diese innere menge aus wenn wir sie so wollen Und
01:25:01
updaten Die die Längen werte diese sonst werte der knoten die von diesem Von diesem knoten aus erreichbar sind das ist das das eine visualisierung von dem was da extra macht vielleicht nicht schönste visualisierung aber es ist eine so Welcher knoten ist das hier wir nehmen den mit dem kürzesten distanz wert nach dieser logik
01:25:26
warum Was wir beweisen müssen ist dass die invariante weiterhin gilt dass dieser knoten Dessen distanz werte rühren wir ja gar nicht in dem moment mehr an Sondern diese distanz werte die ändern wir jetzt Diesen bleiben wir wieder ist das heißt wir müssen jetzt beweisen wenn wir hier den kürzesten den kleinsten distanz wert hernehmen
01:25:46
Dann ist das tatsächlich dann erfüllt er tatsächlich die invariante für die inneren knoten das ist ein kürzester weg Das ist die kürzeste weglänge die distanz wird von hier Warum ist das so
01:26:01
Annahme nein Muss man das ganze noch mal neu ein bisschen zeichnen
01:26:27
So ich zeichne wieder meinen grafen Ich zeichne Den inneren bereich jetzt mal mit weniger detail und das ist der knoten den wir hinzunehmen
01:26:40
Warum ist diese fahrt linke tatsächlich? Die wir jetzt haben die kürzeste weg linge so dass wir also mit dieser distanz wert Diesen knoten zur inneren menge hinzunehmen können angenommen es wäre nicht der kürzeste weg die längern des kürzesten wege dann gäbe es also ups
01:27:00
Einen kürzeren weg hierher irgendwo anders lang der könnte zum beispiel so so so laufen hier hinten rum ja Wenn das nicht der kürzeste weg ist Gibt es einen kürzeren Irgendwie läuft der kann kaut und rühm laufen ist uns egal wichtig ist es gibt diese kante hier
01:27:24
mit diesem knoten hier Die interessiert uns die allererste mit dem wir den inneren bereich verlassen so Der hier hat aber momentan kürzeren distanz wert oder höchsten zu hohen kleinen distanz wert nicht größeren distanz wert oder
01:27:41
höchsten zu großen distanz wert wie der hier Ja der ist weiter weg als der Wenn das hier Dann insgesamt kürzer werden soll und der ist weiter weg dann dann ist der rest hier negativ Widerspruch wir haben keine negativen kanten und deshalb auch keine negativen fadlängen
01:28:02
So einfach ist die welt wenn man einfach mal ein bisschen zeichnet und nicht Wir hätten natürlich jetzt auch hier flupp flupp flupp flupp da sehen sie ungefähr dasselbe bild noch mal flupp geht noch weiter Flupp flupp flupp flupp flupp flupp flupp Und damit ist der beweis zu ende nicht halt halt halt
01:28:25
Beweis zu ende nicht vorlesung zu ende Gut also ist es was anschaulich ist ja Beispiel von drei extra brauche ich hoffentlich in dieser runde hier nicht durchzugehen oder Nein das haben sie egal bei wem sie das gehört haben das haben sie mit sicherheit
01:28:47
Verinnerlicht Laufzeit von da extra wie sieht wie sieht die laufzeit von da extra aus die einfache laufzeit von da extra Ups vielleicht mal wieder Die einfache laufzeit von da extra ist
01:29:02
In jeder sie haben o von n iterationen n minus 1 iteration um genau zu sein da kommt der eine faktor von dem n Quadrat her und das was sie in einem Schritt machen was machen sie in einem Schritt Wenn sie wenn sie es ganz dämlich anstellen ohne particles und so weiter wirklich ganz primitiv machen was machen sie in einer iteration
01:29:23
sie gehen alle Knoten die noch nicht permanent sind die noch nicht in einer menge durch sind und nehmen sich den knoten mit geringsten Distanz o von n und von diesem knoten aus täten sie alles was von da aus auch erreichbar ist auch ab o von n O von n plus o von n ist o von n in jeder iteration kostet o von n o von n iteration gibt insgesamt n quadrat
01:29:49
so das ist das Wenn man es ganz primitiv macht Bei wirklich dichten grafen die sehr nah an dem
01:30:01
An der an am vollständigen grafen sind wird man auch nichts besseres hinkriegen weil man muss ja dann tatsächlich in jeden Knoten omega von n viele Andere knoten betrachten zum update wenn der kraftdicht ist so fast alle knoten hat so Prerequis haben sie gesehen in der gd2 nehme ich an und der einsatz für da extra
01:30:24
Brauchen wir jetzt hier nicht weiter durchzugehen das setzen wir voraus dass sie das alles gesehen haben Und wie man mit einer barrage q da extra formuliert haben sie auch gesehen wollen wir hier nicht zu machen binary hieb also da als pradeq struktur haben sie gesehen
01:30:43
Egal bei wem sie die gd2 gesehen haben gehört haben D hieb lassen wir aus das ist eine kleine variation die nicht weiter wichtig ist viel bonacci hieb ist eine größere variation die nicht weiter wichtig ist Wenn man wenn man nicht so viel respekt vor den leuten hätte wie ich habe
01:31:03
würde man sagen sowas wie viel über nachschieben wird schon langsam pervers Da jetzt implementation ist noch interessant ganz ganz kurz ganz witzige sache Und zwar ist die idee es geht um die party q
01:31:31
Die zeit ist um machen wir das nächste mal wieder ok bis nächstes mal