Bearbeitung des Skripts 852

Sandy,

die Aufgabe kann mit dem Verfahren aus Kap. 4.4 gelöst werden:

• Zuerst ergänzt du einen Pfeil von der Senke zur Quelle, also <5,3> mit der Minimalkapazität 0 und der Maximalkapazität unendlich.
• Dann ergänzt du zwei neue Knoten (in der Musterlösung 0 und 6 genannt).
• Dann gehst du durch alle Knoten des ursprünglichen Netzwerks durch:
  • Bilde die Summe der Minimalkapazitäten aller eingehenden Pfeile. Wenn die Summe > 0, ergänze einen Pfeil von 0 zu dem Knoten mit Minimalkapazität 0 und Maximalkapazität gleich der Summe.
  • Genauso bilde die Summe der Minimalkapazitäten aller ausgehenden Pfeile und ergänze einen Pfeil von dem Knoten zu 6 mit Minimalkapazität 0 und Maximalkapazität gleich der Summe, wenn die Summe größer 0 ist.
• Für alle Pfeile, die schon im ursprünglichen Netzwerk vorhanden waren, setzt du die Minimalkapazität = 0 und die Maximalkapazität gleich der Differenz aus Maximal- und Minimalkapazität.

Jetzt hast du ein Netzwerk, in dem alle Minimalkapazitäten 0 sind (die ehemaligen Minimalkapazitäten werden über die neuen Knoten "umgeleitet") und deshalb der Nullfluss zulässig ist. Auf diesem Netzwerk bestimmst du mit Ford-Fulkerson einen maximalen Fluss.
Dann prüfst du, ob dieser Fluss gesättigt ist, d.h. ob auf allen von der (neuen) Quelle 0 ausgehenden Pfeile der Fluss gleich der Maximalkapazität ist:

• Wenn nein, gibt es keinen zulässigen Fluss im ursprünglichen Netzwerk.
• Wenn ja, gibt es einen zulässigen Fluss. Den errechnest du, indem die für jeden Pfeil im ursprünglichen Netzwerk den Fluss aus dem Ersatznetzwerk mit der Minimalkapazität im ursprünglichen Netzwerk addierst.

Gruß, Jens

Jens,

ich danke dir! Ich werd mich gleich mal daran versuchen.

Sandy

Jens,

nochmal vielen Dank, jetzt hab ich's kapiert. Ziemlich logisch, wenn man einmal verstanden hat!

Sandy