Netzwerke

Ein Netzwerk im Sinne der Graphentheorie ist ein Graph, bei dem die Kanten „gewichtet“ sind. D.h. heißt jeder Kante ij wird ein Gewicht c_ij zugewiesen.

Dass sich Netzwerke für die Abbildung von Verkehrsnetze eignen, ist fast nicht zu übersehen. Es lassen sich aber auch Prozessketten, Lagerhaltungsprobleme und viele andere Vorgänge als Netzwerk abbilden. Je nach Problemstellung können die Gewichte Entfernungen, Zeitdauern, Kosten oder Kapazitäten sein.

Königsberger Brückenproblem

Das Königsberger Brückenproblem gilt als das Problem, aus dem sich die Graphentheorie entwickelte. Der Schweizer Mathematiker, oder besser gesagt Universalgelehrte, Leonard Euler (1707-1783), machte sich Gedanken über die Möglichkeiten für Spaziergänge über die Brücken von Königsberg im damaligen Preußen.

Durch Königsberg fließt die Pregel, und in deren Mitte befinden sich zwei Inseln. Auf einer der Inseln befand sich der Kneiphof (Fläche A). Die Inseln waren wie in Abb. 1-6 dargestellt über Brücken verbunden.

Die Frage ist, ob es möglich ist, einen Spaziergang zu machen, bei dem jede Brücke genau einmal überschritten wird und der zurück zum Ausgangspunkt führt.

In einen „modernen“ Graphen überführt, ist jede Fläche ein Knoten und jede Brücke eine Kante.

Die Antwort lautet, es ist nicht möglich.
Ohne nähere Erläuterung, die Bedingungen sind, dass

1. der Graph zusammenhängend ist und
2. dass alle Knoten einen geraden Knotengrad haben. Der Knotengrad gibt die Anzahl der Kanten an, die mit einem Knoten inzidieren.

Die erste Bedingung ist erfüllt, aber der Knotengrad von A ist 5. Damit ist ein Spaziergang in oben beschriebener Form nicht möglich.

Eine andere Fragestellung ist, ob es möglich ist, einen Spaziergang zu machen, bei dem alle Brücken überschritten werden, der aber nicht zum Ausgangspunkt zurückführen muss.
Die Antwort auch hierfür: Nein, es ist nicht möglich.

Die Bedingungen sind:

1. Der Graph ist zusammenhängend.
2. Es gibt genau 2 Knoten mit ungeradem Knotengrad und der Spaziergang beginnt an einem der beiden und endet an dem anderen.

Der Graph ist zusammenhängend. Der Knotengrad von A ist 5, der von B ist 3 und der von C ist ebenfalls 3. Von daher sind es mehr als zwei Knoten mit ungeradem Knotengrad und die Bedingung ist nicht erfüllt.

Ein bei Kindern beliebtes Spiel ist „das ist das Haus vom Nikolaus“ zu zeichnen.

Es ist hier möglich, alle Kanten genau einmal abzufahren. Die Knotengrade sind 2, 4, 4, 3 ,3.
Es gibt genau 2 Knoten mit ungeradem Knotengrad.
Das heißt, wenn man in Knoten D oder E anfängt und in E oder D endet, ist es möglich. Es ist allerdings nicht möglich, wieder an den Ausgangspunkt zurück zu gelangen.

Weniger beliebt hingegen ist es unter Briefträgern, die gleiche Straße mehrfach ablaufen zu müssen. Da in aller Regel das Straßennetz nicht so aufgebaut ist, dass alle Knoten einen geraden Knotengrad haben, wird sich meist kein Weg finden lassen, bei dem jeder Weg nur einmal abgelaufen werden muss. Der chinesische Mathematiker Guan Meigu befasste sich in den 1960er Jahren mit dem Problem.

Die Aufgabe beim Briefträgerproblem ist, die Kanten zu suchen, die doppelt abgelaufen werden müssen, sodass der Briefträger wieder zum Ausgangspunkt zurück kommt und die Summe der Längen der doppelt abgelaufenen Kanten minimal ist.

Diese Aufgabe lässt sich nicht mehr ganz so leicht lösen, Lösungsverfahren machen in der Regel von mehreren verschiedenen Graphenalgorithmen als Subroutine Gebrauch, zum Beispiel einem der in den nächsten Abschnitten vorgestellten Kürzeste-Wege-Algorithmen.

Färbungen

In einem ungerichteten Graphen könnte man auf die Idee kommen, die Knoten mit verschiedenen Farben anzumalen, sodass zwei benachbarte, d.h. durch eine Kante verbundene Knoten, eine unterschiedliche Farbe haben. Ist die minimale Anzahl von Farben mit der das möglich ist n, dann sagt man der Graph ist n-knotenfärbbar.

Die Bestimmung der Anzahl der Farben ist alles andere als einfach und erfordert neben umfangreichen theoretischen Kenntnissen erheblichen Rechenaufwand.

Ein zentrales Ergebnis ist der „4-Farben-Satz“. Er besagt, dass ein Planarer Graph mit maximal 4 Farben färbbar ist. Ein Planarer Graph kann so gezeichnet werden, dass sich Kanten nicht schneiden.

Wenn die Zeichnung eines Planaren Graphen vorliegt, kann dieser also mit 4 Farben eingefärbt werden. Anderenfalls stellt sich die Frage, ob sich der Graph planar zeichnen lässt. Diese Frage ist manchmal schwerer zu beantworten als man denkt.

Die Vermutung, dass 4 Farben ausreichend sind, kam 1852 beim Einfärben von Landkarten auf. Es dauerte über 100 Jahre, bis man diese Vermutung mithilfe von Rechnern beweisen konnte. Man kann jedes Land als Knoten interpretieren, und wenn die Gebiete eine gemeinsame Grenze haben eine Kante zwischen den Knoten einzeichnen. Ist das Gebiet allerdings nicht zusammenhängend, weil es z.B. Exklaven gibt, kann es sein, dass 4 Farben nicht mehr reichen.