Ford Fulkerson Übungsaufgabe B0401

Gymfan,

ich versuche mal, es dir zu erklaeren.

nach dem ersten markierungsschritt folgt die flusserhoehung. in diesem fall geht die erhoehung den weg 0 1 3 6 mit 4 einheiten. am besten schreibt man sich das an den graphen. im 2. markierungsschritt kann der knoten 3 nur noch mit einer 4 markiert werden, weil ja durch schritt 1 schon 4 einheiten durchgeschickt werden und zwischen 1 und 3 duerfen maximal 8 durchlaufen.

war das halbwegs verstaendlich?

gruss, christine

Oh, vielen vielen vielen Dank!!!!!

Zu der Aufgabe und allgemein zu Ford-Fuklkerson hätte ich auch noch ein paar Fragen:

Bei der Aufgabe könnte ich die ersten Flusserhöhungen auch andere Wege abgehen. Gibt es eine vorgeschriebene Reihenfolge, so das nur die angegebene Tabelle korrekt ist?

Und bei B0402 verstehe ich auch nicht, warum in der Lösung bei Iterationsstufe 2 Knoten 3 noch nicht rückwärts markiert ist, dann aber in Iterationsstufe 3?

Bei moodle steht eine Aussage vom Lehrstuhl, dass die Reihenfolge bei Ford & Fulkerson egal ist. Hauptsache man bekommt die maximale Flusserhöhung raus. Aufgabe B0402 schau ich morgen mal nach, aber ich denke, dass es auch hier irrelevant ist, in welcher Reihenfolge man den Fluss erhöht

Puh....jetzt habe ich diese Aufgabe nochmals durchgerechnet, ganz ohne einen negativen Fluss und trotzdem mit gleicher Flussstärke von 8. Keine Ahnung ob das auch so richtig ist...lies am besten mal bei moodle im Forum...da wurde über diese Aufgabe auch diskutiert

ich frage mich gerade sowieso, was man davon hat, wenn man den Knoten 3 mit (4-,2) markiert.....

Wäre es möglich, dass wir hier einmal für die Algorithmen von Ford, Bellmann und Djikstra durchgehen. Welche Elemente in die Menge M hineinkommen und deren Vorgehensweise beschreiben?

Bei Djikstra ist die Menge M die Menge der untersuchten Knoten.
In jedem Iterationsschritt wird hier ein Knoten mit seinen Nachbarn untersucht.

Ist das korrekt, dass bei Bellmann auch mehrere Knoten gleichzeitig aus der Menge M untersucht werden können oder ist das auch immer nur einer?

Und wie das bei Ford. Gucke ich mir da zuerst einen Knoten an und packe in M alle Elemente die über eine Kante erreichbar sind und ordne diesen Distanzen zu? Dann betrachte ich wieder meinen Ausgangsknoten und berechne die Distanzen zu den Knoten die über genau zwei Kanten erreichbar sind usw...
In M wären dann also immer Elemente die über die gleiche Anzahl von Kanten erreichbar wären?