Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Theoretische Informatik - Flüsse und Flussnetzwerke #1
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 38 Zeilen
- Hallo und herzlich willkommen zurück zur theoretischen Informatik. Weiter geht es mit Grafen oder genauer gesagt mit Flussnetzwerken. Ja, das ist jetzt mehr oder weniger ein neues
- Thema und ich habe die letzten Videos ja schon zu Grafen gemacht. Ihr kennt auch Grafenkantengewichte schon. Also diese, sagen wir mal, hier haben wir ein Kantengewicht von 10. Upsala, da wollte ich
- kein Enter reinkauen. Ja, das sind dann die Kantengewichte gewesen und was jetzt neu dazu gekommen ist, ein Graf kann eine Quelle, das ist der Punkt hier, und eine Senke, das ist
- dieser Punkt hier, oft Q und S oder S und T abgekürzt, genannt, ja genau. Ja, und was bei einem Fluss so besonders ist, es gibt eine Richtung, also eine Richtung von der Quelle zu
- der Senke. Nicht auf direkten Weg, sondern über diese ganzen Knoten hier in der Mitte über diese fünf. Und ja, ein Fluss ist dann eben ein, also auf dieser Kante ist jeweils noch eine weitere
- Funktion definiert und diese Funktion nennt sich dann eben Fluss. Also in einem Flussnetzwerk gibt es diese neue Funktion Fluss genannt und die muss ein paar Bedingungen erfüllen. Für Quelle und für
- Senke gilt das jetzt gerade nicht, was ich sagen möchte, aber für alle anderen gilt es und zwar, was reinkommt, muss auch wieder raus. Das heißt, ich bekomme hier über diese Kante, also stellt
- euch vor, das hier ist irgendein Meer oder eine Quelle, wo aus dem Boden Wasser fließt und das hier ist das Meer, wo es rein fließt. So, inzwischen drin kann sich die Quelle aufteilen in mehrere
- Flüsse und jeder Fluss hat halt nur eine gewisse Kapazität, bevor er überläuft. Und wir in der theoretischen Informatik, wir sagen einfach, okay, ein Fluss darf nicht überlaufen, weil sonst haben
- wir ein Problem, sonst verlieren wir was. Wir wollen ja alles haben, also am Schluss hier an der Senke. Also das heißt, ein Fluss kann nicht überlaufen. Das heißt schon mal für uns, hier auf
- den Kanten können wir nicht mehr Fluss haben, als wir Kapazität haben. Das heißt, die zehn von zehn ist hier das Maximum, die 15 von 15 hier ist das Maximum, aber die 1 von 20 ist hier
- definitiv nicht das Maximum. Dann fließt eben dieses Wasser hier auf diesen Flussbetten entlang und hier gibt es dann halt wieder eine Gabelung. Was wichtig ist bei diesen Gabelungen, die habe
- ich jetzt gerade nur so genannt, die wird euer Prof wahrscheinlich nicht so nennen, alles was rein läuft, muss auch wieder rauslaufen und es darf nicht mehr rauslaufen, also es kommt kein neues
- Wasser dazu, sonst wäre es ja wieder eine neue Quelle, mehr oder weniger, also jetzt in Natur gesehen. Und ja, hier muss noch eine Null davor. Das bedeutet, wir geben hier von der Quelle eins,
- obwohl wir 20 transportieren könnten, hier runter und hier spaltet sich der Fluss und gibt hier eins nach da weiter und von hier fließt genau eins, nicht null und nicht zwei, sondern genau eins
- weiter in die Senke. So die Senke kann so viel verkraften, wie sie möchte und die Quelle kann so viel spucken, wie sie möchte. Aber alle anderen Knoten zwischendrin, der hier muss genau diese
- zehn von hier und diese Null von hier und diese Null von hier wieder ausgeben, der hat nur eine Möglichkeit, deswegen geht er nach hier und der hier muss auch genau diese 15, also nicht 16 und
- nicht 14, sondern genau 15 muss er auf entweder dieser Kante oder dieser Kante hier weiter transportieren. Auf welcher Kante, das kann er sich aussuchen. Aber man muss natürlich aufpassen,
- dass wenn ich jetzt hier, sagen wir mal, ich würde die 15 oder ich habe ja nur eine Kapazität von 10, aber ich würde die 10 da transportieren, diese Kante hier hat das Problem, sie kann nur 15,
- ja dieser Knoten, diese Kante hier hat natürlich das Problem, hier kann ich maximal 15 transportieren, jetzt kriege ich aber 10 hier rein und 10 hier rein. Das heißt, es kann so nicht funktionieren,
- der Fluss ist nicht gültig und deswegen muss man sich natürlich dann immer überlegen, wo lang fließt dieser Fluss. Ja und hier fließt natürlich dann 25 wieder, denn ich kriege hier
- 10 rein und hier 15 rein. Ich könnte natürlich auch die 25 hier lang fließen lassen und dann da lang, aber das ist eigentlich relativ wurscht. Also noch mal kurz zusammengefasst,
- auf einer Kante darf maximal so viel Fluss fließen, wie die Kapazität ist, also diese Zahl rechts ist die Kapazität, die Zahl links ist der Fluss. So und mindestens 0, also Minus, kann nicht fließen.
- Der Fluss darf allerdings auf einer Kante, Moment ich zeige es euch gerade, auf so einer Kante hier darf tatsächlich Fluss fließen. Also hier könnt ihr jetzt zum Beispiel 10 von 10, wenn ich jetzt
- hier noch 10 reinkriegen würde, dann müsste ich hier 11 haben. So hätte sich der Fluss quasi nicht verändert, denn hier fließen 11 rein, hier fließen 10 wieder zurück und 1 fließt weiter nach hier.
- Die kann auch so viel aufnehmen, wie sie möchte. Das wäre tatsächlich auch möglich. Ja und dann kommen wir zur nächsten Definition, das wäre dann der Wert des Flusses. Da addiert man einfach
- alles, was aus der Quelle rausgeht, minus dem, was in die Quelle reingeht. Also in dem Fluss aktuell gerade 11, das geht ja raus, plus noch mal 10, das geht ja auch raus, plus noch mal 15,
- geht auch raus, minus die 10, die wir hier wieder reinbekommen. Das heißt, wir haben einen Wert von 11 plus 10 plus 15 minus 10, also 26. So und jetzt fällt euch wahrscheinlich etwas auf,
- nämlich genau dieser selbe Wert von diesem Fluss geht auch in die Quelle wieder rein, denn wir müssen ja alles, was wir hier angenommen haben, müssen wir entweder wieder zur Quelle
- leiten oder wir müssen es zur Senke leiten und bei der Senke kommt dann natürlich alles rein. Das heißt, hier können wir auch einfach alles zusammenzählen, was reinläuft. Also 1 plus 25
- ist wieder 26. So ja und zwischendrin wird einfach irgendwie weitergeleitet. Genau und da geht es dann halt haufenweise Algorithmen, die sich beschäftigen, wie man denn da diesen Fluss
- optimieren kann und möglichst viel von der Quelle bis zur Senke pumpen kann. Das wird zum Beispiel auch in der Wirtschaft benutzt, wenn man jetzt, also sagen wir mal, wir haben Transportwege,
- Wege von, also sagen wir mal die Ölpipeline von Russland nach Deutschland. So die läuft erstmal über, keine Ahnung, Polen wahrscheinlich und ja dann leiten wir natürlich auch noch ein
- bisschen was nach Frankreich weiter und dann sagen wir mal, ist Frankreich die Senke von Frankreich geht es nicht mehr weiter. Mal ganz abgesehen davon, dass wir was verbrauchen,
- das lassen wir mal ganz außen vor. Wir haben eine Kapazität von Russland nach Polen und von Russland nach Deutschland direkt von jeweils 25 und von Deutschland nach Polen von 10 und von Polen nach
- Frankreich von 100 oder sowas und dann kann man da eben maximieren, dass beim Frankreich möglichst viel ankommt. Also das war jetzt ein relativ einfaches Beispiel, in der Praxis ist es natürlich
- noch deutlich komplizierter als das, was ich hier hingemalt habe. Ja, aber da gibt es schöne Algorithmen und die möchte ich euch in den kommenden Videos eben vorstellen. Also es hat
- durchaus praktischen Nutzen, auch für sogar andere Themen, die man gar nicht erwarten würde, die ich dann euch auch noch zeigen kann. Okay, dann bis zum nächsten Mal und macht's gut. Ciao, ciao.
Zum Nachlesen
Theoretische InformatikIhre Inhalte sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeits- und Komplexitätstheorie, aber auch die Logik und formale …
OnlineDer Anglizismus online (['ɔnlain]; deutsch „Zugang zum Internet“, „im Netzwerk“) bezeichnet in der Informatik einen Zustand, in dem ein Gerät, das über eine …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …