Graphenalgorithmen

Maximaler Fluss

 aufwärts

Problem

Gegeben ist ein Netzwerk mit einer Quelle (source) s und einer Senke (target) t (Bild 1). Gesucht ist ein maximaler Fluss von der Quelle s zur Senke t entlang der Verbindungen des Netzwerkes, unter Beachtung der Durchfluss­kapazitäten der einzelnen Verbindungen, die als Zahlenwerte angegeben sind.

Bild 1: Netzwerk
Bild 1: Netzwerk

Das obige Netzwerk kann beispiels­weise einen Fluss mit dem Wert 10 auf dem Weg über die Knoten s-x-z-t aufnehmen. Hierdurch werden die Durchfluss­kapazitäten der durch­laufenen Verbindungen zwar nicht ausgeschöpft, aber jedenfalls auch nicht über­schritten. Bild 2 zeigt diesen Fluss, dargestellt als erste Zahl, getrennt durch einen senkrechten Strich von der Durchfluss­kapazität. Ist nur eine Zahl angegeben, so handelt es sich um die Durchfluss­kapazität und der Fluss beträgt 0.

Bild 2: Netzwerk mit Fluss (erste Zahl Fluss, zweite Zahl Kapazität der Kante)
Bild 2: Netzwerk mit Fluss (erste Zahl Fluss, zweite Zahl Kapazität der Kante)

Dieser Fluss ist jedoch nicht maximal – wir können ihn sogar auf den Wert 12 steigern. Zusätzlich können wir ihn ergänzen um einen weiteren (Teil-)Fluss mit dem Wert 11, den wir auf dem Weg s-y-r auf die Reise schicken. Dieser Fluss spaltet sich am Knoten r dann auf. Ein Teil vereinigt sich am Knoten z mit dem erst­genannten Fluss, der von dort aus nun den Wert 12 + 7 = 19 hat. Die Durchfluss­kapazität der Verbindung z-t wird hierdurch nicht über­schritten.

Das folgende Bild 3 zeigt diesen Fluss, wiederum dargestellt als erste Zahl, getrennt durch einen senkrechten Strich von der Durchfluss­kapazität.

Bild 3: Netzwerk mit Fluss (erste Zahl Fluss, zweite Zahl Kapazität der Kante)
Bild 3: Netzwerk mit Fluss (erste Zahl Fluss, zweite Zahl Kapazität der Kante)

Es stellt sich die Frage, ob dieser Fluss maximal ist, oder ob er sich noch auf einen größeren Wert steigern lässt. Die Regeln hierbei sind: Die Durchfluss­kapazitäten der Verbindungen dürfen nicht über­schritten werden, und alles was in einen Knoten hineinfließt, fließt auch wieder hinaus (abgesehen von der Quelle s und der Senke t).

Modellierung

Wir modellieren das Problem mithilfe eines gerichteten Graphen mit Kanten­markierung. Statt von Verbindungen zwischen den Knoten des Netzwerks sprechen wir nun von Kanten des Graphen.

Definition:  Ein Fluss­netzwerk (flow network) ist ein gerichteter Graph G = (V, E, c) mit Knotenmenge V, Kantenmenge E und nicht­negativer Kanten­markierung c : E Pfeil nach rechts reelle Zahlen. Das Fluss­netzwerk hat zwei ausge­zeichnete Knoten s mit Eingangsgrad 0 und t mit Ausgangsgrad 0. Die anderen Knoten nennen wir die inneren Knoten des Netzwerks.

Die Knoten s und t spielen eine spezielle Rolle als Quelle (source) s und als Senke (target) t eines Flusses durch das Netzwerk. Eine Kanten­markierung c wird inter­pretiert als Kapazität (capacity), d.h. als maximale Durchfluss­menge der betreffenden Kante.

Fluss

Definition:  Sei G = (V, E, c) ein Fluss­netzwerk. Ein Fluss (flow) in dem Netzwerk ist eine Abbildung f : E Pfeil nach rechts reelle Zahlen mit folgenden beiden Eigen­schaften:

  f(ekleiner gleich c(e)   für alle Kanten e Element E,

 Summe (u, vElement E   f(u, v)  =   Summe (v, wElement E   f(v, w)   für alle inneren Knoten v, also für alle Knoten v Element V \ {s, t}.

Die beiden Eigen­schaften bedeuten, dass der Fluss f(e) durch eine Kante e durch ihre Kapazität c(e) begrenzt ist und dass genau das, was in einen inneren Knoten v hineinfließt auch wieder herausfließt.

Das folgende Bild zeigt einen möglichen Fluss durch das obige Netzwerk; jede Kante e ist mit f(e) | c(e) beschriftet, d.h. die erste Zahl stellt den Fluss durch die Kante dar, die zweite Zahl die Kapazität der Kante, also ihre maximale Durchfluss­menge.

Bild 4: Fluss in einem Netzwerk (erste Zahl Fluss, zweite Zahl Kapazität der Kante)
Bild 4: Fluss in einem Netzwerk (erste Zahl Fluss, zweite Zahl Kapazität der Kante)

Definition:  Der Wert | f | eines Flusses f in einem Netzwerk ist der Gesamtfluss, der aus der Quelle s entspringt:

| f |   =    Summe (s,vElement E   f(s, v)

Beispiels­weise hat der Fluss in dem Netzwerk in Bild 4 den Wert 19. Wegen der zweiten Eigenschaft eines Flusses, nämlich dass aus allen inneren Knoten genauso viel wieder herausfließt wie hineinfließt, ist dieser Wert gleich dem Wert des Flusses, der in die Senke hineinfließt.

Steigerungsweg

Wenn ein Fluss durch ein Netzwerk gegeben ist, so stellt sich die Frage, ob dieser Fluss noch gesteigert werden kann. Im einleitenden Absatz hatten wir gesehen, dass ein Fluss mit dem Wert 10 noch auf den Wert 12 gesteigert werden konnte, und dass ein zusätzlicher (Teil-)Fluss hinzu­genommen werden konnte, wodurch der Gesamtfluss noch einmal gesteigert wurde.

Wir suchen also nach Wegen von der Quelle s zur Senke t, auf denen der Fluss die maximale Durchfluss­kapazität noch nicht ausschöpft, oder auf denen ein Fluss quasi in die falsche Richtung fließt. Einen derartigen Weg nennen wir einen Steigerungs­weg (augmentation path). Ein Steigerungs­weg bietet die Möglichkeit, den Gesamtfluss noch zu steigern.

Die möglichen Steigerungs­wege sind genau die Wege von der Quelle s zur Senke t in einem im Folgenden definierten Rest­kapazitäten-Netzwerk.

Definition:  Gegeben ist ein Fluss­netzwerk G = (V, E, c) mit einem Fluss f. Wir bilden hierzu ein weiteres Fluss­netzwerk G' = (V, E', c'), das wir als Rest­kapazitäten-Netzwerk (residual network) bezeichnen.

Das Netzwerk G' hat dieselbe Knotenmenge V wie G. Die Kantenmenge E' besteht aus

Die Kapazität einer Vorwärts­kante e beträgt c'(e) = c(e) – f(e); die Kapazität einer Rückwärts­kante e-1 beträgt c'(e-1) = f(e).

Ein Steigerungs­weg ist ein Weg im Rest­kapazitäten-Netzwerk von der Quelle s zur Senke t.

 

Das folgende Bild 5 zeigt das Rest­kapazitäten-Netzwerk zu dem Netzwerk mit dem dort einge­zeichneten Fluss aus Bild 4.

Bild 5: Restkapazitäten-Netzwerk
Bild 5: Restkapazitäten-Netzwerk

Ein Weg von der Quelle s zur Senke t in diesem Rest­kapazitäten-Netzwerk ist beispiels­weise der Weg über die Knoten s-x-y-z-t. Dieser Weg stellt somit einen Steigerungs­weg für das ursprüng­liche Netzwerk dar. Der Wert, um den sich der Gesamtfluss im ursprüng­lichen Netzwerk steigern lässt, ergibt sich als das Minimum der Kapazitäten der Kanten des Wegs im Rest­kapazitäten-Netzwerk. In diesem Beispiel ist dieser Wert 4. Indem der Fluss entlang dieses Weges im ursprüng­lichen Netzwerk um 4 gesteigert wird, ergibt sich der folgende in Bild 6 dargestellte Fluss in dem Netzwerk.

Bild 6: Netzwerk mit gesteigertem Fluss
Bild 6: Netzwerk mit gesteigertem Fluss

Finden von Steigerungswegen

Zur Berechnung eines möglichen Steigerungs­wegs suchen wir in dem Rest­kapazitäten-Netzwerk einen Weg von der Quelle s zur Senke t mithilfe der Breitensuche. Wir steigern dann den Fluss entsprechend und passen das Rest­kapazitäten-Netzwerk entsprechend an. Anschließend suchen wir einen weiteren Weg – solange, bis es keinen Weg mehr gibt. Wir beginnen mit dem ursprüng­lichen Netzwerk, das einem Rest­kapazitäten-Netzwerk mit einem Fluss mit Wert 0 entspricht.

Dieses Vorgehen ist in der Funktion computeMaxFlow im unten angegebenen Programm realisiert.

Schnitt

Um eine obere Schranke für den maximalen Fluss durch ein Netzwerk zu gewinnen, betrachten wir Schnitte durch das Netzwerk.

Definition:  Sei G = (V, E, c) ein Fluss­netzwerk mit Quelle s und Senke t. Ein Schnitt (S, T) durch das Netzwerk ist eine Partition der Knotenmenge V in zwei Mengen S mit s Element S und T mit t Element T.

Die Kapazität c(S, T) des Schnittes ist definiert als die Summe der Kapazitäten der Kanten, die von S nach T verlaufen:

c(S, T)  =   Summe u Element S, v Element T   c(u, v)

Etwas anders ist der Fluss des Schnitts definiert; vom Fluss durch die Kanten, die von S nach T führen, wird der Fluss durch die Kanten, die von T nach S wieder zurückführen, abgezogen:

f(S, T)  =   Summe u Element S, v Element T   f(u, v)  –   Summe u Element T, v Element S   f(u, v)

Das folgende Bild 7a zeigt einen Schnitt (S, T) durch das Netzwerk aus Bild 4. Die Teilmenge S besteht aus den Knoten s, x, y, z und die Teilmenge T aus den Knoten r, t. Bild 7b zeigt einen trivialen Schnitt: Die Teilmenge S besteht nur aus dem Knoten s, die Teilmenge T aus allen anderen Knoten.

yes Bild 7: Schnitt durch ein Netzwerk (a), trivialer Schnitt (b)
(a) (b)
Bild 7: Schnitt durch ein Netzwerk (a), trivialer Schnitt (b)

Die Kapazität des Schnitts aus Bild 7a beträgt 20 + 14 = 34, der Fluss des Schnitts beträgt 15 - 7 + 11 = 19. Die Kapazität des Schnitts aus Bild 7b beträgt 16 + 13 = 29, der Fluss des Schnitts beträgt 11 + 8 = 19.

Offenbar ist der Fluss jedes Schnitts durch das Netzwerk gerade gleich dem Wert des Flusses durch das Netzwerk, denn der Gesamtfluss durch das Netzwerk muss ja den Schnitt passieren. Im Beispiel hat jeder Schnitt einen Fluss von 19. Und offenbar kann somit der Gesamtfluss nicht größer sein als die Kapazität eines minimalen Schnitts. Durch das Netzwerk kann nicht mehr hindurch­fließen als durch die engste Stelle hindurch­passt.Tatsächlich zeigt sich, dass sich der Gesamtfluss steigern lässt, bis er die Kapazität eines minimalen Schnitts erreicht, d.h. der maximale Fluss entspricht genau der Kapazität eines minimalen Schnitts [FF 56].

Der Schnitt in Bild 8 hat eine Kapazität von 23. Dieser Schnitt ist minimal. Entsprechend gibt es einen Fluss mit dem Wert 23, jedoch keinen mit größerem Wert. Tatsächlich haben wir im einleitenden Absatz bereits auf intuitive Weise einen Fluss mit dem Wert 23 gefunden.

Bild 8: Schnitt mit minimaler Kapazität
Bild 8: Schnitt mit minimaler Kapazität

Satz:  (Ford, Fulkerson [FF 56])

Sei G = (V, E, c) ein Fluss­netzwerk. Die folgenden drei Aussagen sind äquivalent:

 

Programm

Die Klasse FlowNetwork modelliert ein Fluss­netzwerk. Sie enthält die Methode computeMaxFlow zur Berechnung des Wertes eines maximalen Flusses. Zugleich wird ein minimaler Schnitt berechnet und in der ArrayList mincut gepeichert.

// modelliert ein Flussnetzwerk
public class FlowNetwork extends WeightedGraph
{

    public int s, t; // source, target
    public double[][] f; // flow
    public ArrayList<Integer> mincut;   // minimaler Schnitt

    // Konstruktor; Fluss wird mit 0 initialisiert
    public FlowNetwork(int n_)
    {
        super(n_, 0);  // noedge=0
        f=new double[n][n];
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                f[i][j]=0;
     }

    // berechnet den Wert des Flusses, der aus der Quelle entspringt
    public double getFlowValue()
    {
        double flow=0;
        for (int j=0; j<n; j++)
            flow+=f[s][j];
        return flow;
    }

    // berechnet das Minimum der Kantengewichte entlang des
    // Wegs über die Knoten der Liste augmentationpath
    private double getMinCapacity(ArrayList<Integer> augmentationpath)
    {
        int i, j;
        MiniMaximizer<Double> min=new MiniMaximizer<Double>();
        Iterator<Integer> it=augmentationpath.iterator();
        i=it.next();
        while (it.hasNext())
        {
            j=it.next();
            min.add(getWeight(i, j));
            i=j;
        }
        return min.getMinVal();
    }

    // steigert den Fluss entlang des Wegs augmentationpath um flow;
    // reduziert die Restkapazitäten entsprechend
    private void augmentFlow(ArrayList<Integer> augmentationpath, double flow)
    {
        int i, j;
        Iterator<Integer> it=augmentationpath.iterator();
        i=it.next();
        while (it.hasNext())
        {
            j=it.next();
            f[i][j]+=flow;    // Wert des Flusses steigern
            setWeight(j, i, f[i][j]);  // Rückwärtskante
            addWeight(i, j, -flow);    // Vorwärtskante
            i=j;
        }
    }

    // berechnet den maximalen Fluss in einem Netzwerk;
    // sucht einen Steigerungsweg (augmentation path) im
    // Restkapazitäten-Netzwerk (residual network),
    // steigert den Fluss entsprechend und aktualisiert das
    // Restkapazitäten-Netzwerk, sucht erneut nach einem
    // Steigerungsweg, solange bis kein Steigerungsweg
    // mehr gefunden wird;
    // zum Schluss wird ein minimaler Schnitt (S, T) berechnet,
    // dargestellt durch die Menge S aller Knoten, die von der
    // Quelle s aus erreichbar sind
    public double computeMaxFlow()
    {
        ArrayList<Integer> augmentiationpath;  // Steigerungsweg
        BreadthFirstTree bft;   // Breitensuchbaum
        mincut=new ArrayList<Integer>();    // minimaler Schnitt
        double flow;

        while (true)
        {
            bft=new BreadthFirstTree(this, s);
            if (!bft.isReachable(t))
                break;
            augmentiationpath=bft.getPathTo(t);
            flow=getMinCapacity(augmentiationpath);
            augmentFlow(augmentiationpath, flow);
        }

        // minimalen Schnitt berechnen ( = alle Knoten, die
        // zum Schluss noch von der Quelle s aus erreichbar sind)
        for (int i=0; i<n; i++)
            if (bft.isReachable(i))
                mincut.add(i);

        return getFlowValue();
    }

}  // end class FlowNetwork

 

In der Funktion augmentFlow wird eine Vorwärts­kante, sobald ihre Rest­kapazität den Wert 0 erreicht hat, automatisch gelöscht. Dies wird dadurch erreicht, dass im Konstruktor der Wert noedge mit 0 festgelegt wird. Kanten mit einer Kapazität 0 sind also nicht vorhandene Kanten.

Im Programm werden die Klassen WeightedGraph, BreadthFirstTree und MiniMaximizer verwendet.

 

Für den Test wird das Fluss­netzwerk aus dem oben angegebenen Beispiel verwendet.

public class TestFlowNetwork
{
    public static void main(String[] args)
    {
        FlowNetwork w=new FlowNetwork(6);
        w.s=0;
        w.t=5;
        w.setWeight(0, 1, 16);
        w.setWeight(0, 2, 13);
        w.setWeight(1, 3, 12);
        w.setWeight(2, 4, 14);
        w.setWeight(1, 2, 10);
        w.setWeight(2, 1, 4);
        w.setWeight(3, 2, 9);
        w.setWeight(3, 5, 20);
        w.setWeight(4, 3, 7);
        w.setWeight(4, 5, 4);

        System.out.println(w);
        System.out.println("Maximaler Fluss: "+w.computeMaxFlow());
        System.out.println("Minimaler Schnitt: "+w.mincut);
    }

}

 

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 14.02.2017   Updated: 28.02.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik