Übung 7.2 b)

Moderator: Effiziente Graphenalgorithmen

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Übung 7.2 b)

Beitrag 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

Benutzeravatar
Arki
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 15. Sep 2004 00:47
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 7.2 b)

Beitrag 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
Der Biber machts richtig: Nagt alles kaputt!

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Übung 7.2 b)

Beitrag von yourmaninamsterdam »

Die "Pfade" zur den Nachbarknoten sind schon eindeutig bestimmt, nämlich die direkte Kante...

Benutzeravatar
Arki
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 15. Sep 2004 00:47
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 7.2 b)

Beitrag 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?
Der Biber machts richtig: Nagt alles kaputt!

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Übung 7.2 b)

Beitrag 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.
Ein Hemd ist Einstellungssache!

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: Übung 7.2 b)

Beitrag 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

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Übung 7.2 b)

Beitrag von yourmaninamsterdam »

Hast du mal bitte ein konkretes Gegenbeispiel?

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: Übung 7.2 b)

Beitrag 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.

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: Übung 7.2 b)

Beitrag 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²)

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Übung 7.2 b)

Beitrag 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?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 7.2 b)

Beitrag 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.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“