Results 1 to 2 of 2

Thread: preflow push Algorithmus

  1. #1
    Elite Becherer's Avatar
    Join Date
    Oct 2002
    Posts
    406
    Thanks
    0
    Thanked 0 Times in 0 Posts

    preflow push Algorithmus

    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


  2. #2
    Hero
    Join Date
    Oct 2002
    Location
    Hamburg
    Posts
    239
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by 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
    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.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •