Network Flows II

Video thumbnail (Frame 0) Video thumbnail (Frame 6871) Video thumbnail (Frame 21906) Video thumbnail (Frame 29022) Video thumbnail (Frame 30729) Video thumbnail (Frame 32464) Video thumbnail (Frame 38592) Video thumbnail (Frame 47886) Video thumbnail (Frame 53141) Video thumbnail (Frame 62011) Video thumbnail (Frame 70705) Video thumbnail (Frame 75127) Video thumbnail (Frame 88384) Video thumbnail (Frame 100416) Video thumbnail (Frame 112448) Video thumbnail (Frame 114356) Video thumbnail (Frame 126469) Video thumbnail (Frame 128262)
Video in TIB AV-Portal: Network Flows II

Formal Metadata

Title
Network Flows II
Title of Series
Part Number
9
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 Constraint (mathematics) Maxima and minima Feasibility study Range (statistics) Insertion loss Kapazität <Mathematik> Variable (mathematics) Spring (hydrology) Fluid statics Vector space Supremum Summation Quote Conservation law Untere Schranke Matrix (mathematics) Flux Linear map Maß <Mathematik> Compact space
INTEGRAL Zirkulation <Strömungsmechanik> Graph (mathematics) Gradient Residue (complex analysis) Kapazität <Mathematik> Infinity Positional notation Minimalkostenflussproblem Graph (mathematics) Supremum Hill differential equation Vertex (graph theory) Summation Parallelen Length Untere Schranke Arc (geometry) Flux Directed graph Maß <Mathematik>
Kante Stress (mechanics) Zahl Graph (mathematics) Cycle (graph theory) Direction (geometry) Kapazität <Mathematik> Set (mathematics) Number Calculation Incidence algebra Function (mathematics) Graph (mathematics) Pauli exclusion principle IRIS-T Summierbarkeit Arc (geometry) Flux Maß <Mathematik>
Mass flow rate Chemical equation Graph (mathematics) Constraint (mathematics) Maxima and minima Angle Infinity Graph (mathematics) Uniqueness quantification Vertex (graph theory) Arc (geometry) Linear map Compact space INTEGRAL Zirkulation <Strömungsmechanik> Cycle (graph theory) Feasibility study Sign (mathematics) Positional notation Minimalkostenflussproblem Helmholtz decomposition Conservation law Matrix (mathematics) Maß <Mathematik> Group representation
Kante Sign (mathematics) Mass flow rate Chemical equation Helmholtz decomposition Uniqueness quantification Range (statistics) Vertex (graph theory) Set (mathematics) Maß <Mathematik> Group representation
Kante Stress (mechanics) Addition Sine Chemical equation Cycle (graph theory) Graph (mathematics) Desire path Incidence algebra Set (mathematics) Chain Positional notation Incidence algebra Graph (mathematics) Nichtlineares Gleichungssystem Vertex (graph theory) Untere Schranke Arc (geometry) Flux Directed graph
Kante Stress (mechanics) Zahl Mass flow rate Chemical equation Desire path Set (mathematics) Sign (mathematics) Logic Helmholtz decomposition Uniqueness quantification Vertex (graph theory) Group representation
Kante Sign (mathematics) Greatest element Mass flow rate Process (computing) Helmholtz decomposition Uniqueness quantification Iteration Summation Arc (geometry) Proof theory Group representation
Kante Stress (mechanics) Greatest element Mass flow rate Range (statistics) Mathematical induction Number Sign (mathematics) Field extension Helmholtz decomposition Uniqueness quantification Energy level Flux Group representation
Kante Stress (mechanics) Mass flow rate Graph (mathematics) Process (computing) Sign (mathematics) Iteration Network topology Helmholtz decomposition Cantor set Cloning Arc (geometry) Factorization
Kante Stress (mechanics) Mass flow rate Zirkulation <Strömungsmechanik> INTEGRAL Maxima and minima Parameter (computer programming) Kapazität <Mathematik> Boom barrier Spring (hydrology) Cost curve Helmholtz decomposition Summation Strömung Absolute value Maß <Mathematik>
Kante Stress (mechanics) Haar measure Mass flow rate Zirkulation <Strömungsmechanik> INTEGRAL Compass (drafting) Direction (geometry) Physical law Maxima and minima Mittelungsverfahren Kapazität <Mathematik> Integral element Leiste <Technik> Military rank Sign (mathematics) Sheaf (mathematics) Military operation Helmholtz decomposition Summation Musical ensemble Flux
Mass flow rate Process (computing) Graph (mathematics) Chemical equation Constraint (mathematics) Maxima and minima Infinity Incidence algebra Graph (mathematics) Uniqueness quantification Vertex (graph theory) Arc (geometry) Linear map Proof theory Compact space INTEGRAL Zirkulation <Strömungsmechanik> Cycle (graph theory) Residue (complex analysis) Feasibility study Sign (mathematics) Positional notation Minimalkostenflussproblem Function (mathematics) Sheaf (mathematics) Normed vector space Helmholtz decomposition Conservation law Matrix (mathematics) Flux Group representation
Kante Mass flow rate Maxima and minima Range (statistics) Set (mathematics) Kapazität <Mathematik> Canonical ensemble Infinity Partition (number theory) Subset Rand Supremum Quote Summation Gebiet <Mathematik> Untere Schranke Strömung Flux
Mass flow rate Weight
Kante Partition (number theory) Subset Mass flow rate Film editing IRIS-T Set (mathematics)
so genau sind die anderen immer so sein dass er verlängert werden an der TU Darmstadt so hallo
allerseits wir sind wieder zusammen ihr Wissen zusammengekommen um uns wieder dem Thema der Fluss Algorithmen zu man was über jetzt mal begonnen haben wir nahmen sich dieser Vorgabe das mal gesehen das ist die allgemeine Problemstellung Wir wollen einen statischen Fluss über statische für so betrachten dynamische Verluste die sich über die Zeit verändern Methoden dafür die basieren auch Methoden für statische Flüsse wie wärs aber jene Vorlesung bei statischen wissen lassen das heißt also dass der Fluss der eine kann den Graf im gerichteten Grafen geht nicht von der Zeit abhängig ist nicht mehr Zeit variiert sondern einfach zeitunabhängig da ist als eine Variable die nur mit der Kante von Ihnen nach J indiziert ist das sind die Fluss Erhaltungsbedingungen hier dass die für ihn als ein Knoten die Summe der ausgehenden Flüsse Minister eingehenden Flüsse das kann man sich immer gut wieso vorstellen wenn man für so einen Knoten die Kranken die reingehen vielleicht auf diese Seite malt und die kann die raus auf diese Seite malt was natürlich im Allgemeinen wird man das nicht so platzieren und nicht platzieren können das ist alles so in dieser Reihenfolge sondern über das Denken das mal ein Wohnhaus gegriffen und die Summe der Fluss werde die Summe der Kanten Werte x auf dem Rhein kannten betrachten wir die Summe auf den ausgehenden Karten jeweils für sich und jetzt sehen diese Summe von dieser Summe ab und was rauskommen soll ist ein spezieller wert der mich für diesen Knoten eine Balance wird denn wir haben darüber gesprochen Knoten bei den dieser Balance wert positiv ist das sind die bei den etwas ins System zusammen mit Quellen bei den in das ganze System irgendetwas herein hineinfließt und kann und Quoten bei dem dieser B wird aber was wird negativ sind senken bei den irgendwie der Fluss aus dem Netzwerk abgegriffen wird und nun bei den er dieser Balance mit 0 ist das ein Transfer Knoten die dienen nur dazu damit Flusstal durchfließt gebündelt wird und dann wieder verteilt wird so kann man sich das vorstellen wir haben allgemein natürlich obere Schranken Kapazitäten der Fluss doch eine gewisse Kapazität nicht vorschreiben die durch die Kante technisch vorgegeben ist wie bei Trachtler braucht immer auch den allgemeinen Fall dabei das einen das auch untere Schranken gibt dass also der Fluss ein Mindestmaß an wird auf jeder kannte kein spezifisch haben soll das ist in den meisten Anwendungen nicht relevant in manchen schon deshalb nehmen wir das mit aber oft genug betrachten wir den Fall dass die unteren Schranken alle 0 sind wie in den meisten Anwendungen der Fall ist so und das diese beiden Sätze von Bedingungen diese beiden Mengen von Bedingungen definieren was ein zulässiger Fluss ist um und unter allen zulässigen Flüssen wollen jetzt einen finden so wie wir unter allen fahren ein kürzesten führen wollen wollen wir hier unter allen zulässigen Flüssen einen finden der die Kosten minimiert was sind die Kosten für jede Kante haben wir so etwas wie ein Einheitskosten werden wir eine Einheit Fluss über die Kante von Ihnen nach J schicken dann kostet uns diese Einheit Fluss C Ort an Wert 1 Euro oder in Strom Verbrauch oder was immer jetzt der relevante Kosten gerade Kosten Dimension ist und wenn ich also XI und Einheiten insgesamt über die Kante i schicke dann heißt es die was es mich kostet diese XJ Einheiten über diese kannte ihr zu schicken ist gerade C J Exilort C hat die Kosten pro Einheit X X und einhalten ergibt Gesamtkosten die kannte und das aufsummiert über eine kann mehr gibt es die Gesamtkosten des Flusses im ganzen Netzwerk so das haben wir beim letzten
Mal schon betrachte diesen doch ein Stück weiter gegangen diese Punkte brauchen wir nicht noch mal zu
betrachten wie er haben das noch nicht begonnen den Rest Grafen oder im englischen vielleicht ein bisschen von dem mache oral Grafen also man jedoch im deutschen war Grafen manchmal vom Rest Grafen also die Klinke soll Graf besser nicht belassen wir's dabei so was ist das wir haben jetzt einen eine Grafen mit dem Fluss drin und wir betrachten uns eine einzelne kannte von irgend einem Knoten wiesen die hier genannt noch gar nicht machen wir gar keine Namen der ist von Ihnen nach J so dass der Knoten und das ist der Knoten J wir haben da drauf 3 Werte wir haben die untere Schranke als feste konstanten Wert wir haben die obere Schranke als festen konstanten wird die in Prozent für das Problem und wir haben jetzt einen Fluss den wir hier bisher immer mit XI J abgekürzt haben kürzen als auch aber diese 3 Werte haben wir jetzt da drauf wir haben als Input L und hat und wir haben jetzt irgendwo hier fällt vom Himmel her irgend Fluss wird ich sie und das ganze ist jetzt das ist natürlich ja für diese kann der sondern für alle kannten so was der Visual Graf jetzt daraus macht oder was wieder definiert ist ist die der ist die Idee vom Rest war Grafen ist jetzt zu modellieren wie viel flohst wert wie viel kann ich das hat noch nach oben treiben um wie viel Einheiten kann ich noch mehr dazu hinschicken oder wie viel Einheiten kann ich wieder zurücknehmen das ist natürlich klar wie viel das sind ich kann Jürgen des XJ Einheiten mehr aufbauten und ich kann ich XJ minus LJ Einheiten weniger draufpacken und also Grafen haben sie dieselben Knoten Sie haben also auch wieder ne und eine J diese kannte natürlich nur stellvertretend für alle anderen könnten Grafen für dieselbe Operation in gilt und sie ersetzen diese alle berichtet könnte durch 2 gerichtete kannten mit neuen Kapazitäten unter der Kapazität neue unwichtig ist die obere Kapazität O E J minus X I J und hier drauf setzen Sie die Kapazität X E Ort zu Minus L I J schauen wir mal nach das sollte jetzt genau das sein was ja auch irgendwo gleich steht die Kosten sind dieselben ja da sehen Sie ob hier sehen Sie hier OJ minus X I J und ich Sie haben es Elliott das sind die beiden Riesen waren Kapazitäten Restkapazitäten die übrig sind und die Idee dabei ist wir gucken uns wenn wir wenn wir mit diesen mittendrin in einem Algorithmus ja das ist das ist der das ist der Grund warum das betrachten also sehe ändern sich dann immer mal wieder wenn wir über betrachtet haben zum betrachtet mitten drin im Algorithmus was ist da los somit am Algorithmus haben wir solche Fluss ich sie hat die die Werte Mesurat Grafen wenn wir jetzt auf zu besolden offen über den der mir gar nicht mehr dem ursprünglichen Grafen arbeiten sollen das Übergreifen arbeiten und machen uns das Leben so viel einfacher wir können wir können hier Fluss Einheiten werden 6 ihr noch dazu packen ohne die Kapazitäten zu verletzen oder wir können weniger Fluss Einheiten als wir jetzt haben Fluss Einheiten reduzieren was wir dadurch ausdrücken können dass wir eben bis zu X dass er der Fluss Einheiten zur den Weg zurück nehmen lassen ja die die Idee ist die Fluss Einheiten X ihr Tier zu reduzieren sei ein neuer Einfluss zu kommen von diesem Fluss Ex-Sieger hat den abzudecken zu einem neuen vielleicht besseren Fluss in nicht in dem wir hier damit arbeiten der Flüsse hoch und runter zu setzen Fluss wird hoch und runter zu setzen sondern hier floss führt zu erhöhen wenn die also das ins geht bis zu dieser oberen Schranke bis zu dieser Karte also an Kapazität können wir das machen oder hier Fluss zu erhöhen bis zu dieser Schranke was bedeutet dass wir ich hier im ursprünglichen Grafen den Fluss werde ziehen dass Susan Fluss zurückschicken auf diese Art und Weise das ist ein Modell das sich vielleicht am Anfang ist man bisschen komisch aus aber wenn man es sich aber daran gewöhnt hat ist das sehr sehr praktisch so ist müssen uns noch über die Kosten dabei unterhalten am Ende geht es immer um die Kosten nicht auf der vorwärts kannte haben Sie die Kosten werden hier noch habe ich nicht dazu geschrieben die Kosten der den Kassen hat natürlich hier haben Sie die Kosten der CLJ und ihren Sinn Kosten werden minus 10 Grad das bedeutet wenn Sie hier eine Einfluss rüberschicken kostet diese Szene hat passt weil zurück ins ursprüngliche Modell würde das auch hier Erhöhung um 1 wenn Sie hier eine Fluss Einheit hingegen auf diesem rückwärts kannte drüber schicken kostet Sie das Minus Sieger das heißt sie gewinnen J passt weil das rüberschicken das zurückschicken von hier nach Yvonne Fluss Einheiten entspricht gerade den zurücknehmen von Fluss und damit dem zu den Wohnkosten hier auf der Seite also es nur 1 zu 1 Korrespondenz zwischen den 2 Modellen wenn Sie den Fluss auf diese Art und Weise hier geändert haben dass sie über tragen müssen Sie natürlich den war Graf entsprechend abbilden weil die Experten sich dadurch geändert haben natürlich nicht damit den alten ist werden weiter rechnen das passt nicht so jetzt Welt möcht ich dazu noch einen Punkt ansprechen nämlich wie kriege ich hier offensichtlich parallele kannten rein wir haben aber immer gesagt wir wollen keine Parallelen Karten haben beziehungsweise das stand er in den Folien ich habe gesagt mir ist es wurscht ob parallel kannten drin sind oder nicht warum ist mir das wurscht denn noch zurück zurück zu dem anderen Problemen was wir letztens betrachtet haben kürzesten Wege um was es hier mit parallelen kannten na ja wenn wir am kürzesten interessiert sind gucken wir uns an wie lang ist die könnte wie lange sie kannte und die Länge von beiden schmeißen daraus können wir können uns leisten wenn beide gleich lang sind schmeißen eine von den beiden kann aus ist egal welche nicht dass bei kürzesten Weg auf diese Art und Weise können wir ohne in allgemeiner davon ausgehen der kürzesten Wegen das wir keine Parallelen könnten haben hier Kinder natürlich wenn Sie einen Visual Grafen bauen wenn das Bild von eben hernehmen wenn der sich schon eine helle und eine rückwärts Kanther hatten im ursprünglichen Grafen zwischen E und J dann kriegen Sie jetzt natürlich 2 Parallele könnten jeweils raus mit dieser Konstruktion was ist hier zu sagen na ja die hat sie Wirkung ist beide die Kapazitäten an unter der die beiden ja wenn Sie 2 parallel Rohre haben diverse gewisse Kapazität für Wasser haben dann können Sie die beiden einfach gedanklich abstrakt betrachten als eine Uhr dessen virtuelle Kapazität die Summe der realen Kapazitäten ist also können auch hier mit parallelen kannten umgehen aber das ist dieser Punkt der dieser ist war darf keine Parallele kannten haben aber wir wir ignorieren dass sie können es ignorieren indem wir den Schritt machen diese Kapazitäten die beiden kannten zu einer zu vereinigen Kapazitäten zu addieren oder einfach zu tun als ob uns das Problem gar nichts anginge hier wenn diese dementieren müssen Sie natürlich damit Entwickler kommt das ist klar aber sein Gesicht implementieren solange man darüber nachdenken solange können wir so tun als ob das mit den parallelen kann das alles nicht angeht okay keine kann der soll Kapazitäten gleich 0 haben also wo beispielsweise der Fluss am oberen Anschlag ist dann ist das ja 0 Komma vergessen wo war kein Lust rüber schicken können könnte sich für so was schicken können was sollen wir das nur noch betrachten und genauso hier wenn wir wenn X am unteren Anschlag ist SX gleich J dann ist hier Visual Kapazität 0 können doch diese kann vergessen was wir uns damit ab plagen das ist das was diese Not hier gesagt
so viel essen Beispiele die Zahlen sind leider nicht so besonders groß aber ich hoffe Sie können es trotzdem lesen oder oder wenn sie es vielleicht ausgedruckt oder vom Recht am Rechner vor Augen haben können Sie kann sie rein Summen das ist ein Netzwerk hier sind es nur was der obere Kapazitäten aufgetragen unsere Kapazitäten sind alle 0 die untere schon sind alle neue deshalb haben wir in jeder einzeln könnte nur eine Zahl nur eine schwarze Zahl und Sie sehen hier alle Knoten das ist das das sehen sie nicht sondern das sage ich Ihnen die Knoten haben alle Balance 0 das heißt also sind reine Pflanzschnitt nannten Notz darunter geht nur Fluss durch hier haben sind im Beinhaus von plus 5 Jahren sehen wir uns vom wie das 5 das heißt also in diesen ganzen Netzwerk es besteht macht ein zulässiger Fluss das eine das er 5 Einheiten folgen diesen Knoten Lee ganz links zu diesem Knoten ganz rechts durch schickt er auf irgendeine Art und Weise sie erinnern sich wenn man jetzt mal gesehen die Balance Werte müssen damit das Ganze ein zulässiger Fluss überhaupt möglich ist müssen die Balance Werte aller Knoten sich zum 0 aufaddieren was in diesem Fall wirklich der Fall ist auch die sind alle 0 plus 5 plus minus 5 ergibt neue passt so und Sie sehen das ist ein relativ einfaches Beispiel wir haben 5 Einheiten auf einem einzigen Fahrt durchgecheckt das hätte natürlich ein bisschen komplizierter sein können das durch schicken aber das reicht hoffentlich alle um das Beispiel zu illustrieren so jetzt schauen Sie mal zum Beispiel auf diese können hier 10 ist die obere Kapazitäten 0 ist und dass das Ding geschrieben steht die untere Kapazität 5 Einheiten werden rüber geschickt das heißt Kapazitäten eine wie nie Einrichtung bis 5 oder jedes vielleicht noch ein bisschen deutlicher Weise unterschiedliche Kapazitäten dabei herauskommen diese Kante hiermit Gewicht 12 oder diese gar mit Gewicht 12 hat auch da werden 5 Einheiten am Fluss rüber geschickt das heißt die Visual Kapazität was noch im was noch mehr sein kann was man noch mehr Einfluss rüberschicken kann über diese Karte sind 7 Einheiten dass sie soll Kapazität immer Sure Grafen und um wie viel kann man Einfluss der Größe 5 mit 5 Fluss einhalten reduzieren natürlich um maximal 15 die Unterfranken 0 ist also hat diese rückwärts kann die hier die wir so eine Kapazität 5 so viel Fluss können wir und so viel kann man den Fluss hier reduzieren beziehungsweise war Grafen und so viel kann man den Einfluss zurückschicken und sie sehen vielleicht hier noch ein interessantes Beispiel hier auf diesen beiden kannten geht jeweils ist der Fluss jeweils am Anschlag das heißt also es ist keine diese kannte selber als vorwärts kannte 7 sogar Graf nicht drin weil er sie wäre mit war Kapazitäten drin macht keinen Sinn damit kann man nichts anfangen sie ist aber als rückwärts kann drin weil wir eben diese 5 alternden darüber gehen jederzeit Zeit und und die können das reduzieren sowie comma zurückschicken deshalb haben wenn Sie sich jetzt irgendeine kannte ansehen auf der gar keine Lust drauf ist dann ändert sich auf der nichts der denn sie können weiterhin nehmen Sie diese kann hier mit Kabel oder die sie mit Kapazität sehen sie können 10 Einheiten so viel wie diese Kapazität ist können Sie 10 Einheiten rüberschicken also haben Sie sie kann das vorwärts könnte man sogar Grafen da der Fluss darauf 0 ist können Sie nix zurückschicken oder schon ist auch 0 also gibt es keine nach rückwärts kannte so das ist das Konzept das ist war Grafen ich denke also von den Motivationslage ist vielleicht er momentan noch dürftig wozu man das Ganze braucht aber ich glaube vom Verständnis der was das eigentlich ist und wie das funktioniert und wie die Korrespondenz ist sollte hoffentlich scheinen ein 1. Lichtlein da sein so wir betrachten der 1. Satz sagtest Flüsse sind Attribute der Kanten Zahlen Attribute auf den Karten die die Fluss Haltungsbedingungen und die Kapazitäts- Bedingungen einhalten müssen wir werden das aber jetzt sehen
ich mache das mal gleich voll und ganz dass wir 2 ff komplementäre Sichtweisen dazu dazu haben einerseits diese Sichtweise wie wir sie bisher haben es gibt einen Fluss wird pro kannte eine dazu komplementäre Sichtweise ist wir haben eine gewisse Menge von verraten und Züge den Grafen und jeder dieser Faden jede dieser Züge hat seinen eigenen Fluss wird kx von P für den den Pfad P und kx von für den Zügel C und diese beiden Sichtweisen sind identisch sind 1 zu 1 wir werden wir werden jetzt in den nächsten Minuten sehen dass man das ineinander überführen kann beziehungsweise die Einrichtung steht schon hier nämlich wir gehen nachher gleich noch mal hierauf zurück ich glaube das ganze wird deutlicher wenn wir die andere Richtung uns mal
betrachten haben wie gehen
wir so dahin ignorieren Sie
erstmal mal der dem den 1. Satz der bezieht sich auf das was übersprungen haben nehmen Sie den zweiten Satz der mit Converse sie beginnt jeder nicht kann ich nicht ihrer nicht negative ab floh also das was sie bisher betrachtet haben ja in dem ein paar Bilder zu riechen zurück da das ist ein
relativ primitiver nicht negativer kannten ja sehr primitiv eigentlich nur eine Fahrt mit plus 5 Fluss Einheiten ist aber die Definition wo
ist die Definition hier die Definition
erlaubt natürlich beliebig komplizierter der Konstruktion Fluss Werte im Fluss werde es auf allen kann solange nur diese Bedingungen erfüllt sind so davon reden wir
als Abfindung der Tod wird hier kommen da noch hin
jeder solche was wir so kennen gelernt haben als plus X kann dargestellt werden durch einen Menge von Fahrten und Zyklen die so dass jeder Pfad und jeder Zyklus einen gewissen Fluss Wert trägt also was in Fahrt zügelloses wir nicht noch mal zu sagen aber was es heißt dass Einfluss wird trägt vielleicht ein einfaches Beispiel dazu so Sie haben hier sehr einfaches Beispiel bei wird plus 3 Balance wird minus 3 Jahren 7 0 hier haben sie 0 und jetzt wir natürlich farbige Kreide nicht schlecht ja Treffer Forum für 3 vor dem passt so vielleicht machen was ein bisschen komplizierte nicht wert 3 sondern wert 6 und sie haben einen Facharzt dem und dem sie eine Fluss Einheit zu sie haben einen zweiten fort zum wo dem ordnen Sie 2 Fluss Einheiten zu ja auf einen könnten beträgt dieser Frau der in dieser Pfad enthält trägt der 2 Fluss einhalten bei und Sie haben noch 1 3. Fahrt der 3 Fluss Einheiten dem wir 3 einhalten zu zuordnen so und was wir sagen können ist der Gesamt Fluss über jede Kante ist hier 1 Einfahrt der rote oder was es sein soll so rötliche der dem eine Fluss Inhalt zugeordnet wird hier auf der Kante das ist nur der gelbe Fahrt 2 Einheiten also diese kann Tier Fluss wir 2 diese kann Fluss wird 3 weil da 2 fallen sind einer mit wird 1 zu 1 mit der 2 die hat auch Fluss wird dabei und die hat Fluss wird 5 und wenn Sie das mal anschauen dann stellen Sie fest dass an jedem Knoten die Fluss Erhaltungs- Bedingung erfüllt ist ja kommen sich die beiden mittleren Knoten an eine rote Einheit 2 gelbe Einheiten General eine Route einer Zeugin über einhalten gehen aus kann gar nicht anders sein als das erfüllt ist genauso hier 2 gelbe 3 grüne Einheiten gehen rein 2 gelbe 3 grüne einhalten geben raus und hier so habe ich das Beispiel gerade gezeichnet 6 Einheiten gehen raus 1 2 und 3 und genau die kommen hier auch wieder an Ja das geht den Sinneswandel wovon hier überhaupt die Rede ist das wir auf der einen Seite können wir natürlich Einfluss so komponieren wie ich das jetzt eben gesagt habe das ist das was wir was ich jetzt erst einmal übersprungen hatte Doktor Doktor doch
war da ja sie haben sie haben
erst einmal hier jedem wir haben eine Menge von Fragen jeden dieser Pfade haben sie einen Fluss wird zu Worte das waren unsere werde 1 2 3 auf dem roten gelben und grünen fad sie haben hier die die Inzidenz der in die Inzidenz wird also wenn einer kandidiert auf dem vor P ist dann zählt das Städtchen Ahlens Komiker Symbole und werden sie wenn die kannte er hat nicht in ist dann steht ja eine 0 das heißt also was hier steht vergessen Sie mal diesen rechten Summanden hier erst mal diesen linken so man mir was hier steht ist das was ich versucht habe hier zeichnerisch darzustellen der rote und der gelbe und der geht es ging über diese kannte aber nicht der Grüne das heißt also dieses Geld also konnte gar Symbol ist 1 für die beiden das heißt die also die 2 wenn diese keine gezählt und 0 für diese kannte würden wir die 3 wird nicht gezählt so kommt das hier zustande März mit diesen Fragen die Fluss werde die 1 2 3 konnte gesehen 0 0 oder 1 je nachdem ob der Pfad über die Kante geht oder bei nicht oder nicht so jetzt habe ich aber noch die Züge warum das denn wir haben doch jetzt eben gesehen das lässt sich doch wunderbar so hier tja darstellen ja das ist aber natürlich nur eine einfache schöne suggestive Situation die gezeichnet habe wir müssen uns natürlich bewusst sein dass die Situation auch ein bisschen komplizierter sein kann period man die Situation ein klein wenig komplizierter so jetzt haben wir hier wir können das Leben einfacher machen wir auf jeder einzeln kann den Fluss wird von einst was bedeutet das in Fragen haben man halt das stimmt nicht was passt nicht hier muss natürlich bloß wird von 2 sein so einfach kann geht es jetzt auch nicht im Sinne des wird von 3 sein hier muss wissen Plus wird von 2 sein jetzt muss es oder jetzt passt es Sie geben 3 Reihen 3 raus Dreierreihen aus 2 3 1 raus zwar raus zwar rein und jetzt haben wir hier einen Vorrat von links nach rechts mit dem wird 1 wir haben noch einen vor von links nach rechts der kann hier nicht mehr weiter gehen das ist schon weg aber das ist der Fluss ist schon für erledigt ebenfalls mit dem wird 1 und was ist mit dem Rest hier ist das hier früher ist hier so sieht es aus wenn man enthusiastisch seine Vorlesungen so jetzt heißt hier ist Rest und Sie sehen das grüne was sich da schließt das Anzüge ebenfalls mit so wurden mehr als 1 ja also wir haben ja sie sehen wenn wir nur die Bedienung wie wie wie wie Flüsse definiert in Versailles Bedingung dann sind solche Situation natürlich absolut korrekt ja und Sie sehen das kann man nicht in Frage allein zerlegen sondern der Platten Züge übrig kann man sie kann sich drehen wenn sie wie Sie wollen ist auch durch aus möglicherweise erzwungen durch die unteren Schranken wenn die positiv sind in Mama dasselbe Bild wieder wenn wir zum Beispiel die ideelle Werte alle positiv sind 1 zum Beispiel dann werden was immer Einzelsieger Fluss ist er würde einen Zügel enthalten müssen geht gar nicht anders weil dann muss Fluss wird hier über diese Kante gehen und das konstituiert auf alle Fälle Fernzüge sie können sich hinstellen wie sie wollen es wird nicht ohne Zügel abgehen so und deshalb haben wir hier diesen zweiten Summanden der genau so strukturiert dass wir haben eine Menge von Fragen und eine Menge von zügeln die zusammen für jede kann der den Fluss wird er geben also wenn wir solche Menge von fahrenden Zügen haben sich das etwa hier dargestellt habe in diesem Beispiel dann konstituiert das einen ab floh einen Fluss wie wir ihn ursprünglich definiert haben so wie das eben gesagt haben wir zählen einfach alle flüsterte zusammen die grüne 1 und die gelbe 2 hier ergibt Fluss wird 3 und so weiter aber das spannende ist jetzt das umgekehrte bevor kommen hier ist noch mal
ein Beispiel dazu wer mit einem Beispiel hat gesehen gebrauchen dieses Beispiel nicht noch mal durchziehen ob das muss ich später gut muss ich spiele wo die Tastatur reinigen da weißer Kreide sieht man die Karte Spur nicht so aber bei in Kreide oh das ist doch hoffentlich nicht also ist ich hoffe einmal sehr das ist nicht aggressiv so kommen noch dazu
das Sparen ist die umgekehrte Aussage ab Converse wir gesehen wenn wir sone und sone Menge von fahren und Zyklen haben dann ergibt sich daraus automatisch Einfluss auf jeder kannte das ist das umgekehrte wenn wir einen arg floh haben einen Fluss auf das kann dann bloß Werte die einer der die gekapert nein die die Versailles Bedingungen erfüllt dann können wir den die komponieren und darum geht es hier in diesem kurzen Abschnitt wir können diesen Fluss des komponieren in so eine Kombination aus einer Menge von Fragen und einer Menge von zügeln und wir können noch mehr dazu sagen nämlich wir können die also in dem die Anzahl der Pfad und Züge beschränken die Behauptung des 1. Mal ist es nur eine Behauptung bisher die Behauptung ist das ist höchstens plus empfahl und Zügen gibt wenn die Anzahl der Kanten n die Anzahl der Knoten wie immer oh und also das werden für jeden blieben Fluss aus aus Wissens plus entfallen Cygwin komponieren können und von diesen endlos entfahren und Sie sind es höchstens Zyklen die dabei mitspielen das sieht ein bisschen kompliziert aus dieser Formulierung untergeht aber das kann man mit sich ja diese Formulierung existiert schon seit den sechziger Jahren so bis jetzt hat noch keiner in die die gefunden dass das zu verkürzen zu vereinfachen das geht wahrscheinlich auch nicht machen Sie sich klar das was was hier genau steht wir können diese an die Menge die Anzahl der Pfade plus Züge zusammen kann irgendwo zwischen 0 und 1 plus 1 sein aber egal wo sie zwischen 0 und 1 plus 1 ist die Zahl der Ziegel alleine muss zwischen 0 und sein ja also es kann durchaus sein dass wir plus NVA da haben dann haben wir nur Züge Zwangs läufig weil wir im entfallen Züge maximal haben werden wir hingegen weniger als als N Nordpolfahrer der haben dann wissen wir es kann nicht mehr im Plus fahren Züge geben weil die die Züge die zukommen können sind Wissens ja wenn sie zum Beispiel N halbe Pfade nur noch haben dann kann die Gesamtsumme der Pfade Züge höchstens noch Plus Inhalt ist ja das ist so die die zahlenmäßige Logik dahinter
so ich will versuchen die Ihnen damals
jetzt nicht anhalten Schritt für Schritt anhand der einzelnen Sätzen zu erklären sondern zeichnerisch zu erklären was da vor sich geht also anschaulich sie fahren mit irgend erkannte an von er nach J mit einem Fluss Wert größer 0 und Fluss könnten mit Fluss werden wohl sind praktisch gar nicht im Spiel interessiert sie nicht so jetzt gibt es an diesen Knoten hier 2 Möglichkeiten entweder Sie haben hier eine Senke oder nicht das haben Sie erwartet wenn ich wenn ich in so einfach wäre so wenn es keine Senke ist dann wissen Sie es geht muss auch mindestens eine weitere kann daraus gehen mit größerem All versah Bedingung einer Senke kann es sein muss es nicht sein genau so argumentiert es ist eine Quelle er trat was ich sage oder nicht wenn es keine Quelle ist da muss es ja auch wieder eine kann da reingehen Dinge Salons Würdigung die größer 0 der Fluss Wert hat und so können sie fortsetzen bis sie zur hier zu einer Quelle kommen er zu einer Senke Entschuldigung oder wo und wie sie hier zu einer Quelle kommen so lange wie die Argumentation auf jeden Fall wenn Sie das gefunden haben die es über größer 0 dann gucken Sie sich an welcher von die den hat in den kleinsten XI J wert das muss nicht der sein will die kann das ja mit der Sie angefangen haben es kann immer nur sein zum Beispiel die hier das ist die Kante vor dem Cranach L und die hat den kleinsten wert die Grenzen Fluss wird aktuelle was Sie jetzt machen ist für jede einzelne kannte reduzieren Sie den aktuellen Fluss wert um diesen minimalen Fluss wert und das ist ihr Fahrrad Jones sofort B ihres ihr erst ob fortbilden sie gefunden haben sie reduzieren das Ganze in den ganzen Fluss wir gerade ist um diesen wert und der Fluss wird von P den setzen sie auf dieses X K L haben den 1. Fahrt mit seinem zugeordnet wird gefunden und das machen sie so weiter nachdem Sie diesen 1. Fahrt gefunden haben von Irmgard Keller zu einer Senke reduzieren sie den Fluss Wert hier wird um das Minimum einer aktuellen Fluss Werte und machen man Leben mit dem mit dem Rest Fluss dennoch im gesamten Netzwerk übrig bleibt werden ja nicht nur von diesem Pfad das ist ja nur ein kleiner Pfad in dem großen Netzwerk wir machen das dasselbe noch mal und finden so eine Fahrt nach dem anderen so dass deren Summe dann für jeden für jede kannte den sein Fluss wird ergibt war warum terminierter das irgendwann warum es also um 1 zu Ende beachten Sie dass Sie hier der sich hier mindestens eine kannte den Fluss wird auf 0 erzählt habe das heißt in jedem einzelnen Iteration wo ich sein Fahrrad konstruiere wird einen bekommt eine Kante am Ende Fluss wird 0 das kann mit jeder kannte noch einmal passieren das heißt insgesamt Kanzleramt verkannten oft überhaupt diese Operation passieren so ist das Bild so weit erstmal klar und das ist nun ist es Ihnen noch nicht so klar die jedoch Fach sind wenn es also nicht so richtig klar aber dann wenn ihnen das nicht klar ist dann müssten sie aber alle aufschreien es gibt 2 Flüge in diesem Bild also besser gesagt ich wir in dem man sich das so gesagt habe 2 zusammen etwas vornehmer wir müssen an 2 Stellen noch das Modell etwas erweitern ich weiß nicht wer von ihnen jetzt erst ok das ist der 1. Punkt irgendwo muss ja mal die Zyklen Netz ins Spiel kommen werden
Sie so wie wir jetzt eben gesagt haben mit und erkannte ihr beginnen und sie gehen voran dann kann es sein das sie nie auf eine Seng gestoßen sondern das ist immer weiter und weiter und weiter und weiter geht hier Invisible zufällig gegangen sind aber da gab endlich ist wenn ist wenn es immer weiter und weiter und weiter geht's da muss es irgendwo Zügen das kann so aussehen dass wir wieder bei ihren kommen es kann aber auch anders aussehen nur ich das ein bisschen weiter nach links von Elli nach J so es kann so aussehen das wir hier innen drin zu einem Zyklus kommen also die Ursprungs kann muss nicht in den Zyklus enthalten sein aber da haben wir wieder ein Zyklus gefunden derselben Eigenschaften ja wir können wir können auf allen Kanten um denselben wird reduzieren dass unser Zyklus C jetzt hier ist das Minimum vielleicht bei der wieder bei der kann davon kann nach L und wir setzen den Wert des Zyklus auf x K L unter 10 dass den Fluss entlang dieses Zyklus um es gar so machen wir weiter sogar mit Zügen und dabei ins Spiel auch hier wieder das Argument dass kann nicht beliebig häufig sein weil wir jedes Mal mindestens eine Kante bei einer auf einer Karte den Fluss auf 0 runter wenn ich da wo dieses Minimum angenommen wird so das war die 1. Liebe die wird aufgelöst haben also von dem die 1. Modelle Erweiterung die wir machen mussten was es weiter die die Balance werden müssen ohne beachtet werden es kann genau es kann sein dass hier er oder sein und so der beiden benannt wird es kann sein dass hier das was aus der Quelle mehr rauskommt als reingeht oder auch hier weiter sinke was mehr reinkommt als rausgeht dass das größte das ist meine Stellung das kleiner ist als als der minimale wert eines Flusses hier dann sollten wir natürlich nur so viel reduzieren dass diese Quelle oder diese senke das da die Balance 0 wird ja mehr sollten wir mehr sollten wir das nicht reduzieren brauchen wir auch nicht so und wenn wir das jetzt noch mal zusammen sammeln wie oft kann es uns passieren mit diesem Bild wie oft kann es uns passieren dass wir uns hier befinden und und anderen dieses sind unsozial maximal so häufig wie es kannten geht denn jeder denn jedes Mal wenn wir seien Sie befinden reduzieren auf jeden Fall eine solche Kante auf 0 den Fluss Wert und damit ist schon das hier gesehen oder wie The Most einen 2. hat man sie sehr flau wir können höchstens er mal an seine kann mal häufig auf einem Zügel diese Operation durchführen so und wenn wir das jetzt hier alles zusammenrechnen jedes Mal jedes Mal wenn wir diese Operation durch egal zu den Zügen oder zum Fahrt führt entweder geht der Fluss wird einer Kante auf 0 oder einer der beiden entknoten des Übergangs getroffen worden wie häufig kann eine Kante auf 0 gehen also illegal in wohl wie häufig kann es passieren so oft wie kann gibt also mal die Marter wie häufig kann es passieren dass die Balance bei über einem Knoten auf 0 geht und na das ist jetzt bei Ihnen nun noch einmal passieren kann wir sind daher vorsichtig wir so wie wir eigentlich wurden in Balance ist er ist das gehen kann betreiben will dem nicht mehr viel sinke das kann es doch passieren Knoten gibt N wie Nordpol mal und damit haben was Wissens bloß einmal kann können wir eine dieser beiden Operation ausführen und gerngesehen höchstens einmal kann diese Operation aus was hinter dem Beweis steckt ist natürlich eine relativ einfache vollständige Induktion eine verschenkt Sohn über die Anzahl der Kanten die positiven Fluss vertragen plus die Anzahl der Knoten die Quelle oder sinken sind eine von diesen beiden Zahlen reduzieren wir in jedem Schritt mindestens eine von diesen beiden Zahlen und damit ist die Induktion Voraussetzung anwendbar wir können davon ausgehen dass der Rest nachdem wir diesen Pfad oder diesen Züge daraus genommen haben dass der sich ebenfalls so in Fahrt und zügelte komponiert ist das ist die mathematische Beweis Struktur dahinter ich wurde so schwer oder ich finde so anschaulich aber gut ich habe schon seit 20 Jahren damit zu tun
über soll diesmal anschaulich okay also das ist das was wir hier allen so wortreich formuliert worden ist nicht im Grunde nichts anderes als das was ich da gesagt
habe so fürs die Kompositionen kann man in dieser Zeit tun warum nein Ja wir gehen hier davon aus dass der für das denke der Graph zusammenhängend ist das heißt die Marter die unsere kannten es müssen so groß wie N wie Nordpol also methodisch die Anzahl der Knoten so wie hier wir können höchstens also also was hier letztendlich steht ist etwas komplizierter aber dafür präziser gefasst seit 23 Jahren vorhanden mal plus entsteht ja eigentlich wobei aber wenn wir wenn der Graph zusammenhängend ist dann ist wissen Sie mindestens N minus 1 1 müssen sparen Baum drin so dass also das dann gleich so von allen mal das was hier oben steht so warum warum ist das so wir können plus einmal dieser Schritt tun einem Fahrt oder entzücke identifizieren wie viel Aufwand kostet uns das pro Operation na ja was kostet das und so einen Fahrt oder so einen Züge zu finden mehr gehen wir gehen von Ober- und wodurch und wenn wir das 1. Mal wieder einen Knoten gefunden haben denn mir schon mal gehört haben können wir auch wenn wir uns über gefunden ja das heißt also in dieser Operation egal ob es am Ende auf einen Züge oder aufs Einfahrt hinausläuft fassen wir jeden einzelnen Knoten nur einmal an wir fahren irgendwo beliebig an der der 1. Klonen alles der der oder die 1. Kantine in Unna ist der von von Kanten mit Fluss wird größer 0 und von der gegen die irgendwie immer weiter das kann es höchstens nach allen Schritten asymptotisch haben wir die Situation geklärt sind wir auf beiden Seiten meiner Quelle und Senke oder an den beschlossen daher kommt der 1. Faktor das Ende da hinein da das hier ist auch eine
unmittelbare Folgerung haben Sie an sich was eine Strömung ist eines Sieger erreichen das ist der Fall wenn der Balance wird über alle 0 ist das heißt also jeder Knoten sein Durchgangs Noten pflegen und Geld rein gehend der Fluss ist gleich raus und was es gibt keine Quellen keine senden das heißt also die Situation wie wir sie hier halten das wir ausgehend von irgend mehr kannte rückwärts zu einer Quelle und vorbeizulassen gekommen kann gar nicht auftreten das heißt also es kann die eine Situation auftreten dass wir in den Zügel reinlaufen und deshalb ist eine Strömung nicht repräsentiert durch fahren Züge sondern nur durch durchzieht da habe ich jetzt noch meine
Vorbereitung nachgedacht kann er keine Sorge ich bin der Meinung in diesem Fall das Corolla stimmt ich bin mir aber nicht sicher ob man das wirklich als Corolla aus dem bisherigen Gesagten folgern kann sondern ich will Ihnen sagen wie ich es folgern würde und ihnen sagen warum und an welcher Stelle meine Folgerung jetzt eben über das was Sie jetzt gesagt haben hinausgeht vielleicht finden Sie auch wieder flicken kann sie auch wieder mein Job machen mein Gehalt ich beziehen aber mein Job machen und und mir zeigen dass es doch tatsächlich eine Folgerung aus dem bisher Gesagten ist dass ich da irgend eine Möglichkeit übersehen haben so war steht hier erst einmal die Kostenfunktion glaube ich brauchen kann die die brauchen gar nicht integral zu sein nenne ich bin mir sicher die baulichen egal zu sein aber wenn die Kapazität des oben ohne Schranken ganzzahlig sind dann gibt es sogar eine nur minimalen Kosten Fluss der ebenfalls ganzheitliches dessen x-Werte wird auf jeder kannte ganzzahlig ist das ist insofern ganz praktisch weinen wenn sie wissen dass ihnen das in Iran in ihrer Anwendung die Imports alle ganzzahlig sind ja Sie haben ganz Kapazitäten in diskreten Einheiten in dem er irgendwie gemessen dann brauchen Sie keinen damit zu reservieren hilflos werde seien Sie kein Interesse mehr für die Fluss wird und wissen das wird klappen so warum geht das ich glaube was wir eigentlich stehen soll die das was sie eigentlich stehen sollte ist falls die Kapazitäten und die Balance dann geht für mich auf die werden sollte müssen ganzzahlig sein die Kosten des nicht ganz so ich sein so das zeigen Ihnen jetzt warum ich dass dieser Meinung bin so Sie haben jetzt bekannte des deren Fluss Wert also von Ihnen nach J der Einfluss Wert XII Ort ist nicht ganzzahlig das gebrochenes Augen hat und welche Nachkommastellen so die Cuthbert die oben und und Schranken und die Balance werde sind aber alle ganzzahlig so wenn hier J ganz ganzzahlig ist dann heißt das doch dass diese nicht ganzzahlig kalt das ist nicht die einzige Karte ist an der am Knoten J die den Fluss wird nicht ganz so leicht ist ja das gebe ich es gar sämtliche anderen kannten die reingehen und sämtliche anderen könnten die rausgehen wenn die eine ganzzahlige Fluss werde hätten oder eine nicht oder ganzrandig das geht nicht das passt nicht es muss also mindestens eine weitere Kante geben die rausgeht oder die reingeht die einen nicht ganzzahligen Wert hat zum Beispiel eine ausgehende also hier sollte er nicht sein solle und meldet sich keiner ist egal ist damals es gerne so manchen weitere rausgehen kann das sein die nicht ganzzahlig ist machen wir mal diesen einfachen Fall durch das ist analog zu dem was wir jetzt bisher betrachtet haben auch hier wieder selber Arguments und so weiter bisher vielleicht zu einer Senke kommen und hier das selbe aber selber Argument bis wir zu einer Quelle kommen hier ist nicht aus Z alles nicht ganzzahlig ja wir können wir können argumentieren es gibt immer eine Kante an diesen wurden deren Fluss wird ebenfalls nicht ganz einig ist so was wir in diesem einfachen mal machen können ist mein bisschen den werden zu rütteln mal plus Epsilon über darauf setzen auf jeder dieser kannte unter X minus erzielen auf nehmen an den einfachen Fall Entschuldigung dass da bin ich jetzt schon einen Schritt weiter in den einfachen Fall ist es sogar noch noch einfacher Teil als ich das jetzt vor der allgemeinen zu betrachten in dem einfachen Fall setzte über eine ein wenn es Epsilon runter auf jeder dieser kannten und haben die Kosten reduziert flinkes am Fluss weil wir wir haben denn es gibt haben endlich mal halt halt halt so das kann ja nicht sein das Argument geht dennoch weiter das halbe Schürung bekommen gar nicht bis zur Senkung des mehr Quelle sondern wir kommen immer es schließt sich garantiert ein Züge schön da habe ich hierzu kurzgeschlossen wenn Sie jene kann haben nicht ausgeführt dann können Sie immer weiter und immer weiter gehen bis sich Züge schließt der diese kann den Erhalt oder wie wir es eben gesehen hatten der vielleicht immer so aussieht dass Sie hier beginnen und dort irgendwo zu schließlich der Zwickel aber Betrag wir mal die Situation hier ist über alle nicht Element aus Z und so weiter ja so die Kosten Werte können größer oder kleiner 0 sein deshalb machen wir folgendes wir erhöhen über einmal den Fluss wird um Epsilon das ist ein alternativer Fluss dem Rabbi rauskriegen so das und das ist ein alternatives y und einmal von wir über einen Fluss wird um Epsilon ausreichen klein so wenn jetzt die Summe der Fluss größer 0 ist die Summe Türen der Summe der Kosten werde größer 0 ist dann ist dieser 2. Fluss wo wir Umerziehung verringert haben besser als aus ganz los kann also das ganze es keine minimaler Fluss kostenlos gewesen sein Widerspruch wir hingegen die Summe der Kosten Werte auf diesen kannten
hier insgesamt kleiner 0 ist dann kriegen wir einen besseren Fluss raus in dem wir hier plo über plus Epsilon aufsetzen den Fluss in den Gesamt Fluss auf diesen Zügen um erhöhen kann also der Ursprungs Schluss wieder keine Minimalkosten fürs gewesen sein Widerspruch wenn hingegen die Summe der Kosten Werte 3. Fall wenn hingegen die Summe Kosten werden 0 ist auf auf diesem Zettel die Kosten werde einzeln kannten dann können wir mit plus Erzählungen oder minus y darf könne nichts ändern Einfluss wird am Gesamt Fluss am Gesamtkosten der des Flusses ja egal welches y wir und Durchsetzung der höheren welche selbst wir verhindern dadurch dass das dieser Zyklus sozusagen kostenneutral ist ändert sich nichts daran in dem Fall können aber selbst lachen so groß zu so groß setzen das sind ja alles werde es unendlich viele Werte die nicht ganz so einig sind und bei endlich vielen werde nicht ganz einig sind kann selbst so groß so setzen gerade so groß setzen dass der 1. dieser werde ganzzahlig und und damit ist die Anzahl seiner Argumentation eben die Anzahl der Kanten die der Einfluss werde nicht ganzzahlig ist ist um 1 vermindert worden und das Essen das ersetzen wir fort es müssen starker Tobak vielleicht aber dafür die man das ganze auf dass sie sich das Ganze noch mal nachträglich wich mir sagen wir was haben lassen ändern anderthalb Fallgeschwindigkeit billig erträglich dass sich das nachträglich noch mal na dann versuchen den Kopf gehen zu lassen auf die Art und Weise wenn wir selbst können wickelte wir sind ist es und so groß gerade so groß die Kante die am nächsten deren Fluss wird am nächsten so Ganzheitlichkeit ist gerade ganz ich würde und dies den ganz ich die die Krim dick taucht dann in weiteren Operation dieser Art in den nächsten Schritt nicht mehr auf so warum sage ich jetzt gesagt dieses Corolla wie ich mir nicht sicher ob es wirklich ein Chorleiter aus ist warum weil ich die ganze Zeit hier mit einer vereinfachten Situationen gearbeitet habe es kann ja auch folgendes sie fahren an mit einer Kante deren Fluss wird nicht ganz so ist wir stellen fest vielleicht eine rausgehen kann sie es auch nicht ganz so eilig aber stellen fest dass sich alle rausgehen kann man ganzzahlige Werte wie das die Balance ist ganz traurig das kann man nur sein dass einen dahingehenden kannten nicht ganzzahligen Wert hat jetzt geht es rückwärts vielleicht nochmal Schritte rückwärts wir stellen fest alle reingehen Kranken in sind haben ganzzahlige wenn diese so normal da muss eine andere rausgehen erkannte nicht ganzzahligen wird haben und so weiter und so fort ich meine Mann ist so ja mal wieder die Situation so ja sie sehen also wir haben es nicht mehr mit dem Zügel img im eigentlichen Sinne zu tun sondern mit einem sie wieder vorwärts und rückwärts kannten enthalten kann was machen wir hier die Operation nur plus minus etwa Plusminus Epsilon hier Minus Plus erzielt worden hier wieder Plusminus erzählen das ist richtig haben und hier minus plus erzielen also genau umgedreht wenn wir auf diesen kann den Fluss und mehr zu einer höheren vermindern Serie um Epsilon und wenn wir die und dann sollen wir wieder hier und wenn man dann in die Haare wenn wir das so machen dann bleibt die Fluss aber Haltungsbedingungen bestehenden den wenn sich die 4 verschiedenen Fälle mal angucken was da passieren kann sie haben den 1. volle 2 vorwärts könnten wo sie jeweils um Epsilon 1 alle anderen Karten diesen Knoten berühren bleiben gleich man vor dem für Haltungsbedingungen gegolten hat geht sie in der auch ja die Summe der ausgehenden erhöht sich um y die Summe der aus genau für sie somit der reingehen versöhnt sich im y bleibe die Balance und bestellen das wäre wenn sie rückwärtsgehen hier um Apps von Männern hier hiermit Land vermindern bleibt das gleiche wenn Sie jetzt die Situation haben um es und erhöhen und über den zu nach rückwärts könnte mehr vermindern dann ändert sich an der Summe der rausgehen für gar nichts aber auch weil die gar nicht hier berührt sind ich diese Operation und bei der Summe der eingehen kann er ändert sich auch nichts weil diese wurde reingehen Flüsse wird einmal Umerziehung erhöhten einmal mehr unvermindert bleibt gleich und genau das dasselbe in der letzten ob Situation ja mal minus Epsilon mein plus selbst hören die Summe der reingehen kannten Flüsse ändert sich nicht weil sie gar nicht oder wenn es wird keine einzige kann eigene keine berührt bei diesen Knoten hier und die Summe der rausgehen und ändert sich auch nicht weil die Summe der ausgehen Flüsse hier um y erhöht wird und hier und es vermindert wird die Flüsse Haltungsbedingungen bleibt bei allen diesen Operationen egal wie genau die Konstellation ist an dieser und enthalten und damit entlang des Zügels auch enthalten bleibt erhalten so und jetzt selber Argumentation jetzt sehen wir die so mehr der Kosten ein bisschen anders nämlich für die vorwärts kannten auf diesen Züge vielmehr die Kosten positiv und das kann will mir sehr negativ so jetzt können wir den Fluss
einmal die obere Leiste hier plus plus plus minus minus plus bloß minus minus Fluss erhöhen hier auf dem Vorwurf Fluss vermindern auf den rückwärts kannten das ist die Züge Richtung Fluss vermindert auf den Ringplatz könnten werden die Gesamtkosten werde so gerechnet vor vor kann positiv vielleicht auf bringt kann negiert wenn die diese Summe negativ ist hat sich dadurch dass es ganz um den Epsilon erhöhen der Kosten wird verbessert verringert Widerspruch dann war das womit wir gestartet sind keine Minimalkosten Kosten aus genauso umgekehrt jetzt nehmen wir die das untere vor Vorzeichen auf den vorwärts kannten vermindern wir den Fluss auf dem rückwärts kannten erhöhen wir den Fluss wenn die die Summe der Kosten Werte anerkannten auf diesen Zirkel so gerechnet vor kann positiv gerechnet zurück was kann negativ gerechnet die Kosten wenn die was kommt jetzt wenn die das hat mir eben wenn die negativer jetzt wenn sie positiv ist da der das so einen besseren Fluss in dieser zweiten Version wieder ein Widerspruch völlig spiele sie Mittel zum 1. Frage der dritte Fall ist wieder dass dieser Fluss das schön dass dieser Tüte kostenneutral ist ja also ich kann hier um Apps die Summe der Kosten Werte vorwärts kannten die Kosten werde positiv gerechnet kann die Kosten werden negativ gerechnet und alles zusammen addiert ergibt 0 da kann ich umerziehen an den Fluss in die Ränge richten wie Einrichtung für ändern es ändert sich nichts an den Kosten der das Gesamtkosten Fluss ist dann kann ich wieder wie eben den Fluss wird umso ein Ärzte und verändern das gerade so eben eine irgendeine dieser kannten der dass der Einfluss der ganzheitlich wird dann ist diese kann aus dem Spiel heraus und ich kann mit dem Rest Fluss der übriggeblieben ist weitermachen kann ein Züge nachdem alle anderen einsetzen so lange bis alle ganzzahlig sind und hat immer kostenneutral geändert egal wenn ich bin ich nicht in Widerspruch laufe Sie diese Änderung kostenneutral das heißt ich habe am Ende einen minimalen Kosten Fluss der nicht ganzzahlige Koch kannten Flüsse enthält überführt in einen minimalen Kosten Fluss der nur ganzzahlige kannten für enthält weil ich in jedem also dieser Schritte einzügigen indizieren Fluss darauf verhindern indem dieser Schritte habe ich eine Kante mit nicht ganz sein kann wie es eine Kanne mit ganz anderen was gemacht und Koks weitere Migration nicht mehr an bei ich immer nur man kann dann gucke deren deren kann sie nicht ganz so ist so und wegen dieser vorwärts und rückwärts Geschichte sagen wir mal so es ist ist es gewagt etwa finde ich von einem Chor Law zu den bisherigen zu sprechen sie sehen wie lange das gedauert hat das zu argumentieren und wie weit ich da über diese Flut dick und besitzen der sie werden dass Apps die Frage war wie wählen Sie ja seit wann genau ich wiederhole die Fragen immer damit damit dass auch auf dem Band ist die sie werden das Erzielung gerade so man das mal ganz konkret immer doch mal ganz konkretes Beispiel vielleicht wird es dann irgendwie klar machen wir mal nen ganz ein kurzes Beispiel nur so und die Fluss Werte hier drauf sind zum Beispiel 0 comma decimal 9 0 comma decimal 2 0 comma decimal 8 0 comma decimal 3 so wenn sie wenn das die Richtung des Zügels ist also die beiden Werte horizontalen sind die vorwärts die beiden werden kann sind rückwärts kannten und dann wäre 0 comma decimal 1 die richtige Wahl dass sie den Fluss ich hier entlang erhöhen dann wird nämlich diese Kante ganzzahlig wenn Sie wenn Sie hier auf den Beinen vor riskanten also Plus 0 comma decimal 1 plus 0 comma decimal 1 minus 0 comma decimal 1 4 auch minus 0 comma decimal 1 damit diese kann die oben ganzzahlig uns umsonst bleibt alles so in seinen Bereich oder sie sagen minus 0 comma decimal 2 das heißt also sie sie ziehen hier 0 comma decimal 2 ab sie ziehen hier 0 comma decimal 2 ab 17 hier 0 comma decimal 2 ab und hier nur 0 comma decimal 2 damit diese Kante ganzzahlig also nehmen wenn sich dafür entscheiden zu addieren dann gucken sich welche dieser Werte ist nach oben zu sagen die Gerhard die geringste Aufrundung nötig um ganz zu kommen und wenn sie wenn sie Fluss reduzieren kommen sich an welche kann hat die geringste Abrundung nötig um ganz wahr zu werden gute Frage die Frage war das Protokoll was passiert wenn sie den Fluss nicht reduzieren dürfen weil die oben und unten schauen das nicht zulassen dafür steht diese Vorbedingungen der Körper City der werden die Kapazitäten DLJ und die jetzt in die Greisin ganzzahlig sind und der für Fluss wird auch das nicht ganz ehrlich ist wieder oberen und Anschlag ja also hier das sich dass sich ein ätzt dass ich die Existenz eines etwas größer 0 angenommen habe was ich in untergeschoben habe bis jetzt endlich mal jemand gefragt hat er das resultiert aus dieser Vorbedingungen dass die Kapazitäten ganzzahlig sind also wie gesagt die kostenlose müssen nicht ganzzahlig sein die Balance Werte müssen auch ganzzahlig sein sonst lässt sich das natürlich nicht würde sie an das werde ich ganz heißen dann können Sie mir denn ganz Einfluss nicht die nicht alle Knoten benannt in das geht nicht so gut warum ist das jetzt hier an dieser Stelle habe mir den Esther
vor schon eingeführt die wir noch mal zurück zu
das wir jetzt nix überspringen
Annotationen ohne den vorher schon
eingeführt ich hiervon nur an der
viel für Fluss eines der Fluss sollte nicht vor Fluss eingeführt worden sein ihr nicht
hier nicht hier nicht
mehr eines der Fluss wurde früher mal
eingeführt aber wo wurde jetzt nochmal Einfluss eingeführt das wirklich nicht es egal vergessen sie dass wir
kommen mit sowieso zum Thema ein eine
maximale Flüsse maximale Flüsse war ende ab so jetzt recht
ja maximal für Sie kennen Sie vielleicht aus der geht so das ist ein Spezialfall davon die Situation ist die ich suche mal nach einem Bild war da nicht im Bild natürlich nicht
okay kein Bild maximal Flüsse
Was ist das sind wir wie gewohnt dass sich Grafen so als große Kreise zeichne davon werde ich jetzt abweichen beim Thema maximale Flüsse von jetzt an den Grafen solche spitz zulaufenden Flaum so S und C oder sie können auch als was anders interpretieren ich bitte nun stubenrein Interpretation so muss natürlich nicht so aus sehen Sie können sich vorstellen dass der dass es in Wirklichkeit so aussieht die habe um den Grafen platziert und irgendwo ist das so dann muss ist weg aber es ist natürlich bequem das so zu zeichnen das S und T an an den beiden Rändern des Bildes liegen und was die jetzt wollen ist Fluss von hier nach hier durch das Netzwerk durchzuschicken alle Knoten hier drinnen haben Balance werden 0 sind also reine Transfer Knoten hier wollen Sie maximal 4 Fluss durch schicken im raus aus dieser Quelle rausschicken der dann hier entsprechend mit demselben wert ankommt ja wir wir noch sehen dass das tatsächlich so ist das ist das was Sie hier rausschicken auch hier ankommen würde zwangsläufig so also mehr fahren jetzt ne Menge nicht stubenrein Interpretation einen aber das lassen mal nochmaliger so also die Situation das 1. Mal klar ich die Wahl der belastetes das 0 verdient wunderlich also nicht erst der gesehen Sommer raus minus rein das heißt der Netto Fluss wert der aber es raus geht soll möglichst groß werden und dasselbe soll weil es bei reingehen wir werden sehen dass es automatisch immer so dass was bei es rausgeht geht bei die halt umgekehrt und diesen Fluss Ärzte besser reingeht wollen wir maximieren und und wir wollen jetzt keine untere Schranken 0 haben der Einfachheit halber und obere Schranken hat irgendwelche wird so ist wird hier behauptet ob Surf also eine einfache Beobachtung das maximale für ein Spezialfall vermieden und Kosten sind das auch tatsächlich relativ einfacher Observation dazu zeich nicht das ganze vielleicht noch mal ein klein bisschen exzentrischer warum ist dieses maximale Fluss Problem dass sie vielleicht das Gebiet so Kennenlernabend IS-Milizen kennenlernt der von Dieners genannt ok Summe für die 1. macht nichts wenn sie nicht in der Hand haben so ich meines ganzen bisschen exzentrischer das ist jetzt der Graf mit so mit es hier und hier hier soll der Fluss durch geschickt werden warum ist das minimale Kosten Problemen weil sie könne oder sie ganz verdutzt auf einfache Art und Weise reduzieren darauf sie fügen hier eine Kante einen Fontänen ist zurück und sagen die Kante diese diese kann der hat Fluss wert minus 1 als schön Kosten werden es 1 alle anderen kann hier drin wir haben kosten wird gleich 0 und die Balance Werte von und von T sind auch gleich 0 von den niedrigen sowieso so das bedeutet das was Sie hier durch schicken von erst nach T beides haben Balance wird 0 das geht jetzt alles über diese kann der wieder zurück ja eine Strömung geschlossen und hier mehr über diese rote kannte fließt weil der Kosten wird negativ ist je mehr über diese rote kann fließt umso besser ist der da ist der kosten wird ja wir sagten es Kosten negativ sein müssen wir jedenfalls hier nicht deshalb lässt sich das Problem reduzieren auf einen Kuss Problem ist dass sie ein Rhythmus für vor für die Problemstellung für allgemein Problemstellen gewisse betrachtet dann kann auch gleichzeitig das machst Problem lösen was insofern mit Kanonen auf Spatzen schießen heißt weil es effizientere Algorithmen speziell für Marxloh gibt aber verziehen begoß Valognes so handhaben und sie sind sie sind sofort da was anderes implementieren in der die Zeit dann hauen Sie einfach mit dem begrüßt worden und muss drauf und fertig in dem sie die Karte einfügen und dann er dann eben man verfolgen muss an den ok ist noch jetzt noch eine andere mehr was besagt diese Annahme wir hatten gegen Ende des letzten Mal es gesagt manchmal zweckmäßig auch Kapazitäten und den in einen schönen Tag einen unendliche Kapazität zu geben ja um auszudrücken dass auf diesen kannten keine Kapazitätsbeschränkungen es dass so viel lieber fließen kann sie wie man hat will aber wenn wir jetzt nimmt vor haben von S durch den Grafen hindurch nach C und das über die obere Kapazität unendlich es ist ganz natürlich witzlos er dann ist unendlich der Fluss wird der der optimale Fluss wird also gerne also die mit dass Diebe diese Instanz ist unbeschränkt anbauen und beschränkt gut wir können das natürlich vorher schnell feststellen ob es um den Pfad gibt in dem wir von S aus kannten betrachten wir gucken von S aus zu welchen anderen Knoten kommen wir wenn wir nur kannten hernehmen die die unbeschränkte Kapazität haben und wenn T zu den Kanten der Entwicklung gehört die wir damit erreicht haben dann dann gibt es so ein Pfad und den nicht dazu wird in gibt es keinen Fahrt bis sich in längere Zeit nannte der Knoten sofort finden na gut wenn man die Kanten wirklich durch muss um die geht um diejenigen kann mit mit unendlicher Kapazität zu wenn wenn man die nicht gleich zur Verfügung hat für nicht gleich zur Hand hat welche kannten davon er davon unendliche Kapazität haben die von diesen Quoten ausgehen dann ist es vielleicht etwas voreilig zu sagen dass von NRW weil er eine Anzahl der Kronen kannten es ist garantiert so nett
Führung das Wort Netz heißt ja im Englischen nicht nett sondern nett vage Netz was immer was das heißt das ist das deutsche Lehnwort netto die gehen Sie kennen das das NET fordert das wird und das Naturprodukt wissen Sie dann noch zufällig noch was Brutto heißt auf Englisch na wer wohl war schon auf dem Austauschjahr oder so was groß G R O S S in kann was fordert oder so etwas Produkt es ist nicht weiter wichtig so wir haben jetzt nicht mehr viel Zeit wir der wir gehen jetzt hier vielleicht ein bisschen
darüber worum geht es Ich sage ich jetzt einfach
mal nur worum es das Ganze jetzt geht worauf
das Ganze hinauslaufen würde und in die Details steigen wir beim nächsten Mal dann wieder ein so wir haben es hier mit wieder unserem Grafen und was uns interessiert sind es solche Gebilde denen sich Cat Schnitt oh die wo kann also so wo kann rüber gehen also eine Menge von Knoten hier und einer Novelle von Kommunen ja die eine Menge enthält es ja mal man enthält C und wo wir feststellen Netto was hier Netto rübergeht von links nach rechts Natur heißt das wird was wirklich Einfluss werden von links nach rechts rüber geht minus das was über rückwärts kannten zurückfließt in dem Sinne Netto das Erbringen von Netto es ist egal welchen Schnittfläche ziehen immer dieser Fluss Wert F der aus es raus geht jetzt ja auch im Schnitt mit den Kanten den Sie dann zuerst sind und jetzt auch ein Schild mit den kann man sie dann zu T sind über jeden einzeln Schnitt ist das die Idee ist dass der Fluss wert und das ist der geht der Fluss wird insgesamt als Netto Fluss von links nach rechts durch und das wiederum wird uns dazu führen am Ende das das was maximal rüber fließen kann von es noch die durch das Netzwerk durch beschränktes und zwar exakt beschränkt ist durch durch die kleinste Durchlässigkeit durch die der kleinste Kapazität eines solchen Schnitt das und exakt heißt dass der maximale Fluss Wert tatsächlich identisch ist mit der minimalen Kapazität von allen diesen schnitten die die hier drin sind so dass wir also in zu was vor allem bedeutet wenn er und was ein praktisch bedeutet wenn wir werden Fluss Algorithmen kennen diese Probleme lösen und damit kriegen wir dann auch automatisch mit ein bisschen Zusatzarbeit aber überschaubar Zusatzarbeit auch einen minimalen Schnitt raus ein sei ein Bad in der kein Flaschenhals so damit sind wir für heute am Ende des Details wie gesagt dann beim nächsten Mal freute mich mich bedanken
Loading...
Feedback
hidden