September 2015
Intermediate to advanced
415 pages
12h 24m
German

Dieses Kapitel behandelt Verfahren zur Bestimmung von maximalen Flüssen in Netzwerken mit oberen Kapazitätsbeschränkungen. Zunächst werden die grundlegenden Resultate von Ford und Fulkerson bewiesen. Danach werden zwei Algorithmen zur Bestimmung von maximalen Flüssen vorgestellt. Der erste basiert auf Erweiterungswegen minimaler Länge, der zweite verwendet die Technik der blockierenden Flüsse. Für den Fall, dass die Kapazitäten 0 oder 1 sind, werden schärfere Komplexitätsabschätzungen angegeben. Im letzten Abschnitt werden kostenminimale Flüsse betrachtet. Anwendungen von Netzwerkalgorithmen werden im nächsten Kapitel ...