Ein Paketzustelldienst will jeden Tag eine maximale Anzahl von Paketen von Stadt s nach Stadt t bringen. Jeder Transport muss über die Zwischenstädte a, b, c oder d gehen, wie in Abbildung 5.21 angedeutet. Jeder einzelne Transportweg e=(x,y) von einer Stadt x zu einer anderen Stadt y hat nur eine bestimmte, begrenzte Kapazität, d. h., pro Tag können über e nur eine bestimmte Anzahl cap(e) Pakete von Stadt x nach Stadt y transportiert werden, etwa weil auf dieser Strecke nur eine bestimmte Anzahl von Lastwagen zur Verfügung steht.

Abbildung 5.21. Ein Netzwerk

Jede Kante ist mit ihrer Kapazität beschriftet. s ist die Quelle des Netzwerkes und t die Senke.

Selbstverständlich können von einer Stadt x an einem Tag nur so viele Pakete weitergeschickt werden, wie dort auch ankommen. In den Zwischenstädten müssen (pro Tag) alle ankommenden Pakete auch wieder weitergeleitet werden; es sollen sich dort keine Pakete stapeln. Beim Weiterleiten darf aber nie die Kapazität eines Transportweges überschritten werden. Nur in der Stadt t, der „Senke“, dürfen Pakete geöffnet und verbraucht werden - sie verschwinden dort; genauso dürfen nur in der Stadt s, der „Quelle“, Pakete hergestellt und verpackt werden - sie entstehen dort.

Das Problem des Paketzustelldienstes besteht darin, dass er an den Kapazitäten der Transportwege nichts ändern kann; er kann nur das Weiterleiten der Pakete festlegen, d. h. für jeden Transportweg angeben, wie viele Pakete pro Tag darüber fließen sollen, ohne dass es zu Kapazitätsüberschreitungen kommt. Er will diese Flüsse so festlegen, dass pro Tag möglichst viele Pakete in Stadt t ankommen. Mit anderen Worten: Er will einen maximalen Fluss von s nach t herstellen. Dabei kommt es nicht darauf an, dass die Pakete möglichst schnell von s nach t transportiert werden, sondern nur darauf, dass möglichst viele Pakete pro Tag in der Senke „verschwinden“.^[40]

Ein gerichteter Graph G, dessen Kanten e eine nicht-negative Kapazitätsinformation cap(e) tragen, wird als Netzwerk bezeichnet. Seien s, die Quelle (source), und t, die Senke (sink), zwei verschiedene Knoten von G. Ein Netzwerk-Fluss (network flow) von s nach t in einem solchen Netzwerk ist eine Abbildung f, die jeder Kante e einen Wert f(e) zuweist, so dass folgende Bedingungen erfüllt sind:

Der Wert des Flusses f ist „das, was in t ankommt, ohne von dort wieder zu verschwinden“, also die Summe der f(e) über alle zu t inzidenten Kanten e minus die Summe der f(g) über alle von t ausgehenden Kanten g. Aufgrund der Flusserhaltung ist der Wert eines Flusses auch immer gleich der Summe der aus s ausgehenden Flüsse minus der Summe der in s eingehenden Flüsse.

Ein maximaler Fluss (maximum flow) von s nach t ist ein Fluss mit maximalem Wert. Man kann zeigen, dass es immer einen Fluss mit maximalem Wert gibt, in dem die Summe der aus t ausgehenden Flüsse sowie die Summe der in s eingehenden Flüsse 0 sind. Zu s inzidente oder aus t ausgehende Kanten können bei der Berechnung eines maximalen Flusses also vernachlässigt werden (s. hierzu auch Übung 65).

Abbildung 5.22 zeigt einen solchen maximalen Fluss in dem Netzwerk aus Abbildung 5.21: In einer Beschriftung „f/c“ einer Kante steht f für den (über diese Kante geleiteten) Fluss und c für ihre Kapazität. (Warum der Fluss wirklich maximal ist, werden wir gleich sehen.)

Abbildung 5.22. Ein maximaler Fluss

In einer Beschriftung „f/c“ einer Kante steht f für den (über diese Kante geleiteten) Fluss und c für ihre Kapazität. Die Abbildung f ist ein Fluss, da sie die Bedingungen der Kapazitätsbeschränkung und Flusserhaltung erfüllt. f ist sogar ein maximaler Fluss mit dem Wert 120; das ist gleich der Summe der Flüsse der zu t inzidenten Kanten und gleich der Summe der Flüsse der aus s ausgehenden Kanten. Der Fluss ist maximal, weil es einen Schnitt {s,a,c} und {b,d,t} mit ebenfalls dem Wert 120 gibt; s. hierzu auch den Abschnitt “Minimale Schnitte”.

Zur Berechnung solcher maximaler Flüsse bietet LEDA einige Funktionen an, die in der Header-Datei max_flow.h deklariert sind.

Als Beispiel daraus zeigen wir die Verwendung der Funktion MAX_FLOW():

int MAX_FLOW(graph& G, 
             node s, node t, 
             edge_array<int>& cap, 
             edge_array<int>& f);

Diese Funktion erwartet außer dem gerichteten graph G die Quelle s und die Senke t sowie ein auf G gültiges Kanten-Array cap, das die Kapazitäten der Kanten enthält, und ein ebenfalls auf G gültiges Kanten-Array f, in das sie die einzelnen Flusswerte des berechneten maximalen Flusses einträgt. Sie liefert den Wert des berechneten maximalen Flusses zurück.

Das folgende Programm lässt den Benutzer einen (gerichteten) Graphen editieren, wobei er die Daten-Labels der Kanten mit den Kapazitäten beschriften muss. (Die eingegebenen Werte werden zunächst noch nicht angezeigt!) Danach kann er zwei Knoten selektieren. Der erste wird als Quelle, der zweite als Senke aufgefasst, und MAX_FLOW() wird aufgerufen. Das Programm beschriftet dann die Benutzer-Labels der Kanten mit Strings der Form „f/c“, wobei c die aus dem Daten-Label übernommene Kapazität und f der Wert des Flusses über diese Kante im berechneten maximalen Fluss ist. Abbildung 5.22 wurde damit erzeugt.

#include <LEDA/max_flow.h>
#include <LEDA/graph.h>
#include <LEDA/edge_array.h>
#include <LEDA/graphwin.h>
#include <LEDA/list.h>
#include <iostream>

using leda::GRAPH;
using leda::GraphWin;
using leda::window;
using leda::node;
using leda::edge;
using leda::edge_array;
using leda::list;
using leda::string;

int main()
{
  GRAPH<string,int> G;

  GraphWin gw(G, 500, 500, "Maximum Flow");
  gw.set_edge_label_type(leda::data_label);
  gw.set_node_label_type(leda::data_label);
  gw.set_node_border_width(2);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) {    

    // get source s and sink t  
    // as the two selected nodes of GraphWin
    node s, t;
    list<node> L = gw.get_selected_nodes();
    if(L.size() != 2) {
      gw.message("Select exactly 2 nodes! Click <done>.");
      gw.wait();
      gw.del_message();
      continue;
    }
    else { 
      s = L.tail(); // get_selected_nodes() pushes new nodes 
      t = L.head(); // to the front; so reverse order here
    }

    
    // setup cost information: use information associated to GRAPH<,>
    edge_array<int> cap(G);
    edge e;
    forall_edges(e, G)
      cap[e] = G.inf(e);

    // define edge array on G for flow values 
    edge_array<int> f(G);

    // compute maximum flow from s to t
    int max_flow = MAX_FLOW(G, s, t, cap, f);

    forall_edges(e, G) 
      gw.set_user_label(e, 
         string("%ld", f[e]) + "/" + string("%ld", cap[e]));
    gw.set_edge_label_type(leda::user_label);
    gw.redraw();

    gw.message("The value of a maximum flow from " 
               + G.inf(s) + " to " + G.inf(t) + " is "
               + string("%ld", max_flow) + ". Click <done>.");
    gw.wait();
    gw.del_message();
    gw.redraw();
  }
  
}

Maximale Flüsse müssen nicht eindeutig sein; es kann mehrere Möglichkeiten geben, einen maximalen Fluss von s nach t herzustellen. Das lässt eine Verallgemeinerung der Problemstellung zu:

Stellen wir uns in Abbildung 5.21 zusätzlich vor, dass das Transportieren eines Paketes über eine Kante Kosten verursacht, die von Kante zu Kante unterschiedlich sind, dass also jede Kante e zusätzlich mit einer Kosteninformation cost(e) beschriftet ist. Der Transport von f(e) Paketen über die Kante e kostet also pro Tag f(e)·cost(e) Silbertaler. Was der Paketzustelldienst dann erreichen möchte, ist ein maximaler Fluss mit minimalen Kosten, d. h. ein maximaler Fluss f, der die Summe über alle f(e)·cost(e) minimiert.

Zur Berechnung von solchen maximalen Flüssen mit minimalen Kosten bietet LEDA einige Funktionen an, die in der Header-Datei min_cost_flow.h deklariert sind.

So erwartet beispielsweise die Funktion

int MIN_COST_MAX_FLOW(graph& G, 
                      node s, node t, 
                      edge_array<int>& cap, 
                      edge_array<int>& cost, 
                      edge_array<int>& f);

in einem zusätzlichen Kanten-Array cost die Kosten der Kanten als Argument. Sie liefert den Wert eines maximalen Flusses mit minimalen Kosten zurück und trägt die Flusswerte dieses Flusses in das Kanten-Array f ein.

Ein Schnitt (cut) durch ein Netzwerk teilt dieses in zwei nicht leere Teile auf. Formal gesehen ist ein Schnitt eine Aufteilung (S,T) der Knotenmenge V in zwei nicht leere Teilmengen S und T. Abbildung 5.23 zeigt einen Schnitt durch den Graphen von Abbildung 5.21.

Eine Schnittkante (cut edge) ist eine Kante, die vom Schnitt durchtrennt wird, d. h., deren Quelle in S, und deren Ziel in T liegt, oder umgekehrt. Ein s-t-Schnitt (s-t-cut) ist ein Schnitt (S,T), der in den Mengen S und T die Quelle s und die Senke t voneinander trennt.

Der Wert eines Schnitts ist die Summe der Gewichte (Kapazitäten) aller Kanten, die den Schnitt in Richtung von S nach T kreuzen, deren Quelle also in S, und deren Ziel in T liegt. Ein minimaler Schitt (minimum cut) ist ein Schnitt mit minimalem Wert.

Abbildung 5.23. Ein minimaler Schnitt

Ein Schnitt durch einen Netzwerkgraphen. Der Schnitt besteht aus den Teilmengen S={s,a,c} und T={b,d,t}. Die Schnittkanten sind dick gezeichnet. Der Schnitt ist ein s-t-Schnitt. Der Wert des Schnitts ist 60+30+30=120. Dies ist gleichzeitig ein minimaler Schnitt (bezüglich der Quelle s und der Senke t), weil es in diesem Netzwerk einen Fluss von s nach t mit dem Wert 120 gibt.

Ein bekannter Satz aus der Graphentheorie besagt, dass der maximale Fluss immer gleich dem Wert eines minimalen s-t-Schnitts ist. Darüber hinaus gilt auch immer, dass der Wert jedes Flusses kleiner gleich dem Wert jedes s-t-Schnittes ist. Daher ist der Schnitt aus Abbildung 5.23 auch ein minimaler s-t-Schnitt: Der Wert dieses Schnittes ist 120, und da wir in Abbildung 5.22 einen Fluss mit ebenfalls dem Wert 120 sehen, kann es weder einen kleineren s-t-Schnitt, noch einen größeren Fluss geben; das beweist also nicht nur die Minimalität des s-t-Schnittes aus Abbildung 5.23, sondern auch die Maximalität des Flusses aus Abbildung 5.22.

Zur Berechnung von minimalen Schnitten bietet LEDA einige Funktionen an, die in der Header-Datei min_cut.h deklariert sind.

Wichtig

LEDA definiert den Begriff „Schnitt“ in Bezug auf ungerichtete Graphen: Ein Schnitt ist eine Aufteilung der Knotenmenge in zwei nicht leere Teilmengen S und T. Der Wert des Schnitts ist die Summe der Gewichte (Kapazitäten) aller Kanten, die einen Endpunkt in S und den anderen Endpunkt in T haben. Es kommt also nicht darauf an, in welcher Richtung die Kanten den Schnitt kreuzen. Zudem berechnen die Funktionen aus min_cut.h einen minimalen Schnitt ohne Berücksichtigung einer ausgewiesenen Quelle s und Senke t; es werden also alle möglichen Schnitte in Betracht gezogen.

Beispielsweise liefert die Funktion

int MIN_CUT(graph& G, edge_array<int>& cap, list<node>& C);

den Wert eines minimalen Schnittes zurück und speichert eine der beiden Teilmengen S und T dieses Schnittes in der Liste C.

In Abbildung 5.23 liefert diese Funktion den Wert 120 und trennt die Knotenmenge in S={s,a,c} und T={b,d,t} auf. Es ist hier mehr oder weniger Zufall, dass damit auch ein minimaler s-t-Schnitt gefunden wurde, der die Maximalität des Flusses aus Abbildung 5.22 beweist.

Das folgende Programm lässt den Benutzer einen (gerichteten) Graphen editieren, wobei er die Daten-Labels der Kanten mit den Gewichten (Kapazitäten) beschriften muss. MIN_CUT() berechnet dann einen minimalen Schnitt durch das so spezifizierte Netzwerk (wobei nochmals darauf hingewiesen sei, dass es hier keine ausgewiesene Quelle und Senke gibt.) Die Knoten der Teilmenge T werden mit einem rechteckigen Rahmen sichtbar gemacht; Kanten, die den Schnitt kreuzen, werden dick gezeichnet. Abbildung 5.23 wurde damit erzeugt.

#include <LEDA/min_cut.h>
#include <LEDA/graph.h>
#include <LEDA/edge_array.h>
#include <LEDA/graphwin.h>
#include <LEDA/list.h>
#include <iostream>

using leda::GRAPH;
using leda::GraphWin;
using leda::window;
using leda::node;
using leda::edge;
using leda::edge_array;
using leda::list;
using leda::string;

int main()
{
  GRAPH<string,int> G;

  GraphWin gw(G, 500, 500, "Minimum Cut");
  gw.set_edge_label_type(leda::data_label);
  gw.set_node_label_type(leda::data_label);
  gw.set_node_border_width(2);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) {    
    
    // setup cost information: use information associated to GRAPH<,>
    edge_array<int> weight(G);
    edge e;
    forall_edges(e,G)
      weight[e] = G.inf(e);


    // compute minimum cut
    list<node> cut_nodes;
    int min_cut= MIN_CUT(G, weight, cut_nodes);

    // minimum cut may have changed; reset attribute values
    gw.set_node_shape(leda::circle_node);

    // show cut nodes as rectangular nodes
    gw.set_shape(cut_nodes, leda::rectangle_node);
    gw.set_edge_width(1);
    gw.set_edge_color(leda::black);

    // show cut edges thick and red
    forall_edges(e, G) {
      node s = G.source(e);
      node t = G.target(e);
      // is e a cut edge? the following is not an efficient search!
      if(cut_nodes.search(s) && !cut_nodes.search(t)
         || !cut_nodes.search(s) && cut_nodes.search(t)) {
        gw.set_width(e, 4);
        gw.set_color(e, leda::red);
      }
    }


    gw.message("The value of a minimum cut is "
               + string("%ld",min_cut)+ ". Click <done>.");
    gw.wait();
    gw.del_message();
    gw.redraw();
  }
  
}

Mehr Informationen über diese Funktionen finden sich auf den entsprechenden Manualseiten zu max_flow.h, min_cost_flow.h und min_cut.h.

So erlaubt es etwa die Funktion MIN_COST_FLOW(), ein verallgemeinertes Flussproblem zu lösen: Jede Kante hat eine minimale und eine maximale Kapazität und eine Kosteninformation. Zusätzlich darf jeder Knoten Quelle oder Senke sein; er darf dann angeben, wie viel Fluss (pro Zeiteinheit) er in das Netzwerk einspeisen oder daraus entnehmen will. Diese Funktion berechnet einen Fluss mit minimalen Kosten, der allen diesen Nebenbedingungen genügt.