Effiziente Algorithmen Übung 10.pdf

Assignments
Uploaded by Janik M 4868 at 2018-07-16
Description:

Ausführliche Mitschrift aller Lösungen aus der Übungsgruppe zu den Aufgaben des zehnten Übungsblatts.

 +2
143
3
Download
Ich verstehe hier bei der Aufgabe 2 nicht, wie ich den Netzwerk-Simplex-Algorithmus anwenden soll.. Es muss doch auf den Kanten ein Fluss gegeben sein..? Übersehe ich etwas? Kann mir jemand erklären wie man den Algo hier anwendet..? Danke!
den fluss kannst du selber bestimmen, indem du schaust das die flussbedingungen nach bestimmung des flusses erhalten bleiben (sprich das was rein geht, muss auch rausgehen). wenn du dann noch darauf achtest, dass auf nicht baumkanten kein fluss fliest, kannst du quasi rückwärts von knoten (a) aus beginnen fluss fließen zu lassen. bei (a) ist es nämlich eindeutig, da der fluss hier zunächst nur von knoten (r) aus fließt und daher 1 sein muss
No area was marked for this question
Aufgabe 2) Meiner Meinung nach birgt die Kante bh noch eine Kostenreduktion von -1 ? aktuelle Kosten: 11, über b: 10?
View 4 more comments
Deine Kante bh ist falsch rum, schau mal auf dem Aufgabenblatt nach ;) Die Richtung ist hb. Und dann gibt es noch keine Rückwärtskante bh, weil es auf hb keinen Fluss gibt.
so schnell kann's gehen, danke dir :)
Muss natürlich -1 sein, wie auch im nächsten Schritt wieder korrekt weitergemacht.