Minimale Kostenflüsse: Reduzierte Kantenkosten < 0?

[Arki]

In Übung 8 hatten wir uns in der 1. Aufgabe mit optimalen Knotenpotenzialen \(\pi(v)\) beschäftigt und den Graphen so transfomiert, dass der Fluss mit einem Maxflow-Algorithmus gefunden werden kann.

Wenn ich mich recht erinnere, dann gingen wir dabei so vor: Wir berechnen die reduzierten Kantenkosten \(c^{\pi}_{vw}\) in Bezug auf \(\pi\). In der Besprechung der Übung wurden die nachfolgenden Fälle durchgesprochen:
1. Fall: \(c^{\pi}_{vw} = 0\): Diese Kanten liegen im Fluss, die Frage ist, wieviel Fluss sie letzen Endes tragen werden.
2. Fall: \(c^{\pi}_{vw} > 0\): Diese Kanten liegen definitiv nicht im Fluss, also werden sie aus dem Graphen entfernt.
3. Fall: \(c^{\pi}_{vw} < 0\): Diese Kanten können direkt saturiert werden.

Meine Frage ist: Wie kann sich Fall 3 überhaupt ergeben? Ich habe mir dazu das Skript angeschaut und dort wird \(c^{\pi}_{vw} \ge 0\) festgehalten. Von negativen reduzierten Kantenkosten ist dort nicht die Rede. Wie kommt man also auf die Lösung?

Grüße,
Markus

[Stille]

Meine Frage ist: Wie kann sich Fall 3 überhaupt ergeben? Ich habe mir dazu das Skript angeschaut und dort wird \(c^{\pi}_{vw} \ge 0\) festgehalten. Von negativen reduzierten Kantenkosten ist dort nicht die Rede. Wie kommt man also auf die Lösung?

Niemand sonst?

Sie meinen sicherlich Theorem 91. \(c^{\pi}_{vw} \ge 0\) ist ein Optimalitätskriterium, keine allgemeine Aussage.

Reduzierte Kosten können durchaus negativ sein (vgl. Folie 218). Daher können die entsprechenden Kanten in Aufgabe 8.1 auch direkt saturiert werden.

[Stille]

Nachtrag: Letztlich entsprechen die oben von Ihnen genannten drei Fälle dem Optimalitätskriterium \(c^{\pi}_{vw} \ge 0\), denn
nehmen wir an, es gäbe Kanten mit der folgenden Eigenschaft:

1. Fall: \(c^{\pi}_{vw} = 0\): Diese Kanten sind kostenneutral und daher beliebig benutzbar, ohne die Gesamtkosten zu ändern.
2. Fall: \(c^{\pi}_{vw} > 0\): Diese Kanten würden bei Benutzung die Kosten erhöhen. Sie sind daher ungeeignet.
3. Fall: \(c^{\pi}_{vw} < 0\): Diese Kanten senken die Kosten. Sie werden folglich saturiert. Die entsprechenden Rückwärtskanten im Residualgraphen sind Typ-2-Kanten, da \(c^{\pi}_{vw} = -c^{\pi}_{wv}\).

Gäbe es folglich Typ-3-Kanten in einer Lösung, so wäre diese nicht optimal. Daher die Bedingung \(c^{\pi}_{vw} \ge 0\).

[Arki]

Danke für die Hilfestellung! Mir ist inzwischen klar geworden, wo bei der Sache mein Denkfehler gelegen hat .

[Siggi]

[edit] hat sich erledigt[/edit]

[marluwie]

Hallo!

Ich habe noch eine Frage zur dritten Möglichkeit die Kantenkosten positiv zu kriegen (Folie 217). Wenn es disjunkte Mengen S und V \ S gibt, die entweder von s oder \(\bar{s}\) erreichbar sind. Wie kann es dann Kanten (u, v) und (v, u) geben. Denn schließlich gibt es Gewichte für diese Kanten. Angenommen es sei ausreichend, dass S und V \ S von s oder \(\bar{s}\) erreichbar sind. Es kann also Knoten geben, die von beiden Startknoten erreichbar sind. Wie ist dann \(\pi(u)\) definiert, wenn u von s und \(\bar{s}\) erreichbar ist? Immer von \(\bar{s}\) aus ("\(\pi(u)\) have been set by shortest path distances from \(\bar{s}\)")? Durch die Addition von \(\bar{c}\) verfälschen wir doch das Ergebnis. Kommt das nicht einfach dem Ansatz gleich, dass ich auf alle Kantengewichte eine große Zahl addiere, so dass sie positiv werden? Ginge das dann nicht so einfacher ? (Die Antwort ist hoffentlich nein. Sonst kann das nämlich mit den negativen Zyklen auch gemacht werden)

[Stille]

Ja, die Antwort lautet "Nein", Gegenbeispiel wurde bei Johnson's Algorithmus gemacht: einfach zwei disjunkte s,t-Pfade, einer bestehend aus 2 Kanten, einer aus 3 Kanten, Kantengewichte jeweils -1. Kürzester Weg geht über den 3-Kanten-Pfad, nach der Addition der Kantengewichte mit großer Zahl jedoch nicht mehr.

Hier geht es ja darum, optimale Knotenpotentiale zu erhalten. Man betrachtet zuerst die Menge der von s aus erreichbaren Knoten, im zweiten Schritt dann die bisher noch nicht erreichten, usw.