Seite 1 von 1

Übung 7.2 b)

Verfasst: 9. Feb 2009 16:39
von yourmaninamsterdam
Hallo,

hat irgendwer noch die musterhafte Lösung hierfür parat?

Wir haben gerade folgende Variante:
Man nimmt den Redisualgraphen mit nur Rückwärtskanten und berechnet die Distanzkabels d(v) für alle Überschussknoten v auf, ausgehend von s. Dann nimmt man die Überschussknoten v und pusht den Überschuss in beliebige Nachbarknoten, bis der Präfluss ein Fluss ist.
Die Komplexitätsbetrachtung dazu sagt: Wir haben höchstens n Überschussknoten und jeder Knoten hat höchstens n Nachbarn. Dann ist die Komplexität \(\mathcal{O}(n^2)\). Ist das nicht sogar besser als das geforderte \(\mathcal{O}(nm)\). Wo liegt der Haken?

Grüße
Artjom

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 17:01
von Arki
Die Pfade zu den Nachbarknoten sind aber nicht notwendigerweise eindeutig bestimmt. D.h. du pushst nicht einfach blind zu den Nachbarknoten, die auf einem Distanzlevel untendrunter liegen, sondern baust Pfade nach s auf, damit du weißt, wieviel überhaupt über einen solchen Pfad zurückfließen kann. Dabei gehst du im schlimmsten Fall alle Kanten einmal ab, womit du m. E. nach nicht mehr in \(O(n^2)\) sondern in \(O(nm)\) liegst. Korrigier mich bitte, wenn ich falsch liege... ;)

Grüße,
Markus

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 17:41
von yourmaninamsterdam
Die "Pfade" zur den Nachbarknoten sind schon eindeutig bestimmt, nämlich die direkte Kante...

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 18:05
von Arki
Naja du kannst ja nicht einfach mal blind den excess zu einem beliebigen Nachbarknoten w pushen, da du nicht weißt, wieviel throughput w - bzw. seine Nachfolger - hat (in Richtung s). Aus diesem Grund *musst* du Pfade zu s aufbauen (ausgehend von jedem excess node) da jeder dieser Pfade evtl. eine Kante hat, die den Rückfluss limitiert. Ergo: Die Pfade sind durch die bloße Wahl eines Nachbarknotens, der einen Distanzlayer unter dem des excess node liegt, nicht eindeutig bestimmt.

Wenn du das nicht tust, müsstest du deine Entscheidung, Fluss x einfach zu einem Nachbarknoten zu pushen, irgendwann revidieren, weil du über einen gegangen Pfad nicht den kompletten excess zurückgehen kannst. Du müsstest also ein vollständiges Flussproblem lösen - das wirst du nicht wollen. Oder kannst du garantieren, dass dieser Fall nicht eintritt?

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 18:14
von blowfish
angenommen wir pushen aus knoten w fluss in richtung v zurück. dieser fluss auf der kante (v,w) kommt ja ursprünglich aus dem knoten v, das heißt, dieser fluss ist ursprünglich von s nach v geflossen. also können wir ihn auch auf jeden fall von v nach s zurück pushen. wir müssen keine entscheidungen revidieren. falls du einen fehler in der argumentation findest, bitte ich dich des besseren versändnis wegen ein gegenbeispiel zu bringen. damit kannst du uns wohl am schnellsten und effektivsten überzeugen.

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 19:21
von Dreamdancer
Es kann sein, dass man eine Entscheidung revidieren muss, weil ein Knoten zwei Eingangspfade haben kann, diese sich wieder verästeln können etc. Wenn ein Knoten einen Überschuss von 500 hat, heißt das nicht, dass dieser von einen Pfad kommen muss und dass man diesen wieder über einen Pfad zurückschicken kann. Man muss meines Verständnisses nach also schon erstmal einen Pfad aufbauen um zu schauen, wieviel man zurückschicken kann, dann kann man die Werte erst ändern.
Man kann aber den ganzen Excess zurückschicken, wenn der EIngangsgrad des Knotens 1 ist, man deligiert die Aufgabe also an den Vorgängerknoten oder so.

Zudem kann man auf dem Pfad zurück auf einen weiteren Knoten mit Excess treffen, dieser akkumuliert sich dann :P

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 19:32
von yourmaninamsterdam
Hast du mal bitte ein konkretes Gegenbeispiel?

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 19:57
von Dreamdancer
Also es kommt drauf an, wie ich Euch verstehen soll.

Z.B. Graph G = (V,A) mit V = {s,v1,v2,v3,v4,t} und A = { (s,v1), (s,v2), (v1,v3), (v2,v3), (v3,v4), (v4,t }.

Der Max-PreFlow ist aufgebaut:
(s,v1): 5/5 [Flow/Kapazität]
(s,v2): 5/5
(v1,v3): 5/5
(v2,v3): 5/5
(v3,v4): 10/10
(v4,t): 2/2

v4 hat 8 Überschuss und kann es nicht einfach irgendwohin zurück pushen (auf EINEN Pfad).

Also sucht man einen Pfad nach s und schaut wie hoch die Rückkapazität ist und pushed das zurück, oder man deligiert das ganze an den Knoten 3, der dann den Überschuss zunächst übernimmt und in mehreren Schritten ( ZWEI Pfade) den Überschuss abbaut.

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 20:13
von Dreamdancer
Vorschlag:

- Distanzlabel durch BFS von s aus. Excess-Knoten werden in einen FIFO-Queue gesteckt: Also werden die, die am nächsten zu s sind, auch zuerst abgearbeitet. O(m+n)
- Solange Queue nicht leer: Nehme Knoten aus Queue und suche (kürzesten) Pfad im Residualgraphen nach s. O(n), da die Richtung durch die Distanzlabel schon gegeben ist (Traversiere nur von Level k nach Level k-1)
- Da es maximal n-1 Knoten geben können, die Excess haben, gilt O(n²)

Re: Übung 7.2 b)

Verfasst: 9. Feb 2009 21:22
von yourmaninamsterdam
Ich bin nicht überzeugt.
Dein Vorschlag für einen Algorithmus ist auch mit aller Sicherheit nicht korrekt: Zum Beispiel kannst du nicht immer den gesamten Überschuss über einen Pfad zurückschicken (wie du selbst schon angemerkt hast).

Hat zufällig irgendjemand noch parat, wie die Lösung in der Übung war?

Re: Übung 7.2 b)

Verfasst: 10. Feb 2009 10:08
von Stille
yourmaninamsterdam hat geschrieben:Ich bin nicht überzeugt.
Dein Vorschlag für einen Algorithmus ist auch mit aller Sicherheit nicht korrekt: Zum Beispiel kannst du nicht immer den gesamten Überschuss über einen Pfad zurückschicken (wie du selbst schon angemerkt hast).

Hat zufällig irgendjemand noch parat, wie die Lösung in der Übung war?
Im Prinzip nutzt man Flow Decomposition aus. Wähle Überschussknoten j und eingehende Kante (i,j) mit positivem Fluß. Danach sucht man vom Knoten i eine eingehende Kante (k,i) mit positivem Fluß, undsoweiter bis man entweder bei s ist oder einen gerichteten Kreis gefunden hat. Entlang dieses Pfades/Kreises kann man den Fluß soweit reduzieren bis eine Kante Fluß 0 hat. Das macht man solange bis alle Überschüsse abgebaut sind.