Die Anfänge der Graphentheorie
Die Graphentheorie ist ein Teilgebiet der Mathematik, die sich mit Graphen und ihren Beziehungen zueinander beschäftigt. Zu der Entwicklung dieses Teilgebietes kam es unteranderem durch das Königsberger Brückenproblem 1736 und das Vierfarbenproblem um 1850. Ein Graph ist dabei eine Menge aus Punkten, die man als Ecken oder Knoten bezeichnet. Diese Knoten können auch durch Linien, sogenannte Kanten bzw. Bögen miteinander verbunden sein. Die Graphentheorie findet Anwendung beispielsweise im Berechnen von Netzwerken, zum Ermitteln von kürzesten Wegen oder in der Chemie bei der Abzählung von Isomeren. So könnte man in einem Netzwerk die Computer mit den Knoten vergleichen und die Überlandkabel zum Verbinden der ganzen Computer mit den Kanten eines Graphen gleichsetzen. In der Chemie würde man dann die einzelnen Moleküle mit den Knoten vergleichen und die zwischen diesen Molekülen herrschende Bindung als Kanten bezeichnen.
Beispiel:
Grob kann man folgende Graphen unterscheiden:
1a. endliche Graphen (die Menge der Knoten und Kanten ist endlich)
1b. unendliche Graphen (die Menge der Knoten und Kanten ist unendlich)
2a. gerichtete Graphen (die Kanten sind gerichtet--> durch Pfeile statt Linien)
2b. ungerichtete Graphen (die Kanten sind ganz normale Linien)
Außerdem benötigt man die Begriffserklärungen folgender Begriffe:
* Ein Baum ist ein zusammenhängender, kreisfreier Graph.
* Ein Baum mit n Knoten besitzt genau n-1 Kanten.
* Sei G ein zusammenhängender Graph. Ein Gerüst von G ist ein maximaler in G enthaltener Baum, d.h. ein Gerüst ist ein zusammenhängender, alle Knoten enthaltender Untergraph mit minimaler Kantenanzahl.
Man verwendet Bäume und Gerüste für Energieverbundnetze, Bewässerungssysteme, Berechnungen in elektrischen Netzwerken, bei der Abzählung chemischer Isomere sowie bei Minimalgerüsten (siehe unten).
Graphen können auch verschieden eingefärbt werden. Dabei gibt es die Knotenfärbung - diese Färbung der Knoten von G geschieht so, daß keine zwei adjazenten Knoten die gleiche Farbe haben und die Kantenfärbung - diese Färbung der Kanten von G geschieht so, daß keine zwei adjazenten Kanten gleich gefärbt sind. Bei der Knotenfärbung wird die kleinste Anzahl von Farben, die zum Einfärben der Knoten von G nötig ist, als chromatische Zahl X(G) bezeichnet und bei der Kantenfärbung wird die kleinste Anzahl von Farben, die für das Einfärben der Kanten nötig war als chromatischer Index X'(G) bezeichnet. Graphenfärbung verwendet man zum Beispiel bei Mobilfunknetzen oder bei der Stundenplanung.
- Bei dem Königsberger Brückenproblem beschäftigte sich Leonhard Euler mit der Frage, ob man über die Königsberger (heute Kaliningrad) Brücken gehen kann und dabei jede Brücke genau einmal durchläuft und am Ende wieder am Anfangspunkt ankommt.
Als sich Euler dieses Bild in der Schreibweise eines Graphen ansah (siehe unten stehende Zeichnung), kam er zu der Erkenntnis, daß das nur möglich ist, wenn er keinen Knotenpunkt ungeraden Grades hat. In unserem Brückenfall bedeutet das, daß von keinem Ufer aus eine ungerade Anzahl von Brücken abgehen darf, um die gestellte Bedingung zu erfüllen. Da dies hier nicht der Fall ist, ist es nicht möglich alle Brücken genau einmal zu durchlaufen und dann wieder am Anfangspunkt anzukommen.
Dies führte zu den eulerschen Graphen. Man bezeichnet einen Kantenzug, der keine Kante doppelt enthält, sämtliche Kanten des Graphen besitzt und dessen Anfang und Ende übereinstimmen, als Euler-Tour. So bezeichnet man alle Graphen die diese drei Eigenschaften haben als eulersche Graphen. Eulersche Graphen erkennt man ganz leicht daran, daß sie die oben bereits genannten drei Eigenschaften aufweisen müssen. Hat der Kantenzug jedoch nur die erste dieser Eigenschaften so bezeichnet man ihn nur als Tour. Ein zusammenhängender Graph ist auch genau dann eulersch, wenn er als Vereinigung kantendisjunkter Kreise dargestellt werden kann (Veblen). Anwendung finden eulersche Graphen beispielsweise bei der Kontrolle von Straßen- und Schienennetzen, bei Museumsrundgängen, bei der Postauslieferung (Chinese Postman Problem) sowie bei der Müllabfuhr. Das Ziel zur Aufklärung des "Chinese Postman Problem" ist es, daß der Postbote am Postamt startet und den kürzesten Weg durch die Straßen haben möchte, dabei seine Post zustellt und dann wieder am Postamt anzukommt. Da sich erstmalig ein Chinese mit diese Optimierung auch schriftlich beschäftigte, nennt man es "Chinese Postman Problem". Beispiele für eulersche Graphen sind:
- Francies Guthrie bemerkte im Jahre 1852, daß zum Einfärben der Landkarte von England nur vier Farben nötig sind. Dabei muß jedoch darauf geachtet werden, daß zwei benachbarte Länder d.h. Länder mit einer gemeinsamen Grenze, nicht nur einem gemeinsamen Punkt, immer verschiedene Farben haben. So fragte Francies Guthrie seinen Bruder Frederick ob dies bei allen Landkarten möglich sei. Dies war der Ursprung des Vierfarbenproblems. Frederick erzählte es dann seinem Professor DeMorgan. Der erste schriftliche Nachweis dieses Problems geht auf Cayley 1878 zurück. Im folgenden Jahr erschien der Beweis von Kempe, jedoch wurde dieser elf Jahre später als fehlerhaft von Heawood bemerkt. Jedoch war dieser "Beweis" doch von großem Nutzen, da Kempe in ihm etwas fand, was sich heute "Kempe - Ketten" nennt und für den Beweis des Fünffarbensatzes von großem Wert war. Ein anderer falscher Beweis geht auf Tait im Jahre 1880 zurück. Dieser falsche Beweis wurde Jahre später von Petersen ebenfalls als fälschlich erklärt, Tait fand in seiner Erklärung jedoch eine äquivalente Formulierung des Vierfarbenproblems hinsichtlich einer Kantenfärbung mir drei Farben. Birkhoff bewies im Jahre 1922, daß die Behauptung jede Landkarte mit vier Farben einfärben zu können auf alle Landkarten bis zu einer Länderzahl von 25 wahr ist. Im Jahre 1976 wurde die Vierfarbenvermutung von Appel, Haken und Koch bewiesen, jedoch mittels Computer - ein handschriftlicher Beweis liegt bis heute nicht vor. Im folgenden Bild sieht man eine 4-Färbung der Bundesländer Deutschlands:
- Hamilton erfand ein Spiel, das sich "Around the world" nannte und das die Form eines Dodekaeders hatte, wobei auf jeder Ecke der Name einer Stadt zu finden war. Ziel dieses Spieles war es, eine Rundreise durch alle 20 Städte zu finden, bei der man am Ende wieder am Anfangspunkt ankommt und jede Stadt genau einmal besucht hat. Das Problem kann auf graphentheoretische Art folgendermaßen modelliert werden, wobei Hamiltons Lösung rot eingezeichnet ist:
Also ist das möglich. In gewissen Weise ähnelt dies einem eulerschen Graphen, jedoch ist es viel schwieriger.
Hamiltonschen Graphen liegen andere Definitionen und somit andere Graphentheoretische Grundlagen zugrunde:
- Ein Weg ist eine Folge von Knoten und Kanten, in der alle Knoten verschieden voneinander sind.
- Enthält der Weg alle Knoten des Graphen, so nennt man ihn Hamiltonsch.
- Ist des Hamiltonsche Weg geschlossen, so heißt der Weg Hamiltonkreis und der Graph, der einen Hamiltonkreis besitzt, heißt Hamiltonscher Graph.
Die hamiltonschen Graphen finden Anwendung beispielsweise bei Busrouten, mit Bedingung aller Haltestellen, bei der Belieferung aller Filialen einer Supermarktkette sowie beim Travelling Salesman Problem.
- Weiterhin gibt es das Problem der "zänkischen" Nachbarn. Dies führte zur Entwicklung planarer Graphen. Denn bei dem Problem stellte man sich, nach dem Bau von drei Brunnen und drei Häusern und einem darauffolgenden Streit der Hausbesitzer, die Frage, ob es möglich ist, sämtliche Häuser mit allen drei Brunnen so zu verbinden, daß sich die Wege nicht kreuzen. Dies ist nicht möglich, denn bei dem letzten Weg gibt es keine Möglichkeit mehr ihn ohne Kreuzen eines anderen Weges zu zeichnen (grüne Linie--> ein Beispiel). Dies sie folgendermaßen aus:
Da dies nicht möglich ist stellte man sich die Frage, ob es denn Graphen gibt, die diese Bedingung des Nichtüberschneiden von Kanten erfüllen. Und man kam zu der Antwort, daß es solche Graphen gibt. Man bezeichnet diese Graphen als planare Graphen, also heißt ein Graph planar, wenn er sich so in die Ebene zeichnen läßt, daß sich keine seiner Kanten schneiden. Man findet planare Graphen bei kreuzungsfreien Straßen oder Schienen sowie bei der Leiterplattenherstellung.
- Ein weiteres Problem ist das Heiratsproblem. So gibt es beispielsweise sieben heiratswillige Frauen und auch sieben Männer, die als Ehepartner in Erwägung kamen. Jede der Frauen stellte eine Liste von potentiellen Ehepartnern zusammen und man stellte sich die Frage, ob alle Frauen verheiraten kann ohne Bigamie zu betreiben. Die Liste der potentiellen Ehepartner sah so aus:
| F1 |
M2, M3 |
| F2 |
M2, M3 |
| F3 |
M1, M3, M4, M5, M6 |
| F4 |
M2, M3, M4, M7 |
| F5 |
M4, M6 |
| F6 |
M5, M7 |
| F7 |
M2, M3, M7 |
Demnach müsste der Graph für dieses Problem wie folgt aussehen, wobei die Lösung des Problems bereits rot gekennzeichnet ist:
So ist es möglich jede Frau zu verheiraten ohne Bigamie zu betreiben. Aus diesem Problem heraus bildeten sich die Matchings:
* Ein Matching in einem Graphen ist eine Menge unabhängiger Kanten, d.h. die Kanten sind paarweise nicht adjazent.
* Ein maximales Matching ist ein Matching mit der größtmöglichen Anzahl von Kanten.
* Ein perfektes Matching ist ein Matching, das alle Knoten des Graphen überdeckt.
So kann man das Heiratsproblem als ein perfektes Matching bezeichnen. Matchings werden in der Arbeitsvermittlung genutzt.
-
Minimalgerüste: Sieben Dörfer sollen mittels Straßen miteinander verbunden werden, wobei es keine Rolle spielt ob die Dörfer direkt zu erreichen sind, oder nicht. Für die Straßen soll so wenig Geld wie möglich ausgegeben werden. Diese Kosten lassen sich durch Graphentheorie bestimmen - die Kosten für eine Straße zwischen dem Dorf i und j sind in der unten stehenden Tabelle zu finden.(- bedeutet das zwischen diesen Dörfern keine Straße gebaut werden kann.):
| |
Dorf 1 |
Dorf 2 |
Dorf 3 |
Dorf 4 |
Dorf 5 |
Dorf 6 |
Dorf 7 |
| Dorf 1 |
0 |
12 |
10 |
- |
14 |
- |
20 |
| Dorf 2 |
12 |
0 |
12 |
10 |
6 |
- |
- |
| Dorf 3 |
10 |
12 |
0 |
4 |
- |
- |
7 |
| Dorf 4 |
- |
10 |
4 |
0 |
- |
6 |
- |
| Dorf 5 |
14 |
6 |
- |
- |
0 |
6 |
8 |
| Dorf 6 |
- |
- |
- |
6 |
6 |
0 |
4 |
| Dorf 7 |
20 |
- |
7 |
- |
8 |
4 |
0 |
Die Darstellung als Graph sieht so aus (die Lösung ist bereit rot markiert):
Somit betragen die Mindestkosten für das Straßensystem betragen 38. Weitere Bespiele für die Verwendung von Minimalgerüsten sind Zuglinien oder Fluglinien.
-
Es gibt auch das Kürzeste-Wege-Problem. Hierbei hat man einen Anfangspunkt und bestimmte Knoten, zwischen denen man nun den kürzesten Weg bestimmen möchte. An einem bestimmten Beispiel: Ein LKW-Fahrer soll an einem Tag fünf Kaufhäuser beliefern. Er muß die Ware im Lager abholen, dann auf dem schnellsten Weg zu einem Kaufhaus transportieren, und wieder zurück zum Lager fahren, um erneut seinen LKW zu beladen. Wieviele Kilometer fährt er dabei mindestens? Um diese Aufgabe lösen zu können, benötigt man einen Graphen, an dem man die einzelnen Kilometer für jede Strecke ablesen kann. Dieser Graph sieht dann so aus und die Lösung unserer Problemstellung ist dabei rot gekennzeichnet:
Hier kann man nun die einzelnen Teilstrecken, die den kürzesten Weg bilden, ablesen und bekommt als Ergebnis, daß der LKW-Fahrer mindestens 220 Kilometer zurücklegen muß.
