Einführung in Netzwerk-Flow-Techniken und Spannbäume

Einführung

Netzwerk-Flow-Techniken werden in Situationen eingesetzt, die auf die Optimierung von Verkehrsnetzen, Kommunikationsnetzen, Flugsystemen an Flughäfen, Seewegen für Kreuzfahrten, Pumpstationen (die Flüssigkeiten durch Rohrleitungen führen), Straßen zwischen Städten, Rohrnetzwerken und allen Situationen abzielen, die durch ein Netz dargestellt werden können. Dabei repräsentieren Knoten Stationen oder Städte, während Bögen Straßen, Fluglinien, Kabel oder Rohre darstellen und der Fluss durch LKWs, Nachrichten oder Medien über das Netzwerk erfolgt. Dies dient der Suche nach dem kürzesten Weg in einem Straßennetz oder der Ermittlung der maximalen Durchflussmenge in einem Rohrnetz.

Netzwerkmodelle

Netzwerkoptimierungsprobleme können im Großen und Ganzen durch eines dieser vier Modelle dargestellt werden:

• Modell zur Minimierung von Netzwerken (Minimaler Spannbaum / Minimum Spanning Tree)
• Modell des kürzesten Weges
• Maximaler-Fluss-Modell (Peak-Flow)
• Modell der minimalen Kosten (Min-Cost-Flow)

Modell zur Minimierung von Netzwerken

Das Modell zur Minimierung von Netzwerken (oder das Problem des minimalen Spannbaums) befasst sich mit der Bestimmung der Zweige, die alle Knoten in einem Netzwerk so verbinden, dass die Summe der Längen der gewählten Verbindungen minimiert wird. Zyklen (im Originaltext als „Fahrräder“ übersetzt) dürfen in der Lösung des Problems nicht enthalten sein.

Um einen minimalen Spannbaum zu erstellen, gelten die folgenden Eigenschaften:

1. Es sind die Knoten eines Netzwerks gegeben, aber nicht die Verbindungen. Stattdessen wird für jede potenzielle Verbindung eine positive Länge angegeben, falls diese in das Netzwerk eingefügt wird. (Alternative Maße für die Länge einer Verbindung sind Distanz, Kosten oder Zeit).
2. Das Netzwerk soll mit genügend Verbindungen so gestaltet werden, dass die Anforderung erfüllt ist, dass zwischen je zwei Knoten ein Pfad existiert.
3. Das Ziel ist es, diese Anforderung so zu erfüllen, dass die Gesamtlänge der im Netzwerk eingebetteten Verbindungen minimiert wird.

Ein Netzwerk mit n Knoten benötigt nur (n-1) Verbindungen, um einen Pfad zwischen je zwei Knoten zu ermöglichen. Die (n-1) Verbindungen sollten so gewählt werden, dass das resultierende Netzwerk einen Spannbaum bildet. Das Problem besteht darin, den Spannbaum mit der minimalen Gesamtlänge seiner Verbindungen zu finden.

Algorithmus für den minimalen Spannbaum

1. Man wählt willkürlich einen Knoten aus und verbindet ihn mit dem nächstgelegenen anderen Knoten (d. h. man fügt eine Verbindung hinzu).
2. Man identifiziert den nächsten Knoten, der noch nicht mit den bereits verbundenen Knoten verknüpft ist, und verbindet diese (d. h. man fügt eine Verbindung zwischen ihnen hinzu). Dieser Schritt wird wiederholt, bis alle Knoten verbunden sind.
3. Gleichstände: Wenn es mehrere Möglichkeiten für den nächsten Knoten gibt (Schritt 1 oder 2), kann die Auswahl beliebig getroffen werden, und der Algorithmus wird dennoch eine optimale Lösung erreichen. Solche Gleichstände sind jedoch ein Zeichen dafür, dass es mehrere optimale Lösungen geben kann (aber nicht muss). Alle diese Lösungen können identifiziert werden, indem man die Gleichstände auf unterschiedliche Weise auflöst.