Network Flows III

Video thumbnail (Frame 0) Video thumbnail (Frame 8336) Video thumbnail (Frame 17826) Video thumbnail (Frame 29169) Video thumbnail (Frame 31114) Video thumbnail (Frame 34861) Video thumbnail (Frame 49211) Video thumbnail (Frame 62584) Video thumbnail (Frame 65322) Video thumbnail (Frame 68272) Video thumbnail (Frame 80774) Video thumbnail (Frame 86637) Video thumbnail (Frame 90796) Video thumbnail (Frame 95532) Video thumbnail (Frame 97579) Video thumbnail (Frame 110677) Video thumbnail (Frame 117201) Video thumbnail (Frame 119761) Video thumbnail (Frame 133531) Video thumbnail (Frame 135912)
Video in TIB AV-Portal: Network Flows III

Formal Metadata

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

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Loading...
Kante Mass flow rate Desire path Summation Kapazität <Mathematik> Weight Flux
Kante Mass flow rate Repetition Direction (geometry) Moment (mathematics) Set (mathematics) Vapor Range (statistics) Set (mathematics) Kapazität <Mathematik> Subset Connected space Partition (number theory) Subset Differenz <Mathematik> Film editing Partition of a set Spherical cap Summation Flux
Mass flow rate Length Direction (geometry) Feasibility study Kapazität <Mathematik> Set (mathematics) Film editing Grand Unified Theory Logic Spherical cap Ecke Flux Directed graph Proof theory
Mass flow rate Feasibility study Total S.A. Kapazität <Mathematik> Incidence algebra Equation Position Film editing Spherical cap Summation Flux Directed graph Derived set (mathematics) Proof theory
Kante Greatest element Mass flow rate Decision tree learning Graph (mathematics) Direction (geometry) Desire path Set (mathematics) Kapazität <Mathematik> Inequality (mathematics) Total S.A. Position Residual (numerical analysis) Film editing Spherical cap Spielraum <Wahrscheinlichkeitstheorie> Summation Flux Directed graph Proof theory
Residual (numerical analysis) Mass flow rate Positional notation Eigenvalues and eigenvectors Graph (mathematics) Maxima and minima Kapazität <Mathematik> Total S.A. Professional network service Arc (geometry) Maß <Mathematik>
Kante Greatest element Vapor barrier Graph (mathematics) Maxima and minima Propositional formula Kapazität <Mathematik> Equivalence relation Theory Physical quantity Mathematics Theorem Absolute value Arc (geometry) Directed graph Proof theory INTEGRAL Höhe Lemma (mathematics) Desire path Residue (complex analysis) Rounding Category of being Calculation Film editing Equivalence relation Function (mathematics) Spherical cap Flux
Kante Zahl Link (knot theory) INTEGRAL Laufzeit Limit (category theory) Mittelungsverfahren Set (mathematics) Kapazität <Mathematik> Field (mathematics) Berechnung Hill differential equation Iteration
Residual (numerical analysis) Rational number Graph (mathematics) Irrational number Number theory Maxima and minima Integer Kapazität <Mathematik> Ganzzahlige Darstellung
Kante Zahl Group action Graph (mathematics) Direction (geometry) Laufzeit Desire path Maxima and minima Number Proof theory Residual (numerical analysis) Number theory Length Flux Proof theory
Kante Shortest path problem Zahl Moment (mathematics) Laufzeit Maxima and minima List of anatomical isthmi Square Limit (category theory) Set (mathematics) Parameter (computer programming) Professional network service Order of magnitude Military operation Hill differential equation Length Proof theory
Kante Link (knot theory) Graph (mathematics) Laufzeit Maxima and minima Limit (category theory) Set (mathematics) Recursive language Chain Residual (numerical analysis) Function (mathematics) Large eddy simulation Condition number Iteration Factorization Directed graph Proof theory
Zahl Residual (numerical analysis) Graph (mathematics) Function (mathematics) Vertex (graph theory) Condition number Length Directed graph
so genau sind die Änderungen der immer so seine Haftstrafe Lernmaterialien an der TU Darmstadt so Lola Seitz
jetzt geht es langsam so ich habe mir mal vorher genau hingeschaut und habe zu meinem Entzücken gemerkt dass es Platz langsam um interessante Themen geht denn die auch über die Idee 2 hinauslaufen wenn der Dozent anfängt die Sachen zu interessanten spannend zu finden ist es vielleicht eine sagen wir mal so eine zwiespältige Botschaft an die Studierenden aber ich hoffe ich kann sie dazu bringen dass auch nicht einfach nur zu schwer zu wenn sie war wirklich interessante und anspornt herausfordern zu finden so wir sind nach bei Thema also wie wenn es immer noch etwas machen was sich möglicherweise mit ihrer Idee 2 überschneidet Album von Vorfall Gassen Fluss Möhne Pfade finden bevor wir dann darauf aufbauend zu schnelleren und vielleicht auch ich denke auch interessanteren Algorithmen kommen werden die viel über die Natur von Algorithmen noch der allgemeinen erzählen können so und wir waren das letzte Mal stehen geblieben bei der Einführung von ein paar Konzepten dass wir sagen wir haben ja potenziell 2 Kanten für zwischen 2 Knoten von nach V und von vorn nach und dass für die Differenz aus beiden nehmen als den Netto Fluss der von nach V fließt ja ich fand es nicht noch mal wieder ganz von vorne an ich sitze jetzt wirklich mal voraus dass sie die Problemstellung maximale Flüsse und so weiter kennen wir wollen gegeben die vielleicht nochmal Nukus mündlich geben sein älterer Graf einen Staat Noten meistens erst Einzelknoten meistens T und die einzelnen kannten haben eine Kapazität an Ober- Kapazität und wir wollen möglichst viel Fluss von erst noch Täter schicken so dass diese Kapazitäten natürlich nicht überdehnt werden dass die Kaaba das ist der Fluss wird auf Anfang kannte nur so viel er nur so groß ist wie die Kapazität des maximal und Flusser Haltungsbedingungen auf jedem anderen Knoten außer Start und Zielquoten natürlich die Summe der für sie die reingehen in einen Knoten muss gleich die Summe der Flüsse seien die rausgehen so für 2 Mengen können wir das Becken dass nur diese Definition von dem Netto Fluss natürlich 2 Mengen von Knoten Igbos 6 große Plan sind Mengen von Knoten auf die können wir das ausdehnen indem wir einfach sagen für jede kannte die von einem Knoten x in einen Knoten y geht betrachten wir diesen Netto floss also das was wir da um im 1. Spiel schlecht definiert haben den Fluss Wert können wir dann tatsächlich auch als mehr drauf los wir haben ausdrücken nämlich man nämlich also als den Netto Fluss über jede kannte die aus ist die die aus es hinaus zeigt beziehungsweise nach es hineingeht wir haben wir schließen nicht aus dass sollt ich vielleicht von von 1 bis Sterne sagen wir schließen nicht aus das ihn es hinein auch Fluss fließt das ist ein bisschen und konnte nicht so richtig intuitiv vielleicht warum wir das warum man das nicht ausschließt aber er stört uns nicht essen es würde uns mehr Stimsons mehr Arbeit machen wenn wir das ausschließen das heißt wir haben schon die Situation an einem Fluss von es nachgeht dass wir beispielsweise hier in S durch Ausfluss nach C schicken über verschiedene Wege nicht über diesen einen wird natürlich wir haben letztes Mal darüber gesprochen das wir Flüsse auch auffassen können als der fließen über als Pfade und als Zielke eben nicht nur als nicht als kann Gewichte sondern Alternative Vorstellung ist es gibt über 1. Fluss über verschiedene Pfade von es nach die wir geoutet aber es kann auch passieren dass Fluss Aufzügen läuft zum Beispiel hier Fluss der von es mache es läuft oder Fluss der hier irgendwo mittendrin auch Umzüge läuft das ist alles durch die Bedingungen nicht ausgeschlossen natürlich kann das selbe Phänomen auch bei T passieren wie gesagt aus organischen gründen es würde uns ein Haufen Arbeit machen das von grundsätzlich auszuschließen und das stört uns nicht wenn es diesen was auch gibt Frage die Kameras nicht richtig ist wird danke für den Hinweis ja so dass sich schon mal wesentlich besser aus vielleicht noch wenn ich schon so falls für den Fall dass sich die kann man auch mal noch ein bisschen höher ist doch gut da schließen wir nicht aus und das habe macht es Sinn von Netto Fluss zu reden weil eben nicht nur Fluss aus es rausfließen Aufschluss nach S also alles was von es über bekannte nach unten Knoten existiert er wohne kann existiert rausgeht minus dem was reingeht so jetzt können wir damit
schon mal ein klein bisschen arbeiten wir stellen fest was auf Kunde Definition denke ich sich von von von selbst versteht im zweiten Spiel Gespräche mit den Natur Fluss von einer Menge zu einer anderen Menge er definiert und natürlich ist es unser Ziel das X und Y disjunkte Mengen sind die zusammen die gesamte Knoten Menge ergeben in der Vereinigung die gesamte Blutmenge natürlich ist unser Ziel aber wir haben jetzt diese diesen Begriff von Netto Fluss allgemeiner formuliert für beliebige Knoten man zu sollen die natürlich nicht gesund sein müssen die sogar im Extremfall wie hier im period Ar identisch sein können und wir stellen fest wenn man das ja einsetzt in diese Formel im im dritten beziehungsweise sich hier in die in die in diese in diese Frau im Zeiten dash jeder kann da einmal positiv einmal negativ auftritt in dieser Summe die in der F von X comma X steht und da geht es also verkannten Fluss einmal positiv einmal negativ Auftritt ergibt sich natürlich als Gesamtsumme 0 der Fluss der von einer Grundmenge X in die Glut Menge X fließt kann es denn nicht auch intuitiv klar der ist natürlich nur so was man auch vorstellen kann das ist der Punkt B hier der Fluss der von F X nach Y fließt und der Fluss der von etwa nach X fließt netto Flüsse na kehren sich sämtliche Subtraktionen um halt hier bin ich hier klicken sich sämtliche Subtraktionen unten wenn hier wenn ich hier in Zeiten dash die man groß X und groß y ihre Plätze vertauschen das heißt es kommt genau das negative H aus was auch sicherlich eher intuitiv ist also für Sie sind eine sehr intuitive Sache das was von X Y fließt und das ist genau das Gegenteil von dem was von entlang nach X ist einer von den beiden es positiv aber beides negativ je nachdem wo Netto eben das hat das hat die Rinde von Netto Flüssen wo Netto eben mehr hinfließt von wo nach wo ja das ist noch ein bisschen komplizierter erst einmal aber das ist glaube ich auch jetzt keinen keine große Sache dann billig aber versuchen noch anzudeuten wir haben 2 disjunkte Mengen X und Y das ist die Voraussetzung 2. 10. Knoten wenn wir sind also hier mit dem Graf kann sich vorstellen dass alles ist der Graf mit seine gesamte wurden Mängel und wir haben jetzt Z vielleicht mache man nicht gleich den allgemeinsten Fall sondern den Fall der uns meistens interessieren würde so das heißt also das ist noch nicht allgemein Zufall für diese dash sondern hier haben wir noch zusätzlich die Situation und das X und fällt disjunkt sind und das Y und Z das Jungs sind gleich nicht ungleich so das einer sollte ein x 1 das andere sollte ein y sein so so es gleich aus ist nicht mehr und da an diesem Beispiel hier bei dieser umgedrehten mit ihm aus können Sie schon sehen der Netz der Nettoverlust hier und der Nettoverlust hier der Netto zu Abfluss von X nach Z von z nach x und der Netto zu Abfluss hier die addieren sich natürlich weil X und Y des disjunkt sind aber das funktioniert nur wenn X und Y des jungen 10 2 wenn X und Y nicht des Jungen sind das manchmal vielleicht noch hier hinein wenn X und Y nicht dass Jungen sind den gibt es hier kannten die zweimal gezählt werden das heißt also der Netto Fluss zwischen X und Zeit plus dem Netto Fluss zwischen Y und Z ist nicht gleich dem Netto Fluss vom ganzen weil diese Kanten der Natur wird auch wir zweimal gezählt worden ist so dass es immer noch nicht der allgemeine Zufall der hier auf dieser Folie abgehandelt wird den allgemeinsten Fall ist ist ja nicht gefordert das X was y des Jungen zu setzen das ist nur gefordert dass sie beide die jungen zueinander sind so also der allgemeinste falle ist der dass das X und Y wieder sind 2 Knoten man die nicht unbedingt das Jungen mit der kann man jetzt setzen sondern nur miteinander und da sehen Sie haben sie gewiss Überschneidungen die im Prinzip diese Situation hier entsprechen im 1. dash das da da wo zwischen X und selbst etwas hin und her was hier drinnen passiert das ist nur in der Schnittmenge von beidem summiert sich alles zu 0 auf weil allgemein in jeder und jede Menge mit sich selber Netto Fluss 0 gehabt hat und nur das was wirklich von hier nach hier rüber geht in beide Richtungen nur das mitgezählt das heißt wir haben und sie dieselbe Situation als wenn X und Y das Jugendwerk hat so harter Tobak jetzt wird im Prinzip noch hat er
der Tobak aber ich glaube das können wir alle sehr gut zeichnerisch bewältigen was hier steht so das so dass die Folie sich dann Mitglied dieses Zeichen von selbst erklärt so was ist ein Einschnitt einen Schnitt generellen na gut wo was uns vor allem interessiert ist nicht ein genereller schnitt im 1. dash sondern bestimmte Schnitte sie erinnern sich dass sich Grafen in diesem Kapitel wo so maximale Flüsse geht nicht so wie üblich als Kreise zeichne okay Kreise sind auch nicht was ich da zeichnen aber so was ungefähr sondern dass sich die alles keine Ahnung was das sein soll als Muscheln oder was zeichne unten Schnitt ist im Prinzip das im einfachsten Fall was man sich vorstellt eine Zerlegung der Kanten der Knoten in 2 Teile die wir meistens dann wird S und T bezeichnen also jeder Knoten ist exakt in einem von den beiden und die Fälle die uns insbesondere sind die wie Sie eingezeichnet habe dass es in diesem in dieser Partie zusammenge- drin ist und diesen dieser badet uns Menge das habe wenn es unter natürlich auch so bezeichnet in diesem Fall sind wir schon beim zweiten dash wie sein gezeichnet habe die mir vielleicht noch mal kurz kurz durch was in die formale Definition eines Schnittes ist ein Schnitt ist also Graf der alle Knoten des Ausschuss ganz Grafen enthält der aber nur die Kanten enthält die die beiden Seiten miteinander verbinden also die so umgehen oder so von einem Knoten es sein kann ohne die oder von einem Knoten entdeckt sein gewordenen S es sicherlich etwas sehr intuitives machen sie sich aber klar dass dieses einfache Bild die Sache ein bisschen zu sehr vereinfacht er ist so will ich Ihnen mal zeichnen was in dieser Definition noch alles an Möglichkeiten und steckt er warum sich das Essen 7 die sich wenn man sie mal gesehen hat von selber er auch es fällt mir das Wort die sich von selbst verstehen aber man muss jeder mal gesehen haben natürlich kann so Schmidt erst einmal beliebig kompliziert sein ich deute das hier nur mal an ja so könnte der Schnitt zum Beispiel aus sehen aber er kann noch einen Schritt weiter weitergehen und könnte beispielsweise hier Teilmengen zu halten die wenn wir so spielen ob das die abgeschnitten sind durch diesen Schnitt ja dann würde das durch es würde dass es gehören dass sie würde es gehören das ja auch und das ja auch und wäre täten so was noch passieren ist nicht ausgeschlossen durch die Definition eines Schnittes was auch noch passieren kann das kann ich gleich dass sie wiederverwenden diese Frage er habe ich irgendwas falsch er das das stimmt das brauche ich eigentlich nicht so so ist es richtig ja okay machte nur einmal sind für diese zusammen Komponente das Tier zu schaffen dann den die den Film schauen danach fällt für den dabei sein inklusive selbst so was aber noch 10 im Extremfall zukommen kann es sogar diese Situation S T E R S T E so zum Beispiel auch das ist nicht ausgeschlossen wir werden sehen dass das jetzt Schnitte sind die uns nicht so sehr interessieren weil wir ansteht mit minimaler Kapazität interessiert sind und dann reicht es schon den oder den von S nach zu kucken und der das interessiert uns da nicht weiter gut aber es ist alles nicht ausgeschlossen so vorwärts und rückwärts Kanten sind glaube ich klar ich habe eine vorwärts kannte eingezeichnet also das bedurfte nicht gezeichnet habe war das einer vorwärts kannte und das andere rückwärts könnte jetzt wie gezeichnet habe ist dass sie eine rückwärts kann davon T nach Essen das eine vor kann davon ist machte gut nichts weiter zu sagen die Kapazität bis das was hier steht was steht hier wir wir betrachten alle kannten die nur von es nach die also die vorwärts könnten und deren Kapazitäten summieren wir auf also ich meine jetzt nochmal vielleicht doch ein das bitte noch mal einfacher hier weils schematisch einfachsten voll sicherlich am klarsten wird die Karte die die kannten die von links nach rechts über diesen schnell drüber gehen er vielleicht soll ich noch mal dazu sagen die sie natürlich nicht alle immer so schön lokal aus je nachdem wie der Graf eingebettet ist kann es natürlich lange kannten sein also lassen Sie sich also seien Sie misstrauisch gegenüber jeder Zeichnung gilt hier gilt auch woran er gilt natürlich anders vor Zeichnungen müssen immer in speziellen Fall darstellen müssen immer vielleicht vereinfachen und dann ist man ganz schnell auf dem falschen Dampfer dass man glaubt es Konzepte viel einfacher dass man ein anderes Konzept glaubt so die vorwärts kannten die also von Richtung es Staatseinrichtung Ziel gehen deren Kapazität summieren wir auch vor warum weil wir gleich zeigen werden gleich sehen werden dass der maximale Fluss werden davon ist auch die Schweden gerade diese der minimale Kapazität eines solchen schnitt das so wie sie definiert ist ist etwas was sicherlich nicht unplausibel ist aber dann immer ich das Wort plausibel hören denken Sie daran es gibt nichts plausibel als die Aussage dass die Sonne sich einmal in 24 Stunden die Erde dreht denke denke denke dann denke denke Moment wie das jetzt ja plausibel er dem auch er wahrscheinlich des glauben dass heute noch viele Menschen entspricht aber wie wir wissen nicht den Tatsachen also plausibel ist kein Argument deshalb müssen wir es beweisen so hier
vielleicht auch mal ein kleines Beispiel um das was wir jetzt gesehen haben nochmal noch mal so schauen wir haben hier Kapazitäten die oberste Cantat Kapazität 12 die zweitoberste hat Kapazität 9 die 3. also die und das der hat Kapazität 14 die obersten die und das das ein vorwärts kannten weil links es ist und rechts T und die Falle rechts und das in der Mitte seiner rückwärts so der Fluss der Netto Fluss darüber fließt von links nach rechts ist die Flüsse die Fluss Werte sind hier vor der Klammer 12 ihren 11 der der Fluss ist 12 plus 11 minus 4 ja netto heißt eben alles was was vorwärts fließt minus das was rückwärts fließt da kommt 19 aus wenn wir richtig gerechnet worden sicher bist nicht genug Koffein und es nachzurechnen und der der Kapazität diese Schnitte ist da kommen nur die vorwärts kann man das in die oberste der und ohne und der haben die Kapazität 12 und Kapazität 14 ergibt zusammen 26 das schaffe ich mit meinem Koffein Pegel jetzt immer noch dass der Efficeon so
jetzt kommen wir in die Richtung was ich eben angedeutet habe dass die größte dass die Kapazität eines die minimal Kapazität eines schnitt das der es von Sie diese These pariert dass das gleich dem maximalen Fluss wert ist die man von es nach den schicken kann ich will vielleicht noch mal gute ganz kurz was alles dazu sagen es ist plausibel dass das zusammenpasst dass da dass die Dicke dass die bereitet ist das kleinste Nadelöhrs gerade gerade die Menge ist die man insgesamt durch schicken kann aber wenn wir zum Beispiel sagen wenn wir dieses Problem Stellung verallgemeinern dahin gehend dass wir sagen wir wollen nicht eine Art von von gut von SAT transportieren sondern 2 Arten von Gütern die dieselbe Kapazität teilen dann geht es zum Beispiel nicht mehr diese einfache diese einfache Logik das dass die dass die Breite das ist das Ängsten Nadelöhr aus exakt gleich der dem er der dem großen Fluss wird ist immer durch schicken können ja plausibel muss nicht immer richtig sein selbst wenn es mal hier in Steiner war richtig ist muss es gleich um die Ecke denn es ist also so nicht mehr stimmt so was steht hier Wege Wirkung uns einen Fluss an der von es nach T flossen überschlägt und wir gucken uns irgendeinen Schnitt 1 der Staat für uns von einer separiert und die Behauptung ist das zweierlei die 1. Behauptung ist das der Netto Fluss der von es macht hierüber fließt gerade den Fluss wert ist und dass dieser Fluss werde darüber fließt höchstens so viel sein kann dieser Fluss müssen so viel sein kann wie die Kapazitäten der Weiss ist jetzt hier so ein bisschen mengentheoretische Spielereien denn überlasse ich Ihnen sich den anzuschauen wenn sie wollen wenn wenn sie das in der Prüfung zum Besten geben wollen oder wenn sie anderweitig interessiert also zunächst einmal dieser zweite Punkt dass dieser Fluss wird höchstens die Kapazität ist das kann man glaube ich ganz gut auch schon mal
erläuternden hier in diesem Bild was ist die Kapazität das schnellte das ist die Summe der Kapazitäten der vorwärts kannten so wie viele kann Netto von erst noch die rüber fließen na ja auch noch vor Ort könnte kann nur so viel fließen gekapert wie die Kapazität ja also mehr kann brutto nicht von erst nach die fließen als die Kapazität der Schnitt ist und dann ganz einfach passieren dass Fluss zurückfließt das wird natürlich beim Netto Fluss aus abgezogen das heißt insgesamt sie können sich sie kann sich drehen wie sie wollen solange die Kapazität für den eingehalten werden können Sie als Netto Fluss von erst nach Ted er nicht mehr rauskriegen als die Summe der Kapazitäten der der kann die von ist nach dir zeigen das ist eigentlich glaube ich logisch jetzt dieser 1. Punkt
dass dieser Fluss wert der der von es noch T der Natur wusste von SAT übergeht dass er gleich Fluss wird ist das möchte ich Ihnen jetzt nicht mit ein paar mengentheoretischen der Ableitungen näher bringen sondern das möchte ich ihn mit einer anderen meines 8. anschaulicher Jahren Argumentation näher bringen so Sie haben jetzt im Prinzip wie das Bild was ich gerade weg gewünscht habe war ich aber trotzdem lieber noch mal neue das ist nicht trocken und es nach Thiel so eine komische Muschel nicht mehr fällt anderes Analogie ein so was ist der Fluss wird das ist wenn Sie sich erinnern das was netto aus es raus fließt das heißt also der Netto Fluss wird über diesen Schnitt über diesen aller den Schnitt das ist die Definition des los wert ist so jetzt gucken uns einen Schnitt an wie kommen 2 Schnitte an einerseits diesen Schnitt wo irgendwelche könnten überfließen ich deute das noch so einen ist egal jetzt für die Argumentation ob jetzt nach rechts und nach links zeigen und da nehme ich mir und mehr hier diesen Knoten der hat vielleicht mehrere kannten über diesen Schnitt so dass 1 5 können über diesen Schritt in diesem kann die mit diesem Klon Inzidenz sind hin oder zurück es egal und er sind noch weitere kannten die Einrichtung gehen so jetzt nicht jetzt lasse ich diesen Knoten seine Position wechseln und jetzt ist nicht schlecht wenn man auf andere verarbeiten ja ja lieber mehrere weitere Vorhaben vielleicht mache ich das dann auch noch mal für die Nachwelt jeder schon mal die Situation ein bisschen farbig das okay so das Blatt noch so und ja wir diese könnten seltsamer diesen Knoten dar ich hoffe mal dass das jetzt eine gute Einsatz von von Farben ist ein didaktische wertvoll Einsatz wenn wieder ist nicht so sicher dass ich das so vernünftig mache so ich lasse Sie jetzt diesen einzelnen Knoten seiner Position wechseln der gar nicht mehr zu dieser waren zuerst das heißt ich habe um diesen einen Knoten meine schnitt ein bisschen weiter nach rechts verrückt so und wenn sich jetzt angucken das die Summe von dem was hier in diesem Knoten rein und raus wie auf der Seite muss gleich die Summe von dem sein hier raus und rein fließt auf der Seite sonst passen die Verse Haltungsbedingungen nicht ja für den Film für jeden Toten ist soll diesen gilt so rausgeht Mindestsumme 1 gleich 0 das heißt also der Netto Fluss der auf diesen kannten in den Fluten reingeht muss identisch sein mit dem Netto Fluss der aus diesem der hierüber ausgeht ja also das muss einfach hier so netto überwiesen das habe ich das ganze Bild versaut also spätestens hier ist das kein guter Ansatz von mehr so das bedeutet dass dieser neue Schnitt den ich produziert habe in dem ich diesen Knoten habe die mir die das Lager wechseln lassen dass der genau den das darüber die genau derselbe Netto Fluss rübergeht von links nach rechts über den alten Schnitt und jetzt reicht vollständigen Psion über die Anzahl der Knoten auf der linken Seite vom Schnitt Jahr in zu uns Anfang ist trivial weil der Netto Fluss über diesen Schnitt ist nach Definition der Fluss wert und Induktionsschritt ist ich nehme mehr ich nehme den neuen Schnitt mit mit Iglus mit E-Plus 1 Knoten ich muss also umdrehen betrachte den alten schnellt wenn den Options Voraussetzung an und nach an der und nach dem Argument es denn nun zum Schritt gezeigt so war klar geworden oder ich sehe da einige skeptische Gesichter ja aus sie meinen diesen Knoten mehr dieser Knoten muss nett diesen wurden muss mit seiner Umgebung netto Fluss mal haben dass gerade die Fluss Erhaltungs- Bedingung also vielleicht nur dass dieses wird so nochmal unter der Lupe betrachten damit da keine Verständnis liegen bleibt und sofern es diesen Knoten der hat irgendwelche kannten rein und raus ich zeichne man nur eine jeweils und hier genauso kann daraus und unbekannte rein so dass der einfachste Fall ist wo man nicht zu summieren so und dieser Schnitt denn man denn mal ich mal mit einer habe dieser Schnitt geht einmal so und der neue Schmidt geht einmal so also die Fluss Haltungsbedingungen sagt vielleicht so geht das das den Namen geben A B C D die Flüsse Haltungsbedingungen sagt ausgehend E-Plus C gleich rein Reingewinns also Fluss wertet auf Entschuldigung X von Art Plus reingehen der plus X von des ist gleich X von Bild plus X von 10 ja jetzt kann ich das auflösen ich bringe alles aufs auf die eine Seite der Gleichung was links ist und alles auf die andere Seite gleich um was rechts ist dann steht hier X von minus X von B der Netto Fluss hierüber ist gleich X wollen es muss ich genau schauen hier ist der Netto Fluss von links nach rechts da sie muss sie auch den Fluss von links nach rechts kommen da ich weiß was rauskommen muss brauche ich jetzt nicht mehr überlegen wie ich das wie das Umstellen passiert das heißt es geht mit meinen Koffein Pegel X von C minus X des so ja also das was netto über die er in diesen kann der Knoten von rechts rein fließt ist das was mir doch auch viel ins Haus fließt und damit haben wir das erledigt ist kann denn wie gesagt noch die falschen Diktion obendrauf über die Anzahl der Knoten auf der linken Seite und damit hoffe ich habe ich Ihnen das anschaulicher nahegebracht als über diese Ableitung
auf mengentheoretische beharrt auf einfachste Art Menge tierischer Basis so worum geht es jetzt hier jetzt geht's natürlich langsam die rhythmische Richtung wir haben es noch nicht bewiesen dass wirken wirklich Mac Slogan Charts der maximale Fluss wird ist gleich dem minimalen Kapazität eines Schnittes haben nur die Vorstufe GWB Wesen der maximale Fluss wert ist kleiner gleich ja letztendlich steht hier der in dem auch der maximale Fluss werden die minimal und auch so viele maximal wusste also minimal Kapazität das gilt auch noch diese Ungleichungen hier oben im immer mal 13 jetzt gehen wir zum
algorithmische und mit dem korrekte des Algorithmus zusammen führt dann die die gleiche bewiesen dass also der maxi- male Fluss wird gleich den minimalen Kapazität 1 schnitt das ist nicht eine schlüpft aus so was haben wir ich hier wir betrachten im im eigentlichen Grafen kann man das es ist noch sich Christopher okay wer wir haben den eigentlichen Grafen in der und in den betrachten wir Wege von S nach T die jetzt anders sind als die bisherigen nämlich die auch rückwärts kannten zu lassen also hier mal vielleicht gefordert scannte eingefordert scannte rückwärts kannte eine Frau kannte zwar rückwärtsgewandten und so weiter bis wir nach Telekom wir betrachten aber nicht irgendwelche solche Wege sondern wir haben sie denen sich beim letzten Mal den Visual Grafen eingeführt was war das noch mal wir haben in der es war Graf dieselben Knoten wie der ursprüngliche der eigentliche Graf aber andere gerichtete Kantenlänge nicht für jede Kante wo noch Restkapazität übrigbleibt gegen bemerkte dass unsere soll auf ist immer definiert in Bezug auf einen aktuellen Fluss deshalb ist er auch indiziert mit diesem Fluss des F und wenn wenn wenn es noch keine feste wenn er noch Restkapazität lässt wenn er für mich am oberen Anschlag bei Kapazität des erkannte dann ist diese Karte mit dieser Restkapazität immer so war Grafen drin bei wenn eine Kante für positiven Fluss wird hat wenn man also Fluss wegnehmen könnte dann ist sie mit diesen positiven Fluss wird als Kapazität denn das heißt also immer es war Grafen sind das werden wenn das wenn die genau dann wenn die alle diese Eigenschaft haben bei den vorwärts könnten ist noch Restkapazität da kann man kann man also den Fluss noch erhöhen bei den rückwärts kannten S Plus drauf kann man also Fluss wegnehmen genau dann ist dieser Fahrt auch mit allein mit vorwärts könnten im Reservat Grafen trennen ja immer so Grafen war keiner kannte drin die in die Richtung kein Spielraum mehr lässt deshalb werden denn die könnten alle drin sind dann haben sie alle Spielraum und damit können wir jetzt entlang dieses Pfades den Fluss einen wir können jetzt kucken kleines Epsilon hernehmen und immer so sogar Grafen heißt es einfach diese Menge an AT Epsilon zusätzlichen Fluss gegenüber dem aktuellen Fluss F die hier drauf setzen wenn er zum klein genug ist dann ist da keine Kapazität überschritten und das bedeutet zurückübersetzt in eigentlichen Grafen auf den vorwärts kannten wird der Fluss erhöht auf den Rücksitz kannten wird der Fluss entsprechend vermindert also Sie sehen was jetzt der bekommen sie langsam eine Vorstellung davon dass er es war darf keine Schikane ist sondern damit damit genug Stoff für die Prüfung gibt oder so Eier sondern dass er durchaus einen Sinn hat weil er die Situation deutlich vereinfacht werden später noch heute wahrscheinlich nicht mehr Algorithmen sehen wo es kaum noch im Bus muss ein bisschen umständlich wird sie auf dem ursprünglichen Grafen zu formulieren wo es sehr viel eleganter einfacher verständlicher wird wenn man sie auf mir so war Grafen definieren so wie Sie wie groß ist dieses Erzähler na ja für jede einzelne kann da haben wir einen gewissen Spielraum die hoch gehen können ohne die Kapazitäts- Bedigungen zu zu verletzen bei den vor können und wie tief wir gehen können bei dem Gesetz könnten und dass der Fluss bis sich negativ wird wieder ein Siegernamen eine Spielraum und wenn immer das Minimum aller dieser Spielräume aber das gemacht haben dann können wir Fluss drauf erhöhen machen Sie sich klar das hat ich glaube ich schon mal gemacht kann aber ich schau das noch mal zu machen machen Sie sich klar dass wenn wir auf diese Art und Weise entlang eines Fares von Essen 18 den Fluss verändern vorwärts kannten erhöhen auf rückwärts kannten vermindern oder umgekehrt was vollkommen egal ist nur dass wir natürlich eigentlich von S nachdem mehr haben wollen und nicht weniger machen Sie sich klar dass das bei jedem Knoten der überhaupt betroffen ist egal wie das aussieht ich aber vielleicht kann ich müssen wir an dass die Haltungsbedingungen gewahrt bleibt so wir haben von S nach C 4 Möglichkeiten Vision wie das aussehen kann für den Knoten da drauf 2 vorwärts kannten 2 rückwärts könnten wir interessieren uns immer für diesen Knoten eine vorwärts und einer rückwärts kannte eine rückwärtsgewandte und eine vorwärts kannte so ich habe das mal jetzt mit 4 verschiedenen Farben mit Gefahr Faden bezeichnet man könnte es natürlich auch alles auf ein verzeichnen aber das die ist sind aufgrund dieser 2 Seite Tat sicherlich übersichtlicher so was bedeutet das wenn ich jetzt wenn ich jetzt Epsilon mehr hierüber schickes es bedeutet hier plus selbst lange hier bloß Ärzten und hier wird der Fluss wird vermindert in beiden Fällen hier erhöht unvermindert und hier vermindert ich erhält so hier ist es so die Summe der eingehenden Flüsse wird um etwa hält die Summe der rausgehen Flüssen Erbsen hält die Differenz von beiden bleibt gleich spiegelsymmetrisch hier die Summe der herausgebenden wird vermindert diesen einem verminderte sonst bleibt gleich hier die Summe der wird überhaupt nicht berührt sondern die Summe der eingehenden Flüsse wird berührt nämlich die wird hier über diese kannte um dann erhöht und die Umerziehung gleich wieder vermindert die Summe der ausgehenden Flüsse Werte bleibt gleich weil sie gar nicht mehr wenn die Summe der reingehen und was wäre bleibt gleich weißen Position und minus erzielen in diese Summe gibt und hier auch die Summe der eingehenden Fluss Werte in diesem Knoten wird überhaupt nicht verändert die Summe der rausgehen Fluss Werte bleibt auch gleich weil sie einmal umwälzen unvermindert und einmal um es nun wieder etwas auf einer keine vermindert um verbannen kann am selben Tag ja das ist das geniale dann an Flüssen dass sie das sieht den Fluss wert dass sie da sie da einfach entlang einer K 1 1 eines Pfades von ist nach die den Fluss wird auf diese einfache Art und Weise verändern können und sie können blindlings darauf vertrauen dass die Fluss Haltungsbedingungen dabei gleich bleiben Sie müssen auf die Kapazitäten achten so so ein Fahrrad wir haben bis jetzt und ich würde 1 ist ein Auge ihren der Einfluss erhöhen Abfahrt meistens für malerischen Literatur dem Begriff erhöhen was in dieser muss aus flog man ist
so das haben diese Beobachtung haben jetzt auch schon mit dieser Zeichnung erledigt wo ich denn er die Situation im eigentlichen Grafen der Situation immer so alt Grafen gegenüber gestellt habe diese Beobachtung 15 ist nichts anderes als das was hier visualisiert für diese Korrespondenz so na endlich so oft wurde hier schon in der Vorlesung benutzt das n die Anzahl der Knoten die Anteile kann es ist haben endlich mal definiert gut wahrscheinlich wird es war auch schon mal definiert ich will es nicht ungerecht sein so ist die maximale endliche Kapazität die irgendwo in diesem Graben vorkommt auf irgend einer könnte sie ernähren sich werden kurz erwähnt wir haben auch wir lassen prinzipiell auch zu dass kannten eine Kapazität haben von unendlich das heißt also es ist egal wie viel wir drauf schicken wir wissen das würde mir niemals der Flaschenhals werden aber im Normalfall haben wir das auch nicht hier in in dem in den naheliegenden Anwendungen auf Kommunikationsnetzwerke Wasser Netzwerke Stromnetzwerk oder was auch immer haben sie natürlich niemals eine unendliche Kapazität in anderen Situationen es sinnvoll aber denken Sie jetzt erst einmal an die naheliegenden Anwendungsgebiet der da können Sie viel kleiner und endlich vergessen denn es die maximale Kapazität überhaupt vorkommt ich glaube die Kosten die brauchen wir momentan in diesem Kapitel nicht wir sind jetzt gerade damals Logos keine Kosten gibt okay also dieses letzte die Definition von C glaube ich kann mir hier erst einmal wieder in diesen Abschnitt der Vorlesung vergessen so
argumentieren das habe ich eben schematisch erklärt hier sehen Sie noch mal Beispiel um sich selber das klar zu machen sie haben hier in um längst in diesem Bild in Schwarz die Kapazitäten in Blau die die Flurtür Einfluss Werte und sie sehen das Beispiel ist wieder ein bisschen einfallslos ist das selbe Einfall so Beispiel was wir letztens hier auf den Folien hatten das das ist nur eine dass der gesamte Fluss von 5 Einheiten über eine einzige aber ein Einzelfahrt geht natürlich nicht einfallslos sagen dass es despektierlich sondern es ist übersichtlich und das meine ich auch so ja das Wort nun gefällt oder beziehungsweise mit klar geworden dass einig das war es was ich meinte so das war despektierlich sagen was also verwendet habe falls Sie interessiert ist findet sich bestimmt in Wikipedia oder halt in den Wiktionary oder so dann kann sicherlich so oder Visual Graf den hatten wir genau wir dieses Beispiel gesehen zur anlässlich der Einführung des Visual Grafen letzte Woche es ist normal dass wir was sie letzte Woche nachvollzogen haben und in diesem Riss war Graf müssen Sie mal gucken ja das ist immer Grafen definiert da können Sie einfach den ganz normalen stinknormalen Fahrt von ist noch die hernehmen und das ist der Einfluss eigener Faden so ergab es ist normal Abfahrts- und wenn sie das wieder zurückrechnen auf ihren ursprünglichen Grafen dann ist es sinnvoll wenn gezeichnet habe mit vorweisen mit rückwärts kannten wo auf dem vor es kann noch Restkapazität üblich ist und auf dem etwas kann das positiver Fluss drauf denn wir ziehen kann so jetzt kommen
wir zum Algorithmus und zum erklommen Kategorien in 1 in beides zusammen so sie kann das aus der Mathematik das Sie das sehen viele Theoreme von der Form sind sie wollen 2 meistens 2 aber manchmal auch 3 oder mehr auszuhalten sie haben sie haben 3 oder mehr Aussagen von denen Sie zeigen wollen dass die Äquivalenz zueinander sind wie macht man das immer in dem man zum Beispiel immer für Beweise aus 1 wird 2 Auswahl Verbrecher aus 3 x 1 und dann muss man gucken dass das einher mit und schon war kreis ist dass jeder Knoten drauf ist oder halt in beliebiger Reihenfolge so wir haben einen gerichteten Grafen des wieder mit Kapazitäten drin und von es nach der wollen alles also es und diesen gegeben und wir haben in diesem Grafenwiesen die Grafen des einen Fluss F und dann ist die Behauptung folgende genau dann wenn ein maximaler Fluss ist das ist die 1. äquivalenter aus Sorge genau dann auch findet man keinen Fluss schönen Fahrt mehr in diesen Grafen und genau dann auch gibt es einen Schnitt dessen Kapazität gerade dieser Fluss wird ist das was ich ihm gesagt habe Charts Theorien das ist einfach die grinst von 1 und 3 Einfluss ist genau der der die die maximale Fluss größere erst Betrag ist genau die Capaci minimale Kapazität eines Schnittes wenn wenn Sie hier einen anderen Schnitt her nehmen als den den minimaler Kapazität period kann es natürlich nicht funktionieren Es muss der minimale Schnitt sein hier hat der der 3 erfüllt der mit minimaler Kapazität musste wenn ich sage der Minikamera kabbelt immer ich natürlich einer mit minimaler gab es Sie dass keiner mehr sein die gleiche minimal gepostet alle und leiden seit sie Fall also schön so der Beweis ist jetzt nach allen Vorarbeiten recht einfach die also durch wir hier auf der Folie ist von 1 mach 2 das ist mit wieder mal mit Beweis durch Widerspruch angenommen der 2 geht nicht angenommen es gibt da noch einen Fluss einen Pfad na ja dann erhöhen wir den Fluss entlang dieses war ob man Erzählern Erzielung größer 0 und dann haben wir den Bell nennen den Fluss mit höheren Fluss Wert steht im Widerspruch dazu dass es maximal los ist einfache Standard Argumentation so von 2 nach 3 das glaube ich kann ich Ihnen wieder mit einer Zeichnung näher bringen was hier steht so ja wieder unsere schöne Muschel von S nach und wir konnten uns jetzt mal an also wir nehmen an es gibt keinen Fluss nun Pfad hier also dem anders Aussage 2 gilt jetzt machen wir folgendes wir wir gucken uns an dem Visual geworfen das einfacher Sie können wenn Sie nun sich noch nicht so so richtig vertraut fühlen wenn wir sogar graben längere so Grafen den sich das was ich sage immer noch mal übersetzt in den Ursprungs Grafen das heißt also hier wo ich von Vorwärts kann immer so weiter Hafensprecher mit drin Kapazitäten kann ich genauso gut reden von Vorwärts kannten oder rückwärts kann bei vor was kann man das gab es mal war jedenfalls könnten mit Fluss mit positiv aus so wir gucken uns an was kann ich alles mit Fluss in den Faden erreichen ja denken Sie sich da irgendeine breiten Suche Tiefensuche egal was welche Knoten kann ich alle erreichen so T können Sie mich erreichen das heißt irgendwo irgendwo gibt es eine Barriere dar dies verhindert dass IT erreichen können zur hier sämtliche kannten die hierüber gehen der nicht sowohl die linke Seite nennen sie jetzt erst und die rechte Seite denn Sie jetzt die was heißt das dass es eine Barriere ist der Fall ist auf dem vorwärts kannten es Fluss bis zum Anschlag drauf sonst hätten sie von diesen Knoten aus noch einen Schritt weiter kommen können hier rüber auf die andere Seite für alle rückwärts kann dem Ursprungs trafen die darüber gehen heißt das und das kein Einfluss drauf unter Anschlags was sonst hätten sie hier im immer so ein Grafen einen Schritt weiter gehen kann das heißt also für diesen Schnitt gilt der Fluss auf von links nach rechts ist maximal und der Fluss von rechts nach links ist 9 von den nach rechts gleichen Kapazitäten von rechts nach links gleich 0 und das divdiv los wer die Kapazitäten von Ihnen das heißt jetzt sehe bei diesen Fluss bei dem Netto Fluss der von links nach rechts geht zählen wir von links nach rechts die Kapazitäten auf und ignorieren die Kapazitäten Rechner das ist gerade die Definition der Kapazität dieser Schnitt das das hat der Fluss wird es gleich der Kapazität dieses speziellen so konstruierten Schnitt aus und damit haben wir einen Schnitt konstruiert dessen Kapazität gleich dem Netto Fluss wert über diesen Schnitt ist und wir haben schon gesehen vorher dass der Natur Fluss wird über irgendein Schnitt gleicht dem Fluss wird von ist macht ist so und jetzt gehe der dritte Schritt noch das ist jetzt auch nicht weiter dramatisch wenn wir so einen schnell in der wenn wir tatsächlich die MdE den dritten Fall haben in der 3. Fall eintritt es gibt einen Schnitt dessen Kapazität gerade der Fluss führt das aktuellen Flusses ist dann kann natürlich kann es natürlich keinen größeren Fluss Wert gebe es keine keine bösen Kursen Fußwerk wird geben denn wir haben eben gesehen jeder Fluss wird ist kleiner gleich die Kapazität jeder schnell das und der Mündung irgendwo mal Gleichheit haben heißt das ist keine keinen größeren Schritt geben denn den würde er würde sei er gestern schön es kann keine Gründe Grundwissen großen Fluss wird geben denn dann wäre dieser Fluss wird größer als die Kapazitäten so schnell dass wir mal bei Ihnen gesehen dass das nicht sein kann dass der ihrer Fluss wird von jungen eben Einfluss kleine leichte gab sie von und im Schnitt ist und damit bleibt es also übrig als das in dieser Fluss maximal ist das kann keine großen geben und das ist schon
so wie sie dieser Algorithmus aus in der Algorithmus ist im Prinzip nur die Umsetzung von diesen Theorien was jetzt im bewiesen haben was haben wir gegeben wir haben wie immer jetzt in diesem Abschnitt gegeben eingerichteten trafen ein die Grafen mit Noten könnten wir haben Kapazitäten wird gleich noch mal auf einer bemerkens- vor ihr stehen warum wir ganzzahlige Kapazitäten hier haben wollen haben müssen sie sich wir haben schon mal diskutiert dass das keine echte Einschränkung ist sehr Sendekapazitäten vom Typ dabei sind als Double gegeben sind kann man kann man irgendwie feingranulare ist geht er über die er über die da bewährte legen und uns und die er vielleicht Tausendstel oder Millionstel oder was auch immer und wenn es nur ein kleiner ist dann macht die Rundung auf auf diese auf diese ganzen er kann zeigen viele von 1000 soll von einem Millionstel jetzt kein Unterschied mehr für die Kapazitäten so wir haben natürlich immer stark Noten oder Quelle S Zink N Knoten senke Termine und unsere Kapazitäten sind wir so sind wir weiterhin bei bei 0 das in den ganzen Abschnitt obwohl Kapazitäten irgendwo positiv und wir wollen einen maximalen Fluss fahren von Essen nach die finden so wir fahren an mit dem 0 Fluss am einfachsten es muss ja nicht der 0 Fluss seines könnte und ein anderer zulässiger Fluss seinen den wir zufällig wüßten oder mit um mal Reste konstruiert haben aber wir sind machen jedenfalls nichts falsch wenn wir sämtliche auf sämtlichen kannten den Fluss wird mit 0 beginnen lassen wir nehmen denn es waren Grafen hier weil wir endlich in dem wir immer die Pfade suchen denken Sie sich wie gesagt immer das zurück in den Ursprungs Grafen wenn wenn sie sich nicht komfortabel ist als an einem lizismus ist muss man sich nicht komfortabel damit für einen wenn Sie denn sie müssen fremdeln mit denen wir so alt Grafen ich habe selbst erst mal an sich das erstmal mal Student gelernt habe ein bisschen befremdet immer so antrafen so soll es ein ob man hier einen Pfad geht immer so Grafen ja was machen wir dann wir berechnen dass das Erzählern wie ich sagen wie ich schon sagte das Minimum der Spielräume auf diesem Pfad des minimal das ist Minimum der Restkapazitäten aller kann auf diesem Pfad sind für alle vorwärts kannten erhöhen wir in den Fluss wird auf dieser Kante um besagtes Epsilon für eine rückwärts kannten Männern wie dem Fluss wird untersagt das Epsilon und für die nächste Runde für die nächste tration müssen wir natürlich dafür sorgen dass der so ein Dorf mit seinen Restkapazitäten angepasst wird auf die einen aktualisierten Grafen also soll Graf ist immer definiert im Verhältnis zu einem aktuellen Fluss und wenn sich der aktuelle Fluss ändert muss natürlich der war Graf entlang dieses Pfades nun weiter nicht mehr als ein dann dieses war das muss so nicht abgebildet werden weil nur auf den sich die nach wie so ein Kapazitäten ändern und das ist der ganze Algorithmus ja richtig den wichtigsten Grund habe ich vergessen am Ende wird das Endergebnis dann der Rest der der letzte Graf der letzte Vorstellung ausgegeben wann ist das Ende erreicht wenn es keinen auch mit ihren in Fahrt mehr gibt wie wir eben gesehen haben auf der letzten Folie ist das ein äquivalent dazu dass der Fluss wird der Fluss maximalen der Tat so jetzt haben wir
hier ein Beispiel dafür das ist miserabel werden kann die Laufzeit sogar bei kleinen Fluss werden miserabel wird bei kleinen Körpers bei kleinen kannten in diesem Banken ein grafischen miserabel werden kann sie haben hier eine riesengroße Zahl ja vielleicht ne Milliarde keine Ahnung wenn sie das Innere sozusagen halten das ist egal das nur diesen und sie haben hier Kapazität 1 drauf auf dieser mittleren kannte so jetzt kann es ganz dumm laufen es kann ganz dumm gelaufen dass jeder so implementiert haben oder dass die Kanten und Knoten erreichen vorliegen sind das erst Mal diesen Fahrt hier finden über über diese Mittel kannte also Erstlings hoch dann runter und dann rechts wieder hoch um wie viel kann 7 Fluss erhöhen um 1 schön jetzt läuft weiterhin dumm sie nämlich die kannte sie dem von aus die Kante rechts runter stellen fest hier kann ich auch etwas Fluss erhöhen also sprich vermindere gehen sie hoch und gehen hier auch was ist das Ergebnis jetzt ja den Fluss wieder um 1 erhöht schön erfahren Sie wieder ja wäre sie haben deterministischer Algorithmus zur Berechnung der der der was ist jeweils der nächste Pfad er das heißt also Sie machen jetzt wieder derselbe wie vorher weiß derselbe Suha Graf ist nur mit Wasser zur Stadt Fluss wird 0 denn es ist mir hier wieder hoch und runter hoch wieder was wir damals erhält wunderbar und wieder zurück wunderbar freuen sich das in jeder Iteration der Fluss wird wunderbar um 1 erhöht aus sowie sich so wie sie sich jetzt mit dem zurzeit mit dem Festgeldkonto freuen dass ihr Geld jedes Jahr um ein Prozent erhöht wird aber die durch genaues drauf schauen sehen Sie mal dass auch er malt auch mehr Glück haben können oder man hätte es auch vielleicht geschickter anstellen können und hätte einmal gleich hier unten und einmal gleich die Menge von hier rüber geschickt hätte gleich in 2 Schritten die gesamten maximal möglichen Fluss wird von 2 1 von links nach rechts schicken können so und Sie sehen im schlimmsten Falle die Anzahl der der auch mit jungen Schritte kann beliebig schlecht werden er war dieses groß hier unten in in dem um Ausdruck ist gerade in diesem Fall das groß in dem Beispiel dumm gelaufen aber
immerhin mit ganzzahligen Kapazitäten ja ist ganzzahlig hatte ich es vergessen zu sagen aber gute weil vorausgesetzt wird ganz soll in Kapazitäten kriegen sie meine in in mal ob man die Schritten den NNN mal Iterationen der in der Schleife jede Schleife kostet sie maximal so viel proportional die Kanten drin sind weil die Knoten sei kleiner als sie kannten Zahl oder oder Hinweise größer also methodisch also kriegen sie immerhin diese diese Laufzeit raus wenn sie wenn sie eine sehr großes haben eben eine Milliarde sowas ist natürlich schlecht messen der kleiner aus haben ein kleines groß haben vielleicht 10 ist es natürlich super gut
so jetzt kommen wir zu der bemerkens- vor wo ich zusagte warum wir ganzzahlige Kapazitäten haben wollen zumindest wenn wir irrationale Zahlen hernehmen das natürlich und komme wieder nicht geht aber wir können uns das so vorstellen wenn wir irrationale Zahlen hernehmen dann kann es sein dass der Algorithmus der Euro müsste ich jetzt vorgestellt hatte der den bei Schleife Javaner ist nicht von unmittelbar von vorne gegeben dass sie tatsächlich terminiert er und sie konnten zeigen dann in der Arbeit in der dieser muss vorgestellt wurde zur also 62 also jetzt 50 Jahre her das das dann weniger Kapazitäten irrational sind dass es durchaus passieren kann dass der Algorithmus überhaupt nicht terminiert oder immer noch einer der wenigen das die dass die Kapazitäten irrational sind dass der das Herz dass er zwar terminiert beziehungsweise Nein der Termin hier nicht schön und er terminiert nicht aber er konvergiert auch wenn dann auch wieder nicht während die einen sich dunkel an die Annales es nicht eine Folge die monotonen wächst und nach oben beschränkt ist konvergiert sie haben sich ja also auch wenn er nicht den mir der konvergiert aber sie konnte noch zeigen es muss nicht der maximale Fluss wird sein wogegen das geht wenn die irrationale Zahlen haben in der ganze Zahlen haben und letztendlich bedeutet das auch wenn der rationale Zahlen haben den rationale Zahlen keinen gemeinsamen Nenner finden Hilfe von endlich vielen rationalen Zahlen können im gemeinsamen Nenner finden können das als Basis nehmen für ganzzahlige Darstellung der Kapazitäten also auch bei rationalen Zahlen konvergiert immer es kombinierte bei uns damals nicht das ist mehr theoretische Einsicht die natürlich Gott sei Dank nicht vom praktischen Belangen ist weil wir gar keine rationalen Zahlen überhaupt darstellen können im Computer so was Sie jetzt entdeckt haben und darauf will ich jetzt als nächstes zu sprechen kommen ist die immer noch mal zu diesem Beispiel zurück von Leben warum
das wir und was ist an diesen beiden Fahrten oben und unten geschickt da was auch entdeckt haben noch bis in das was er dem Kap entdeckt haben ist weil wir von der wir das jetzt entdeckt er Börsen-Chart genau
wenn wir mal kürzesten Wege dem im Sinne kürzeste im Sinne von Kanten Zahl der kürzeste Weg ja ja sie sehen dass in diesem Beispiel zufällig über das wir uns dass wir uns nicht alles nicht passiert werden diesen Fluss werden diesen Pfad zum Beispiel dass es so gewohnt mit 2 Kanten als Christen weg dann diesen hier oder umgekehrt dass wir uns gar nicht viel passiert was die was im umgab gezeigt haben und was sie was wir jetzt besprechen
werden ist wenn wir immer stehe irgendein auch man so soll man den kürzesten Fahrt suchen dass das ganze dann viel viel bessere Laufzeit hat insbesondere auch auch bei noch so kranken Kapazitätswert noch bei irrationalen Kapazitäts- werden wurde das konvergieren wenn es das den sein möglich wäre wie finde kürzeste Wege in diesem Sinne natürlich liberal Besucher das haben wir schon betrachtet die Preise und findet man immer der Wege mit minimaler kannten Zahl von einem Klon zum anderen
indem wir von diesen 1. Uniper L Branson straffen so die Behauptung ist jetzt dass das ganze in dieser Laufzeit automatische nur durch diese kleine Änderung nur durch diese kleine Änderung das immer den kürzesten Fahrt nehmen und nicht irgendeinen auch mit Abfahrt dass es zu dieser Laufzeit führt Noah hier das ist da steht nicht ohne Sinn ohne umsonst das Wort Warften der Proof also wir sollten das vielleicht eine kurze Skizze oder andere ist das des Beweises das ist wirklich ein bisschen 1 1 1 geht zum nur und ich glaube fürs Verständnis des weiteren ab diesem der weiteren Ausführung diesem Kapitel wenn wir noch sondern also kommen ist es sehr sehr 1 Std mich da ein bisschen mehr dazu sage so der entscheidende Punkt ist erst einmal sehe argumentieren jetzt den Fluss entlang eines Fahrrades und damit das Ganze jetzt nicht zu kompliziert wird nämlich nur vorwärts kam nach der mit Mediation sich auf rückwärts kann genauso gut übertragende zum Weise bitte ich kann auch sagen wir sind so gerade mehr gibt es da betreiben nur vor kann es egal so vielleicht machen das mal so so eine Kante interessiert uns hier und ansonsten ist war danach die so dass es der Fahrt über den wir den Fluss erhöhen jetzt kann es dadurch dass wir hier drüber den Fluss erhöhen kann es passieren dass neue Augmented Nachfahre entstehen was kann wie kann das sein na ja in dem der zum Beispiel diese kannte vorher gleich 0 war der Fluss werden jetzt sehr größer neue das ist ein neuer Pfad entstanden beispielsweise der so aussehen könnte hier sank rückwärts und dann hier lang ja das ist also diese diese beiden jetzt würden hier die waren schon vorher auch mit von hier nach hier argumentierend hier ging es nicht weil hier vorher gleich 0 Fluss war und hier auch schon vorher argumentierend so der entscheidende Punkt jetzt ist der wenn auf diese Art und Weise das Bild ist wieder grob vereinfachend also man kann sie Situation noch komplizierter vorstellen dass ich nur eine Kante dieses weißen Pfades in den roten Faden sondern mehrere kannten aber es ändert nichts an der gemeint Aktion der entscheidende Punkt ist der dass dieser neue Pfad sie soll für mich doch die können Richtung sollten so dass dieser neue Pfad in punkto Pfad länger größer sein muss als der alte Pfad warum dieser Bogen hier muss mindestens so viel länger haben wie dieser Bogen ja sonst wäre das ja keine Küsse ist da weg von erst nach des wenn das sie kein Christa Weges von diesem Knoten nach also wenn ich diese Weglänge hier mal mit bezeichne da muss das hier dieser Bogen hier Weglänge mindestens haben und genau so wenn ich diese Weglänge hier von diesem weißen Fahrt mit B Bezeichner dann muss dieser Bogen hier mindestens auch wenn mal das wir nicht einmal mit anderer Farbe zu rechnen größer gleich aber größer gleich haben sonst wäre das der Weiße Pfad keine bezüglich keine Zusage Größe Cursors weg so wenn ich das zusammen Zähler dann habe ich mindestens aber plus mindestens B plus 1 und der ursprüngliche Fahrt war W Plus habe ich die Karte zweimal gezählt also minus 1 die Länge des ursprünglichen vor das war also B Plus minus 1 und die Länge des neuen Vater ist also ich gleich und die Länge des neuen Vater ist mindestens plus 1 plus 1 das bedeutet sie können keine Pfade neu erzeugen auch Kinder fade die bezüglich kann zwar kürzer sind oder gleich sind dem vor den sie gerade waren das heißt im Laufe der Zeit wird die Länge einer Christen Kanther da ertönen die Länge eines Küsse ist war das immer größer ja es und in gewisser Weise S und T gehen immer weiter auch von anderen weg was was die erreichbaren Bahnfahrt angeht die die haben immer mehr Distanz zueinander und so das ist das 1. was wir uns jetzt merken müssen ich guck mal dass sich das Bild jetzt nicht gleich wieder abwische also protestieren sie wenn ich das für jetzt kommt der zweite Punkt dabei in das muss sich einmal überlegen über das es muss wenn man ganz genau überlegen wie die Argumentationen war einen eine kann der wird saturiert mindestens und das muss ja genau jetzt ist folgender Kontrollen Argumentationen dazu wir erhöhen also Fluss entlang einer solchen Frage ist nur so nun ab das ist jetzt die Kante des wird das nennt man den Sprachgebrauch in dem Bereich saturiert das heißt bis zum Anschlag eine Kante mindestens ist da die bis zum Anschlag mit Fluss noch gefüllt wird weil wir nicht mehr die kleinsten Flaschenhals davor noch minimale Restkörper Restkapazität die drin ist das ist unser Y und den wir dem versehen das heißt die kannte diese dieser kann zum Flaschenhals ist die wird saturiert das hinterher dann kein keine restlos mehr darauf keine positive restlos mehr drauf so das bedeutet dass diese kannte auch in dieser Richtung nicht mehr in unserer worden waren ist nicht mehr für Flüsse eine Pfade Zustand wir zustande kommt wenn nicht mehr für seine fade wir haben verwendet werden kann irgendwann später passiert es aber wieder dass diese Kanther kann es durchaus passieren dass diese Kante wieder für Flüsse und zur Verfügung gestellt wie kann das sein das kann nur sein dass es vorher zwischendurch mal dass diese keine vor zwischen ich meine ein argumentieren Fahrt war der diese kann und das in Tagen hatten Einrichtungen Fluss reduziert hat ja Sie erinnern sich anderes Beispiel hier eben hier diese bei dieser
kann dann werden wenn wir so ungeschickt vor immer diesen fahre hoch runter hoch und danach unter hoch runter dann wieder hoch unter hoch da wieder hoch und runter was dieser Kante laufen dass der Fluss von 0 auf 1 erhöht wird und von 1 auf 0 reduziert und auf ein Bild reduziert interessiert so wir werden jetzt die Länge des kürzesten Pfades hier ja er war da muss ich jetzt hier in der neuen Situation mindestens Elle sogar plus 4 sein nach dem was wir im berechnet haben diese Länge des kürzesten Pfades hier die der sich jetzt auftut auf den wir jetzt auf dem rückwärts diese kann er diese Karte benutzen können hier diese wurde dieser Roter Pfad der hat mindestens doppelte länger natürlich doppelte Menge sondern Länge plus 2 gegenüber dem alten fort und wenn das Ganze noch mal umgekehrt passiert hat jetzt mindestens Länge 4 mehr das heißt also diese kannte kann diese Kante kann höchstens oh voran mal saturiert werden eine feste gerade keine beliebige kann aber fast gar kannte kann höchstens O von einmal saturiert werden weil die Länge des die Länge eines Fahrrades also München fahre das kann ich also im schlimmsten Fall im nächsten Fall enthält die alle Knoten er die Länge 1 1 1 küssen ist keine ist solange Wort noch weiter geht das kann keiner so von allen so wenn wir jetzt kannten haben dann heißt es für die Anzahl der argumentierenden Schritte das wir höchstens O von er mal n viele auch mit denen wir da haben können den die können jeder also kann müssen sofern er mal auf meine Tieren also Sartori an in jedem ob man diesen Schritt saturierte aber eine Kante die auf überhaupt eine keine saturiert mal jeder einzelne könnte kann haben wir als MAN können insgesamt mal n oft die erkannt dass das überhaupt unbekannte saturierten und da wir in jedem Moment ihren Schritt eine keine saturierten kommen insgesamt einmal n maximal so viele zu tyrrhenische drauf und das bedeutet für die Gesamtlaufzeit da eine da eine ob solche Album Augmentation Ofen Aufwand hat viele Gesamtaufwand einmal im Quadrat groß mit diesen einfachen kleinen Argumente mit dieser einfachen kleinen Einsicht dass habe habe ich jetzt hier nicht gelöscht dass wir die Kanten dass wir die Fluss in das werde ich auch mit ihren Operationen die die in die nur kann nur zu Not Fade erzeugen die länger sind als das was gerade aktuelle kürzest ist und mit dieser Argumentation dass wir in jedem in jedem argumentierenden Schritt eine Kante Viren und da die Länge jedes Mal strengen wachsen muss die Länge des kürzesten Weges der diese kann enthält weil er zwischendurch mal Sonne Operation passiert sein muss und danach darf die Länge des gesunde gewachsen von danach da sie gewachsen also können wir das nur so und so oftmal mit dieser könnte gemacht haben N mal mit dieser kannte infolge mal um genau zu sein also kann es nur 1 x 1 x mit unerkannte gemacht haben kann man nur einmal entweder Augmentation Schritt an das ist doch mal eine schöne Argumentation recht einleuchtend illustrativ man kann sich für den zeichnen oder man kann sie hat oder halt Jahr ich
fands ich habe fand schade ich hätt schade gefunden ich hin das jetzt nicht versucht den dazu bringen soll welchen gesagt hat also so sieht das ja aus er ist n Draft interessiert nicht weiter so was heißt das jetzt in dichten Netzwerken das heißt also wo fast jeder kann da vorne so Größenordnung wieder mögliche kann geworden ist wir haben wir haben wir bedeutet n mal im Quadrat das bedeutet ein Quadrat ist die ist so groß wie ein gerade würde das Willkommen auf von Enno 5 bei sehr dünnen Grafen die eigentlich sehr viel realistischer sind die sehr viel öfter in Anwendung vorkommen werden sich dann aber keiner an Grafen ich glaube ich schon mehrfach gesagt bei kann weil planaren Grafen ist ist am die kannten Zahl höchstens dreimal Knoten 2 minus 6 das heißt also wenn die das ist natürlich in O von allen das heißt bei planaren Grafen würde die Laufzeit rauslaufen auf in 3 Verkehrsnetze zum Beispiel sind keine kleineren Grafen als Brücken und Tunnel geht aber dass die kann natürlich er 3 in nur 6 plus Anzahl der Brücken und Tunnel salopp gesagt ok ich habe sich berücksichtigt das Eigentum der mehrere Straßen von mehr Straßen obendrüber geklärt werden könnte aber im aber letztendlich ist es ist es ja wie Hose so das dieser
Algorithmus jetzt fangen wir an zu spielen mit den Ideen die dahinter stecken oder neue Ideen zu entwickeln wünsche zu spielen mit den ganzen Ingredienzen die welche haben dass wenn wir heute nicht mehr weit kommen ich hätte mir überlegt es sollte vielleicht ein bisschen weiter comma war Soldaten er
hat halt nicht sein sollen aber das ist egal wichtig ist das wir ja das wir hier interessante Sachen sehen und ich hoffe dass es beim und hoffe ich ihn auch ein bisschen Spaß macht gut das ist richtig ja ob es nun genau bestimmten eine bestimmte Menge von Stoff in dieser Vorlesung in diesen in diesem Jahr schaffen ist in diesem Sinne zu schaffen ist nicht das entscheidende so da was ist die Idee hinter diese Hände dieser Variation die Idee dahinter ist wer wie was beim etwas Kap Algorithmus in jeder Iteration haben wir einen bezüglich kann seit kürzesten Weg gesucht mit breiten Suche und das heißt jedes Mal viele Iterationen müssen wir mit mit breiten Suche diesen Weg finden das kostet uns an verkannten viel Aufwand und wenn wir diese Krise Weg gefunden haben dann müssen wir da auf dem den Fluss auch mit ihren das kostet uns eine Anzahl Knoten viel Aufwand es eigentlich schade dass nur diese eigentliche diese diese 5 geschichte mit breiten so Rennfahrer zu finden das uns dass die Laufzeit so kaputt macht anstatt von ein Faktor von o von Einnahmen Faktor von von drin nominiert und super das was aber eigentlich die Musik spielt der Fluss Erhöhung wäre nur von allen und die Idee ist jetzt die breiten Suche zu vermeiden in dem man etwas tut was man meines 8 ist gut subsumieren kann oder ein Begriff den Sie aus völlig anderen Kontext Wahrscheinlichkeit nämlich lädt sie ihre jährlichen können Sie das von woanders her der okay was ist ein schönes Beispiel dafür ist dass ich ich war so sicher dass sie das kennen dass ich da jetzt nicht dass ich mir nichts vor dabei kein Beispiel aus meiner Kontext daher genommen haben es geht zum Beispiel um um Auswertung bei bei rekursiven über bei Sushi so rekursiven Sprache 7 G 1 gehen kann haben so Thema sparen so was bitte es eine große Rolle dass die Werte nicht so schnell wie möglich dann berechnet werden wie es geht wie alle für alle Inputs dafür nun immer vorhanden sondern wenn sie erst später wenn die werden wirklich gebraucht werden in vielen Situationen ist damit auf viel effizienter ich dachte das ist in der GT 3 so ein bisschen auch Einkommen bei Labour gilt ja okay gut also vielleicht ist es dann doch damit jeder die 3 bisschen einordnen wenn ich gucken Sie kommen sie nicht still bestimmte der Warschauer sogar das vom die DGB drin der englische Begriff lese iranischen da werden Sie bestimmt gute Beispiele finden mir fällt es leider leider weil ich mich da auch auf diesen Fall nicht vorbereitet habe sie sich kennen Alfeld ist kein gutes Beispiel ein so wir lösen uns jetzt von dieser starren statischen Sicht breiten Suche auch mit ihren breiten Suche auch kommentieren und fange an ein bisschen zu dynamisieren in denen wir jeden können Knoten eine Distanz Funktion eines das wär zuordnen der ja nicht gerne vergessen Sie mal bei Xtra und so weiter das ist jetzt hier vielleicht ein bisschen was andere ist mit diesen beiden Eigenschaften die Distanz und also es geht der geht Hintergedanke sie Distanz zum zum Ziel Knoten Distanz und das habe ich die des Tanzes sieglosen selber zu selber natürlich neue und wir haben eine Bedingung drehen die Ihnen vielleicht bekannt vorkommt aus dem war erfolgloseste Wege nämlich für jede Kante muss gelten mehr für jede kann muss gelten also hier und muss E und des von T ist gleich 0 haben wir gesagt und viele kann der VW muss gelten dass die Distanz von Frau und es ist es richtig und ja höchstens 1 mehr ist als die Distanz des Tanz wird von W so werden sie was soll das Ganze wenn Sie jetzt sich mal so den kürzesten Weg vergegenwärtigen also hier das schießt und sie brauche nicht mehr zu protestieren jetzt hat comma das Beispiel nicht mehr wenn wir wenn ganzen kürzesten Weg betrachten von S nach T was in den Instanzen so T auf diesen kürzesten Weg dieses dann von diesem Klon ist natürlich 0 die von dem es 1 1 2 3 4 5 6 7 8 das heißt also des von V ist gleich die von wie plus 1 jede kann der VW ja schlecht so wenn wir jetzt das Relax 4 zu einem kleinen Bereich für alle Knoten das das dass man sie was ich meine die dieser Knoten hier schleppt noch im alten Wert mit sich der vom alten wird der ist nicht nicht nicht abgedeckt weil wenn es die wenn das hier zum Beispiel die echte Distanz von zu T ist dann wäre das sicherlich den die echte Distanz da von V dahin aber der muss auch nicht aktuelle seiner die Idee diese Distanz Werte die sind nicht aber die die Linken in da ja teilweise das ist die Idee von diesem lese höllischen faul also morgen morgen ich heute also möglichst spät immer erst dann wenn sie gebraucht werden diese da müssen diese Werte stimmen auf diese Art und Weise wenn ich sehe noch wie das geht oder mal gucken was wir heute noch schaffen ansonsten beim nächsten Mal wenn man so so spart man sich die breiten suche man muss nur dafür sorgen dass es hin und wieder mal dann die Situation gibt die ich hier aufgezeichnet habe und dass man sie auch für den natürlich effizient finde dass man die Situation auch entdeckt das hier auf einem Pfad von es nach des das alles mit gleicher gilt immer dann wenn wir das gefunden haben da haben wir einen kürzesten Fahrt von es nach die nach also das klingt das ein bisschen wie Magie ich will aber versuchen ihnen ihnen zu zeigen dass das alles andere als Magie ist dass das Dinge sind die man verstehen kann die man dann am Ende langweilig findet auch ja für dich auch finden können so nach dem Motto natürlich hätte man sich finden können oder aber so was passiert hier vielleicht noch ein bisschen heute was zunächst mal
klarmachen müssen ist wenn wir solche dass das Leben haben dass die beiden Bedingungen dafür dass gültig wer lädt ein solches Tanzlehrling gültig Welt genannt wird zunächst einmal ist eine Distanz wert eines Knotens höchstens so groß wie die Länge eines kürzesten Weges von diesem Knoten nach die warum genau wegen dieser Sache ich brauche ich ersetze jetzt mal hierfür es durch V weil junge irgendein beliebigen Knoten V in dieser ob sehr welchen deren habe die 20 geht in dieser Eigenschaft Nummer 20 geht und wenn das nicht mit gleicher erfüllt ist ja wenn ihr Kleid für kleinere Werte stehen also hier zum Beispiel nur 1 jetzt ist nur 2 hier noch meine 2 hier nur 3 4 4 4 so wenn wir also hier ein kleiner gleiche machen dann ist das offensichtlich so also ich dass es im Verlauf aber eine eine Zahl die nicht größer ist als der Kürze des als die kürzeste Weg länger also Sie sie erstmals hat was damit zu tun mit den kürzesten Weg legen wenn auch relativ schwach nämlich dass das der eine wird nicht größer sein kann als der andere hat gut
an dieser Stelle denke ich machen wir Schluss die Zeit ist abgelaufen er mehr pünktlich gestartet in diesem Fall würde ich ihn auf jeden Fall gerade nochmal vor der nächsten Vorlesung sich noch mal das die vor anzuschauen die wir jetzt die letzten war wurden die wir jetzt betrachtet haben damit sie darin den Einstieg findest du diesmal wahrscheinlichen bisschen komplizierter sein als bei früheren Veranstaltungen der den Einstieg leicht wiederzufinden so dann möchte ich mich für
heute bei Ihnen bedanken
Loading...
Feedback
hidden