preflow push Algorithmus

[Becherer]

Könnte mir jemande, beim Preflow Push Algorithmus was erklären?

Das mit den aktiven Knoten und lift() habe ich verstanden,aber wie und wann fließt der Überschuss wieder in die Quelle zurück, wenn alle Wege zur Senke gesättigt sind?

Müssen die einzelnen aktiven Knoten in der Nähe der Quelle soweit geliftet werden, bis sie zur Quelle abfallen?

Meine Vermutung(hoffe es kann sie mir jemand bestätigen)
Nach der Prüfungsangabe vom Juni würde mir am Ende bei A ein Überschuss von +1 bleiben. Nach Algorithmus 19 im Skriptum würde dieser Überschuss solange zwischen A und B hin und herpendeln, bis einer der beiden Knoten die Höhe der Quelle übertrifft. Stimmt das?

Danke!

lg

[lordseppo13]

Könnte mir jemande, beim Preflow Push Algorithmus was erklären?

Das mit den aktiven Knoten und lift() habe ich verstanden,aber wie und wann fließt der Überschuss wieder in die Quelle zurück, wenn alle Wege zur Senke gesättigt sind?

Müssen die einzelnen aktiven Knoten in der Nähe der Quelle soweit geliftet werden, bis sie zur Quelle abfallen?

Meine Vermutung(hoffe es kann sie mir jemand bestätigen)
Nach der Prüfungsangabe vom Juni würde mir am Ende bei A ein Überschuss von +1 bleiben. Nach Algorithmus 19 im Skriptum würde dieser Überschuss solange zwischen A und B hin und herpendeln, bis einer der beiden Knoten die Höhe der Quelle übertrifft. Stimmt das?

Danke!

lg

seh ich genauso, bei dem einen Beispiel im Skriptum pendelt der Fluss staendig zwischen 3 Knoten hin und her, bis die Hoehe vom Knoten neben der Quelle um ein hoeher ist als die Hoehe der Quelle. Das wird nur in einem Schritt dargestellt.
Glaubts Ihr wird zum Test sowas wieder kommen? - Koennts Ihr die ganzen Lemmas etc., die sind ja teilweise etwas muehsam zu lernen. Ich hoffe, dass beim Test dann auch praktisch was zu machen ist und nicht nur Beweise.