Maximum flows ist Spezialfall von minimum cost flows?

Moderator: Effiziente Graphenalgorithmen

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Maximum flows ist Spezialfall von minimum cost flows?

Beitrag von David »

Hallo,

auf Folie 169 steht, dass MaxFlow ein Spezialfall von MinCostFlow ist. Warum? Wenn man bei MinCostFlow die Kostenwerte weglässt, fällt die Minimierungsfunktion weg. Aber dadurch erfolgt noch keine Maximierung des Flusses, oder?!

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Maximum flows ist Spezialfall von minimum cost flows?

Beitrag von MisterD123 »

kann man das vllt mit negativen kosten als gewinn rechnen?

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

Re: Maximum flows ist Spezialfall von minimum cost flows?

Beitrag von Stille »

Guten Abend.

Ich hatte dieses Forum eigentlich abonniert und mich schon gewundert, daß keine Fragen mehr kommen. Gerade mehr oder weniger durch Zufall hier reingestolpert, und *schwupps* Fragen über Fragen. Ich werde mich auf dieses scheinbar schlecht funktionierende Feature in Zukunft wohl nicht mehr verlassen. Ohje, sieht nach einer Nachtschicht aus. Werde mich bemühen, alles noch zu beantworten, und hoffe, Sie sind noch wach ;-)

Also, MAX FLOW kann als Min COST FLOW modelliert werden, indem man alle Kantenkosten im Originalgraphen auf Null oder einen negativen Wert setzt. Die Quelle sendet nU Einheiten Fluß, die Senke absorbiert nU Einheiten. Nun muß noch gewährleistet werden, daß dieser Fluß auch tatsächlich fliessen kann. Das kann durch eine Dummykante von s nach t mit Kapazität nU und hohem Gewicht passieren. Der Wert eines MAX FLOW im Originalgraphen ist folglich nU - Fluß auf der Dummykante.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“