Viele Probleme in der Informatik können durch ein Diagramm dargestellt werden, das aus Knoten und Verknüpfungen besteht. Beispiele sind Probleme mit dem Netzwerkfluss, bei denen Waren oder Material über ein Netzwerk wie ein Bahnsystem transportiert werden.
Sie können einen Netzwerkfluss durch eine Grafik darstellen, deren Knoten Städte und deren Bögen Bahnlinien zwischen ihnen sind. Sie werden Ströme genannt, da ihre Eigenschaften denen von Wasser entsprechen, das durch ein Netzwerk von Rohren fließt.
Eine wichtige Einschränkung in Netzwerkflüssen besteht darin, dass jeder Bogen eine Kapazität hat, also die maximale Menge, die innerhalb eines festen Zeitraums über den Bogen transportiert werden kann.
Das maximale Flussproblem besteht darin, den maximalen Gesamtbetrag zu bestimmen, der gemäß den Kapazitätsbeschränkungen über alle Bögen im Netzwerk transportiert werden kann.
Das erste Problem wurde von dem russischen Mathematiker A.N. Tolstoi in den 1930er-Jahren untersucht. Die folgende Karte zeigt das tatsächliche Bahnnetz, für das er einen maximalen Verkehrsfluss finden wollte.
OR-Tools bietet mehrere Lösungsmöglichkeiten für Probleme mit dem Netzwerkfluss in den Graph-Bibliotheken.
In den folgenden Abschnitten finden Sie Beispiele für Netzwerkflussprobleme und erfahren, wie Sie diese beheben können: