Seite 1 von 1

Maximum flows ist Spezialfall von minimum cost flows?

Verfasst: 9. Feb 2010 20:21
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?!

Re: Maximum flows ist Spezialfall von minimum cost flows?

Verfasst: 9. Feb 2010 20:51
von MisterD123
kann man das vllt mit negativen kosten als gewinn rechnen?

Re: Maximum flows ist Spezialfall von minimum cost flows?

Verfasst: 15. Feb 2010 23:23
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.