Graphentheorie
Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung graphentheoretischer Probleme oft auf Algorithmen basiert, ist die Graphentheorie auch in der Informatik, insbesondere der Komplexitätstheorie, von großer Bedeutung. Die Untersuchung von Graphen ist auch Inhalt der Netzwerktheorie.
Auf den ersten Blick scheint die Graphentheorie eher eine abstrakte und realitätsferne Disziplin der Mathematik zu sein. Tatsächlich lassen sich aber sehr viele Alltagsprobleme mit Hilfe von Graphen modellieren.
Einen Überblick über die in der Wikipedia verfügbaren graphentheoretischen Artikel liefert das Portal Graphentheorie.
Table of contents |
2 Grundlegende Begriffe und Probleme 3 Geschichte 4 Anwendungen 5 Weblinks |
In der Graphentheorie ist ein Graph eine Menge von Punkten (man nennt diese dann Knoten oder auch Ecken), die eventuell durch Linien (sog. Kanten bzw. Bögen) miteinander verbunden sind. Die Form der Punkte und Linien spielt in der Graphentheorie keine Rolle.
Man unterscheidet dabei zwischen:
Betrachteter Gegenstand
Kompliziertere Graphentypen sind:
Je nach Problemstellung können Knoten und Kanten auch mit Farben (formal mit natürlichen Zahlen) oder Gewichten (d. h. rationalen oder reellen Zahlen) versehen werden. Man spricht dann von knoten- bzw. kantengefärbten oder -gewichteten Graphen.
Exakte Definitionen der verschiedenen Graphentypen findet man im Artikel Typen von Graphen in der Graphentheorie.
Die Graphentheorie definiert eine Vielzahl von grundlegenden Begriffen, deren Kenntnis zum Verständnis von wissenschaftlichen Abhandlungen unbedingt von Nöten ist. Glücklicherweise sind die Begriffe in der Mehrheit sehr intuitiv bezeichnet, so dass man diese schnell erlernen kann und nur gelegentlich die genaue Definition nachschlagen muss. Vor der Lektüre weitergehender graphentheoretischer Artikel empfiehlt sich daher insbesondere das Lesen der folgenden Artikel:
Grundlegende Begriffe und Probleme
Die verschiedenen Eigenschaften können zueinander in Beziehung stehen. Die Beziehungen zu untersuchen ist eine Aufgabe der Graphentheorie. Beispielsweise ist die Knotenzusammenhangszahl immer kleiner als die Kantenzusammenhangszahl, welche wiederum immer kleiner als der Minimalgrad des betrachteten Graphen ist. In ebenen Graphen ist die Färbungszahl immer kleiner als 5. Diese Aussage ist auch als der Vier-Farben-Satz bekannt.
Einige der aufgezählten Grapheneigenschaften sind relativ leicht algorithmisch bestimmbar, d. h. die entsprechenden Algorithmen benötigen in Abhängigkeit der Größe der Graphen nur wenig Zeit, um die Grapheneigenschaft zu berechnen. Andere Eigenschaften sind praktisch auch mit Computer unlösbar.
Die wichtigsten Probleme und Ergebnisse der Graphentheorie werden in folgenden Artikeln dargestellt:
- Paarungen in Graphen
- Zusammenhang von Graphen
- Flüsse und Schnitte in Netzwerken
- Färbung von Graphen
- Durchlaufbarkeit von Graphen
- Cliquen und stabile Mengen
Geschichte
Die Anfänge der Graphentheorie gehen bis in das Jahr 1736 zurück. Damals publizierte Leonhard Euler eine Lösung für das Königsberger Brückenproblem. Die Frage war, ob es einen Rundgang durch die Stadt Königsberg – heute Kaliningrad gibt, der jede der sieben Brücken über den Fluss Pregel genau einmal benutzt. Euler konnte für dieses Problem eine notwendige Bedingung angeben, und so die Existenz eines solchen Rundganges verneinen. Eine hinreichende Bedingung, sowie einen effizienten Algorithmus, der in einem Graphen einen solchen Rundgang finden kann, wurde erst 1873 von Hierholzer angegeben.
Wie oben erläutert können mit Hilfe von Graphen viele Probleme modelliert werden. So lässt sich die Aufgabe eine kürzeste Route zwischen zwei Orten zu finden dadurch lösen, in dem man das Straßennetz geeignet als kantengewichteten Graphen modelliert und in diesem mit Hilfe des Algorithmus von Dijkstra effizient einen kürzesten Weg berechnet.
Bekannt ist auch das Problem die Länder einer Landkarte mit möglichst wenig Farben so zu färben, dass aneinander angrenzende Länder nicht die selbe Farbe erhalten. Hier wird die Landkarte ebenfalls in einen Graphen übersetzt und dann versucht mit einem Algorithmus dieses Problem zu lösen. Allerdings weiß man heute, dass dieses Problem auch mit Computern kaum zu lösen ist und es wird vermutet, dass keine effizienten Algorithmen existieren, die dieses Problem exakt lösen.
Stundenplanprobleme lassen sich über die Färbung von Graphen formulieren.
Anwendungen
Weblinks