Ermitteln des maximalen Durchflusses vom minimalen s-t-Schnitt

Question

Es ist leicht, einen s-t-Schnitt mit minimaler Kapazität bei einem maximalen Durchfluss f zu erhalten, indem ein BFS von der Quelle des Restgraphen verwendet wird. Gibt es einen Algorithmus, um einen maximalen Fluss f zu erhalten, wenn eine minimale Kapazität s-t geschnitten wird?

Answer 1

Nein, im Grunde genommen. Das Problem ist, dass ein Min-Schnitt im Allgemeinen sehr wenig sagt. Bei einem Netzwerk ein neues Netzwerk bilden, indem ein neuer Arc von der Senke an einen neuen Knoten angehängt wird, der zur neuen Senke wird, wobei die Kapazität dem alten maximalen Fluss entspricht. Jetzt ist der minimale Schnitt nur dieser Bogen - keine Information über den Rest des Netzwerks.