Dynamisierung multiterminaler Flüsse in Form von Gomory-Hu-Bäumen

Dr. Tanja Hartmann

Ein Projekt im Rahmen einer KIT Feasibility Study of Young Scientists (FYS)

Die Flussberechnung in Netzwerken ist eine grundlegende Problemstellung der Graphentheorie. Ebenso ist die Dualität von maximalen s-t-Flüssen und minimalen s-t-Schnitten in gewichteten Graphen ein elementares Konzept der Netzwerkanalyse. Sie findet Ausdruck im “Max-Flow-Min-Cut-Theorem”, welches besagt, dass der Wert eines maximalen s-t-Flusses gerade dem Wert eines minimalen s-t-Schnittes entspricht.

Ein minimaler s-t-Schnitt teilt einen Graphen so in zwei disjunkte Teilgraphen, dass die Quelle s in einem der beiden Teilgraphen, die Senke t im anderen Teilgraphen liegt, und dass die Summe der Kantengewichte, die vom s-Teilgraphen in den t-Teilgraphen reichen, minimal wird über alle Schnitte dieser Art. Das multiterminale Flussproblem fragt nun nach allen paarweisen, minimalen s-t-Schnitten eines ungerichteten Graphen.

Gomory und Hu [GH61] entwickelten 1961 eine elegante Darstellung dieser n(n-1)/2 minimalen s-t-Schnitte, indem sie einen gewichteten Baum (Gomory-Hu-Baum) mit folgenden Eigenschaften berechneten:

• Alle Knoten des zugrundeliegenden Graphen sind im Baum enthalten.
• Jede Baumkante repräsentiert einen minimalen s-t-Schnitt bezüglich ihrer beiden inzidenten Knoten – entnimmt man die Kante, so zerfällt der Baum in die beiden Schnitt-Teilgraphen, das Gewicht der Kante entspricht dem Schnittgewicht.
• Der minimale s-t-Schnitt bezüglich zweier im Baum nicht adjazenter Knoten s und t wird durch eine minimal gewichtete Kante auf dem eindeutigen Pfad zwischen s und t gegeben.

Ziel der Feasibility Study ist die Entwicklung eines voll-dynamischen, algorithmischen Ansatzes zur fortlaufenden Neuberechnung von Gomory-Hu-Bäumen, bei fortlaufendem Einfügen und Löschen von Knoten und Kanten im zugrundeliegenden Graphen. Das Hauptproblem hierbei sind die globalen Auswirkungen einer Kantenänderung auf die minimalen s-t-Schnitte. Eine einfache, lokale Aktualisierung der Baumstruktur ist daher nicht möglich. Dies macht eine sinnvolle Vorberechnung und die Erhaltung möglichst vieler, aus einem vorhergehenden Schritt schon bekannter Teile der gesuchten Struktur extrem schwierig und die Fragestellung zu einer interessanten Herausforderung!

• [GH61]
  R. E. Gomory and T.C. Hu. Multi-Terminal Network Flows. Journal of the Society for Industrial and Applied Mathematics, 9:551–570, December 1961.

Im Rahmen dieses Projekts sind mehrere Hiwi-Stellen sowohl im Bereich der Implementierung und Durchführung von Experimenten als auch im Bereich der theoretischen Analyse zu vergeben.