Graphalgorithmen

Graphen sind ein sehr häufig benutztes Modell zur Beschreibung struktureller Zusammenhänge. Sie bestehen aus Knoten, welche mit Kanten (sowohl gerichtet als auch ungerichtet) verbunden sind. Einige prominente Beispiele für den Einsatz von Graphen sind:
  • Routenplanung
    Hier stellen Knoten wichtige Punkte (Kreuzungen, Städte) dar und Kanten entsprechen Verbindungsstraßen. Eine Einbahnstraße wird durch eine gerichtete Kante dargestellt.
  • Kommunikationsnetzwerke (z.B. Telefon, Internet)
    Knoten sind hier Telefone, Modems, Server, Provider und mehr, Kanten die Datenleitungen.
  • Gantt-Diagramme zur Ablaufplanung
    Knoten entsprechen Abschnitten des Projekts, gerichtete Kanten den Abhängigkeiten zwischen den Abschnitten.
  • Abbildung hierarchischer Strukturen

Die Behandlung dieser Modelle mit den Mitteln der algorithmischen Graphentheorie stellt ein wichtiges Teilgebiet der Mathematik und Informatik dar. Einige wichtige Algorithmen aus diesem Gebiet sollen hier vorgestellt und erklärt werden, sowohl als anschauliche Web-Applikationen als auch durch ihren Pseudo-Code.

Eine der meistgenutzten Anwendungen von Graphen im Alltag ist die Darstellung von Verkehrs- und Kommunikationsnetzen. Die Übersichtskarte der deutschen Autobahnen im offiziellen Führer "Autobahn Service", die Bahnlinien eines Verkehrsverbundes oder das Streckennetze einer Fluggesellschaft werden stets durch Graphen dargestellt, ohne dass wir uns dessen überhaupt noch bewusst werden.

Es leuchtet daher unmittelbar ein, dass in diesem Zusammenhang das Studium von Wegen in den entsprechenden Graphen von größter Bedeutung ist. Insbesondere wird man sich für möglichst "günstige" Wege interessieren. Dabei kann "günstig" viele Interpretationen erfahren: Vielleicht ist ein kürzester oder ein schnellster Weg gesucht, vielleicht ein billigster, vielleicht auch einer, auf dem man möglichst selten eine Radarstreife der Polizei antrifft.

Logo Dijkstra.png Dijkstra - Algorithmus
Der Dijkstra - Algorithmus berechnet den kürzesten Weg zwischen zwei Punkten, wenn es keine negativen Kantengewichte gibt.

Logo AStar.png A* - Algorithmus
Der A* - Algorithmus funktioniert ähnlich wie der Dijkstra - Algorithmus. Allerdings benutzt er zusätzlich noch eine Schätzung für den Abstand zwischen den Knoten und ist so unter Umständen schneller.

Logo BellmanFord.png Bellman-Ford - Algorithmus
Im Gegensatz zu den beiden vorherigen Algorithmen berechnet der Bellman-Ford - Algorithmus auch kürzeste Wege, wenn negative Kantengewichte gegeben sind.

Logo FloydWarshall.png Algorithmus von Floyd-Warshall
Der Algorithmus von Floyd-Warshall berechnet den kürzesten Weg zwischen allen Paaren von Punkten. Er funktioniert auch bei negativen Gewichten.

Ziel des Minimalen Spannbaum-Problems ist es, eine Menge von Knoten mit minimalen Kosten zu verbinden. Solch ein Problem liegt zum Beispiel vor, wenn man
  • einige Rechner möglichst kostengünstig miteinander verbinden möchte oder
  • mit einem möglichst kurzen Rohrnetz alle Häuser eines Blocks mit Wasser versorgen möchte.

Ein Spannbaum muss also zwei grundlegende Eigenschaften erfüllen,
  • Zusammenhang und
  • Kreisfreiheit.
Daraus ergibt sich sofort, dass ein Spannbaum eine Kante weniger als Knoten enthalten muss. Hätte er weniger Kanten, könnte er nicht alle Knoten verbinden, hätte er dagegen mehr, so würde er unweigerlich einen Kreis enthalten.

Ist nun jeder Kante ein Gewicht – beispielsweise Länge oder Kosten – zugeordnet, so kann man nach einem Spannbaum mit möglichst kleiner Gesamtlänge oder möglichst niedrigen Gesamtkosten fragen, also nach einem minimalen Spannbaum.

Zur Bestimmung minimaler Spannbäume gibt es mehrere Algorithmen, die zum Teil mehrmals und unabhängig von einander gefunden wurden. Wir beschränken uns hier auf zwei Varianten:

Logo Kruskal Prim.png Algorithmus von Prim
Der Algorithmus von Prim berechnet einen minimalen Spannbaum auf einem ungerichteten Graphen.

Logo Kruskal Prim.png Algorithmus von Kruskal
Der Algorithmus von Kruskal berechnet ebenfalls einen minimalen Spannbaum auf einem ungerichteten Graphen. Weiterhin gibt er auf nicht-zusammenhängenden Graphen auch einen minimalen aufspannenden Wald zurück.

Das Matching - Problem heißt im Deutschen "Zuordnungsproblem". Es geht dabei um das Finden einer möglichst großen Relation, die je zwei Elemente aus verschiedenen Mengen verknüpft.

Der gewichtete Matching - Algorithmus ist ein Spezialfall, der die unterschiedlichen Verknüpfungen mit Präferenzen besetzt, um so eine bestmögliche Zuteilung zu erhalten. Dieser lässt sich am besten an einem Beispiel verdeutlichen: So entsprang dieses Problem der simplen Frage wie man einer gewissen Anzahl von Kindern Geschenke zuordnen kann und dabei eine optimale Zufriedenheit erreicht.

Ein anderes typisches, uns alle betreffendes Problem ist das so genannte Hochzeitsproblem, bei dem die beiden Teilmengen jeweils mit Frauen und Männern besetzt sind. Nun entsteht die Frage, in welcher Kombination die Paare gebildet werden sollen, um eine möglichst hohe Zufriedenheit (geringe "Scheidungsquote") zu erreichen .

Gelöst werden kann dieses Problem unter anderem mit der ungarischen Methode (im bipartiten Fall) sowie dem Blossom Algorithmus (im nicht-bipartiten Fall, hier nur für den ungewichteten Fall dargestellt).

Logo HopcroftKarp.png Algorithmus von Hopcroft-Karp
Der Algorithmus von Hopcroft-Karp berechnet für zwei gegebene Mengen mit möglichen Zuordnungen eine maximale Relation.

Logo Hungarian.png Ungarische Methode
Die Ungarische Methode ermittelt für zwei gegebene Mengen mit gewichteten Verknüpfungen eine maximale (bezüglich der Gewichte) Zuteilung.

Logo Blossom.png Blossom Algorithmus
Der Blossom Algorithmus berechnet im Gegensatz zum Algorithmus von Hopcroft-Karp auf allgemeinen Graphen eine kantenmaximale Zuteilung.

Ein häufig auftretendes Problem in Graphen und Netzwerken ist die Berechnung von Flüssen. Seien es Warenflüsse, Informationsflüsse in einem Kommunikationsnetzwerk oder ein Pipelinenetz für Öl oder Wasser: die Berechnung von Transportströmen in einem Netzwerk ist ein vielfach modelliertes Problem.

Hierbei werden häufig zwei Varianten betrachtet:
  • Bei der Berechnung eines maximalen Flusses ist die Menge der über eine Kante transportierbaren Menge beschränkt durch die Kapazität der Kante. Gesucht ist dann die maximale von Quelle zur Senke transportierbaren Menge.
  • Alternativ kann auch der kostenminimale Fluss einer bestimmten Größe gefragt sein. In diesem Fall ist neben den Kantenkapazitäten noch die Kosten für den Transport einer Einheit der Ware gegeben. Gesucht ist nun ein Transportweg, welcher die Gesamtkosten der transportierten Ware minimiert.

Für beide Problemarten gibt es verschiedene Algorithmen. Zwei davon werden im Folgenden vorgestellt.

Logo FordFulkerson.png Algorithmus von Ford und Fulkerson
Der Algorithmus von Ford und Fulkerson berechnet einen maximalen Fluss im Netzwerk.

Logo CycleCancelling.png Cycle-Cancelling Algorithmus
Der Cycle-Cancelling Algorithmus berechnet einen maximalen Fluss mit minimalen Kosten.

Ein klassisches Problem der Graphentheorie ist das Eulerweg - Problem, wobei nach Wegen bzw. Kreisen, die alle Kanten eines gegebenen Graphen enthalten, gesucht wird.

Die Aufgabenstellung wurde erstmals durch folgende Frage formuliert:
Der Fluss Pregel teilt die Stadt Königsberg (heute Kaliningrad) in fünf Stadtteile, die untereinander durch sieben Brücken verbunden sind. Ist ein Rundgang möglich, bei dem man jede Brücke genau einmal passiert?

Diese Frage lässt sich als graphentheoretisches Problem auffassen (Stadtteile als Knoten, Brücken als Kanten) und verallgemeinern und wurde als solches 1736 von Leonhard Euler gelöst: Ein solcher Rundweg existiert genau dann, wenn kein oder zwei Knoten ungeraden Grad besitzen.
Besitzt kein Knoten ungeraden Grad, so erhält man einen Eulerkreis, besitzen jedoch zwei Knoten einen ungeraden Grad, so ist nur ein Eulerweg möglich, dessen Endpunkte eben diese zwei Knoten sind.

Ziel des verwandten Chinesische Postboten - Problems ist es, einen kürzesten Pfad in einem Graphen zu finden, der jede Kante mindestens einmal benutzt und wieder zum Ausgangspunkt zurückkehrt.

Das prominenteste Beispiel für dieses Problem ist der Postbote, der in seinem Stadtteil Post austeilen muss. Er muss durch jede Straße mindestens einmal gehen, und am Ende seines Weges wieder am Postamt ankommen, wofür er selbstverständlich so wenig Zeit wie möglich brauchen möchte. Der Name des Problems begründet sich auf eben diesem Problem des Postboten, und auf der Tatsache, dass das Problem zum ersten Mal von einem Chinesen untersucht wurde.
Ein analoges Beispiel ist das Problem des Schneeräumdienstes: Auch hier muss das Schneeräumfahrzeug möglichst optimal jede Straße abfahren und am Ende zur Garage zurückkehren.

Logo Hierholzer.png Hierholzer - Algorithmus
Der Hierholzer - Algorithmus berechnet eine Eulertour in einem Graphen (falls eine solche existiert).

Logo DirectedChinesePostman.png Chinesisches Postboten - Problem
Das Chinesische Postboten - Problem kann durch eine Kombination der vorgestellten Matching - Algorithmen und des Hierholzer - Algorithmus gelöst werden.