Graphentheorie

Ungerichteter Graph mit sechs Knoten.

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.

Zahlreiche Alltagsprobleme lassen sich mit Hilfe von Graphen modellieren.

Betrachteter Gegenstand

→ Hauptartikel: Graph (Graphentheorie)

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:

• endlichen Graphen, bei denen die Menge der Knoten und Kanten endlich ist, und unendlichen Graphen, auf die dies nicht zutrifft, sowie
• gerichteten Graphen, bei denen die Kanten gerichtet sein können (dargestellt durch Pfeile statt Linien) und ungerichteten Graphen.

Komplexere Graphentypen sind:

• Multigraphen, bei denen im Gegensatz zu einfachen Graphen Kanten zwischen den Knoten mehrfach vorkommen dürfen sowie auch Schlingen zugelassen sind, d.h. Kanten, die einen Knoten mit sich selbst verbinden und
• Hypergraphen, bei denen im Gegensatz zu einfachen Graphen Kanten mehr als nur zwei Knoten verbinden können.

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.

Grundlegende Begriffe und Probleme

Die Graphentheorie definiert eine Vielzahl von grundlegenden Begriffen, deren Kenntnis zum Verständnis von wissenschaftlichen Abhandlungen unbedingt vonnöten ist. Diese sind 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:

• Typen von Graphen in der Graphentheorie
• Nachbarschaft und Grad in Graphen
• Wege, Pfade, Zyklen und Kreise in Graphen
• Wälder und Bäume in der Graphentheorie

Weitere grundlegende Begriffe findet man in:

• Repräsentation von Graphen im Computer
• Isomorphie von Graphen
• Operationen auf Graphen
• Teilgraphen und Minoren

Graphen können verschiedene Eigenschaften haben. So kann ein Graph zusammenhängend, bipartit, planar, eulersch oder hamiltonisch sein. Es kann nach der Existenz spezieller Teilgraphen gefragt werden oder bestimmte Parameter untersucht werden, wie zum Beispiel Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite, Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, chromatische Zahl, Stabilitätszahl oder Cliquenzahl.

Die verschiedenen Eigenschaften können zueinander in Beziehung stehen. Die Beziehungen zu untersuchen ist eine Aufgabe der Graphentheorie. Beispielsweise ist die Knotenzusammenhangszahl nie größer als die Kantenzusammenhangszahl, welche wiederum nie größer 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, das heißt, die entsprechenden Algorithmen benötigen in Abhängigkeit von der Größe der Graphen nur wenig Zeit, um die Grapheneigenschaft zu berechnen. Andere Eigenschaften sind praktisch auch mit Computern unlösbar.

Die wichtigsten Probleme und Ergebnisse der Graphentheorie werden in folgenden Artikeln dargestellt:

• Paarung (Graphentheorie)
• Zusammenhang von Graphen
• Flüsse und Schnitte in Netzwerken
• Färbung von Graphen
• Durchlaufbarkeit von Graphen
  • Eulerkreisproblem
  • Briefträgerproblem
  • Hamiltonkreisproblem
  • Problem des Handlungsreisenden
• Knotenüberdeckungen, Cliquen und stabile Mengen

Geschichte

Königsberger Brückenproblem im Stadtplan...

...und abstrakt als Graph (Orte durch Knoten, Brücken durch Kanten repräsentiert)

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 (Preußen) gibt, der jede der sieben Brücken über den Fluss Pregel genau einmal benutzt. Euler konnte eine für dieses Problem nicht erfüllbare notwendige Bedingung angeben und so die Existenz eines solchen Rundganges verneinen.

Der Begriff Graph wurde in Anlehnung an graphischen Notationen chemischer Strukturen erstmals 1878 von dem Mathematiker James Joseph Sylvester verwendet.^[1] Als weiterer Begründer der frühen Graphentheorie gilt Arthur Cayley. Eine der ersten Anwendungen waren chemische Konstitutionsformeln.^[2][3] (Siehe auch Chemoinformatik und Literatur: Bonchev/Rouvray, 1990). Das erste Lehrbuch zur Graphentheorie erschien 1936 von Dénes Kőnig.^[4]

Anwendungen

Wie oben erläutert, können mit Hilfe von Graphen viele Probleme modelliert werden.

Geradezu klassisch ist die Aufgabe, eine kürzeste Route zwischen zwei Orten zu finden. Sie lässt sich mit Graphen lösen, indem man das Straßennetz geeignet als kantengewichteten Graphen modelliert und in diesem mit Hilfe des Algorithmus von Dijkstra effizient ein kürzester Weg berechnet wird.

Algorithmisch deutlich schwieriger ist die Bestimmung einer kürzesten Rundreise (siehe Problem des Handlungsreisenden), bei der alle Orte eines Netzwerkes genau einmal besucht werden müssen. Da die Zahl der möglichen Rundreisen exponentiell mit der Zahl der Orte wächst, ist der naive Algorithmus, alle Rundreisen auszuprobieren und die kürzeste auszuwählen, für praktische Anwendungen unbrauchbar. In der Praxis wird man Orte auch mehrfach besuchen können. Dann gilt indirekt die Dreiecksungleichung, und in diesem Fall kann mit Approximationsalgorithmen gearbeitet werden, die eine Rundreise finden, die höchstens doppelt (MST-Heuristik) oder höchstens 1,5-mal (Christofides-Heuristik) so lang wie die kürzeste Rundreise ist.

Prominent ist auch das Problem, die Länder einer Landkarte mit möglichst wenig Farben so zu färben, dass aneinander angrenzende Länder nicht dieselbe Farbe erhalten. Hier wird die Landkarte ebenfalls in einen Graphen übersetzt und dann versucht, mit einem Algorithmus dieses Problem zu lösen. Ähnlich wie beim Problem des Handlungsreisenden lässt sich dieses Problem nach heutigem Wissensstand selbst mit Computern ab einer gewissen Größe der Landkarte nicht in vernünftiger Zeit exakt lösen. Das Problem, allgemeine Graphen optimal zu färben, gilt als eines der schwierigsten Probleme in der Klasse der NP-vollständigen Probleme überhaupt. Unter der Voraussetzung $P\neq NP$ (siehe P-NP-Problem) ist selbst eine approximative Lösung nicht bis auf einen konstanten Faktor möglich.

Veränderung von Graphen

Hauptsächlich in der Informatik wird die Transformation von Graphen anhand von regelbasierten Graphersetzungssystemen untersucht. Graphersetzungssysteme, die dem Aufzählen aller Graphen einer Graphsprache dienen, werden auch Graphgrammatik genannt.

Visualisierung

Im Bereich der Computergrafik ist die Visualisierung von Graphen (Graphzeichnen, engl. Graph Drawing) eine Herausforderung. Besonders komplexe Netze werden erst durch ausgefeilte Autolayout-Algorithmen übersichtlich.

Teilgebiete

• Algebraische Graphentheorie
• Extremale Graphentheorie
• Geometrische Graphentheorie
• Probabilistische Graphentheorie
• Topologische Graphentheorie

Siehe auch

• Portal:Graphentheorie
• Glossar Graphentheorie
• Netzwerkforschung
• Komplexes Netzwerk
• Software zur Visualisierung von Graphen: yEd, Graphviz

Literatur

• Martin Aigner: Graphentheorie: eine Entwicklung aus dem 4-Farben-Problem. 269 Seiten, 1984.
• Daniel Bonchev, D. H. Rouvray: Chemical Graph Theory: Introduction and Fundamentals. Abacus, New York NY 1990, 1991. ISBN 0-85626-454-7
• J. Sedlacek: Einführung in die Graphentheorie. B. G. Teubner, Leipzig 1968, 1972.
• M. Nitzsche: Graphen für Einsteiger (Rund um das Haus vom Nikolaus). Vieweg, Wiesbaden 2004. ISBN 3-528-03215-4
• R. Diestel: Graphentheorie. 3. Auflage. Springer, Heidelberg 2005. ISBN 3-540-67656-2 (online-download)
• Peter Gritzmann, René Brandenberg: Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer. Springer, Berlin - Heidelberg 2003 (2.Aufl.). ISBN 3-540-00045-3

Weblinks

• Links zum Thema Graphentheorie im Open Directory Project

Einzelnachweise

1. ↑ James Joseph Sylvester: Chemistry and Algebra. In: Nature. Band 17, 1878, S. 284
2. ↑ Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson: Graph Theory 1736-1936. Oxford University Press, 1999, ISBN 0198539169.
3. ↑ Arthur Cayley: Chemical Graphs. In: Philosophical Magazine. Band 47, 1874, S. 444–446
4. ↑ Dénes Kőnig: Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe. Akademische Verlagsgesellschaft, Leipzig 1936.