Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
maximaler fluss (klausur 09/2002)
hi,
aufgabe 7 der o. g. klausur:
flussgraph gegeben, man soll die zerlegungen in schichten angeben und zu jeder zerlegung den engpassknoten und seinen durchfluss.
wir haben das zwar mal mit zerlegungen gemacht, aber da zaehlt doch dann, was insgesamt ueber die kante fliesst. wie soll es da also einen engpassknoten geben?
weiss jemand, wie das gemeint ist?
Also unser Übungsleiter, der diese Klausuraufgabe selber lösen musste, wusste auch nicht genau, was die Prüfer da hören wollten. Für uns meinte er, genügt es, wenn wir die Aufgabe mit Ford/Fulkerson? lösen können.
Also ich glaube das funktioniert so:
Man macht alle möglichen “Schnitte” durch den Graphen bei denen StartKnoten links und Endknoten rechts steht. Dann schaut man bei jedem Schnitt, welche Pfade von links nach rechts gehen und addiert ihre Kapazitäten. Das minimum dieser Summen ist der maximale Fluss.
Dann macht mans wie in der Übung: Pfad wählen, Minimum der Restkapazitäten der beteiligten Kanten von allen Restkapazitäten abziehen, gegebenenfalls (wenn Restkapazität = 0) Kanten löschen.
Wenn es keinen Pfad von Startknoten und Endknoten mehr gibt: Feddich.
Mit vorher berechnetem Max.Fluss vergleichen. Wenn sie gleich sind gut, wenn nicht ist irgendwo der Wurm drin und man muss andere Pfade wählen.
Ja das stimmt schon, aber unser Übungsleiter meinte er habe das auch schön auf mehr als einer DIN-A4 Seite so aufgemalt, hat aber trotzdem 0 Punkte eingefahren. Dass max. Fluss gleich dem min. Schnitt ist, ist korrekt 
???
??? das war auch seine Reaktion, aber das gehört hier wohl nicht her. Festzuhalten bleibt: Aufgabe mit Ford/… lösen und bingo
Also war das was ich oben geschrieben habe shcon ok, oder?
Ja sicher 
War eine Anekdote? des Übungsleiters.
So, hab mir die grade mal angeschaut.
Ich hab jetzt also 3 Wege zum Ziel:
- Intuitives Verfahren: bringt mich bei so einfachen Graphen sehr schnell ans Ziel.
- In Schichten (?) aufteilen: Ich betrachte alle möglichen Teilungen des Graphen mit S und T nicht in der selben Hälfte. Für jede Teilung wird die Kapazität aller Kanten vom S zum T Teil addiert. Das Minimum dieser Summen ist der maximale Fluss. (Jetzt selbst erklärt, sollte aber das gleiche sein wie oben).
- Einen einfachen Pfad von S nach T suchen und bei allen beteiligten Kanten die minimale Kapazität abziehen. So lange machen bis kein Pfad mehr existiert. Die Summe aller abgezogenen Werte ist der max. Fluss.
Aber was davon ist jetzt dieser Ford Fulkerson Algorithmus?
Letzterer, bei dem ist noch zu beachten, dass du die Kante, die die minimale Kapazität verursacht, entfernst. So entsteht irgendwann ein nicht mehr zusammenhängender Graph → Schluss Im Endeffekt hast du das so schon gesagt, wollts nur noch mal klarstellen. Du machst halt die aufstellung: fluss/kapazität/restkapazität an jeder kante, usw…
Aber dann kann es eben sein, dass man die Pfade in falscher Reihenfolge gegangen ist bzw ander Pfade nehmen hätte sollen.
Deshalb ist beim FordFulkerson Algorithmus die 1. Lösung nicht zwingend die richtige (ist bei den Lösungen von den Tafelübungen irgendwo mal ein Bsp dabei).
Ich glaube das nimmt man in Kauf, wenn man den Ford/… nimmt. Soweit ich weiss, kann es schon passieren, dass man nicht den max. Fluss erreicht, das liegt aber halt am Algorithmus, der besagt, wähle beliebigen Weg.
eine der algo2-übungen hatte doch so ein beispiel, wenn ich mich recht erinnere. da stand unser üb-leiter vorne und hat den falschen pfad gewählt. (wie poetisch…) jedenfalls kam dann was zu kleines raus. ich such’s mal
update: das muss in der übung 9 gewesen sein. aber ich hab jetzt mit beiden methoden jeweils im ersten anlauf 12 rausbekommen. (steht sogar irgendwo in der lösung, die ham da ja fast zig seiten für gebraucht!!)
Hi,
bei der klausur-aufgabe komm ich aber nie auf die richtige lösung!
der maximale fluß müsste doch 7 sein, ich komm aber maximal auf 5. :vogel:
die einzige möglichkeit den richtigen maximalen fluß zu erreichen hätte ich , wenn die kante d nach c umgekehrt wäre.
hat da jemand den richtigen wert rausbekommen? wenn ja, kann er den bitte mal posten?
gruss
DEvil
ich hab auch 5 raus, mit beiden hier erwähnten verfahren. sicher dass das nicht stimmt?
was wären denn die wege, mit denen man auf 7 kommen soll?
update: 2 möglichkeiten führen zur 5. hat jemand eine andere?
1:
s, a, c, t (4)
s, a, b, d, t (1)
2:
s, b, d, t (1)
s, b, c, t (1)
s, a, c, t (3)
wieso muesste der 7 sein? er ist 5, wie ihr richtig rausgefunden habt. am besten sieht man das mit der schnittmethode, bei der der schnitt, der den graphen in s,a,b,c und d,t teilt, minimal ist - und damit 5 der maximale fluss ist.
fyi, weitere flusswerte:
algo-übung 9: 12
klausur 9/2000, 8c) 12
so was geht mir gehoerig auf die eier! es stimmt schon, aber was ist das fuer ein algorithmus, bei dem man ein paar mal rumprobieren muss, um eventuell auf die richtige loesung zu kommen? das ist genauso wie die probabilistischen algorithmen, die wir glaube ich mal in TI hatten…
aber wenn ich so schneide, hab ich doch 9! ich muss doch die kante dc auch mitzählen, oder etwa nicht?
@Yves: 7 bekomme ich, wenn ich senkrecht durch die mitte schneide.