Graphentheorie

Die Graphentheorie (seltener auch Grafentheorie) 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. Zudem lassen sich zahlreiche Alltagsprobleme mit Hilfe von Graphen modellieren.

Ungerichteter Graph mit sechs Knoten.

Betrachteter Gegenstand

→ Hauptartikel: Graph (Graphentheorie)

In der Graphentheorie bezeichnet ein Graph eine Menge von Knoten (auch Ecken genannt) zusammen mit einer Menge von Kanten. Eine Kante ist hierbei eine Menge von genau zwei Knoten. Ist die Menge der Knoten endlich, spricht man von endlichen Graphen, ansonsten von unendlichen Graphen. Wenn die Kanten statt durch Mengen durch Paare von Knoten angegeben sind, spricht man von gerichteten Graphen. In diesem Falle unterscheidet man zwischen der Kante (a,b) – als Kante von Knoten a zu Knoten b – und der Kante (b,a) – als Kante von Knoten b zu Knoten a.

Komplexere Graphentypen sind:

• Multigraphen, bei denen die Kantenmenge eine Multimenge ist;
• Hypergraphen, bei denen eine Kante eine beliebig große Menge von Knoten darstellt (man spricht in diesem Falle auch von Hyperkanten);
• Petri-Netze mit zwei Arten von Knoten.

Knoten und Kanten können 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 sehr intuitiv einleuchtend:

• Graph
• Nachbarschaft, Grad
• Weg, Pfad, Zyklus und Kreis
• Wald, Baum
• Teilgraph, Minor.

Weitere grundlegende Begriffe sind:

• Adjazenzmatrix
• Inzidenzmatrix
• Isomorphie von Graphen.

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, Bogenzusammenhangszahl, 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 schnell algorithmisch bestimmbar, etwa wenn der Aufwand höchstens mit dem Quadrat der Größe der Graphen wächst. Andere Eigenschaften praktisch angewandter Graphen sind innerhalb der Lebensdauer heutiger Computer nicht zu bestimmen.

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

• Matching (Graphentheorie)
• Zusammenhang (Graphentheorie)
• Flüsse und Schnitte in Netzwerken
• Färbung (Graphentheorie)
• Durchlaufbarkeit von Graphen
  • Eulerkreisproblem
  • Briefträgerproblem
  • Hamiltonkreisproblem
  • Problem des Handlungsreisenden
• Knotenüberdeckung
• Clique (Graphentheorie)
• stabile Menge

Geschichte

Das Königsberger Brückenproblem im Stadtplan…

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

Ein von der Graphentheorie unabhängiger Vorläufer in der Antike war die Methode Dihairesis, mit deren Hilfe man (nur teilweise graphisch) zoologische, musikwissenschaftliche und andere Begriffe hierarchisierte. Es entstanden so frühe Systematiken innerhalb verschiedener Wissensgebiete.

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. Als weiterer Begründer der frühen Graphentheorie gilt Arthur Cayley. Eine der ersten Anwendungen waren chemische Konstitutionsformeln. (Siehe auch Chemische Graphentheorie und Literatur: Bonchev/Rouvray, 1990). Das erste Lehrbuch zur Graphentheorie erschien 1936 von Dénes Kőnig.

Anwendungen

Eine wichtige Anwendung der algorithmischen Graphentheorie ist die Suche nach einer kürzesten Route zwischen zwei Orten in einem Straßennetz. Dieses Problem kann man als Graphenproblem modellieren. Hierzu abstrahiert man das Straßennetz, in dem man alle Orte als Knoten aufnimmt, und eine Kante hinzufügt, wenn es eine Verbindung zwischen diesen Orten gibt. Die Kanten dieses Graphen werden je nach Anwendung gewichtet, zum Beispiel mit der Länge der assoziierten Verbindung. Mit Hilfe eines Algorithmus zum Finden von kürzesten Pfaden (beispielsweise mit dem Algorithmus von Dijkstra) kann eine kürzeste Verbindung effizient gefunden werden.

Algorithmisch deutlich schwieriger ist die Bestimmung einer kürzesten Rundreise (siehe Problem des Handlungsreisenden), bei der alle Orte eines Straßennetzwerkes genau einmal besucht werden müssen. Da die Zahl der möglichen Rundreisen faktoriell mit der Zahl der Orte wächst, ist der naive Algorithmus, alle Rundreisen auszuprobieren und die kürzeste auszuwählen, für praktische Anwendungen nur für sehr kleine Netzwerke praktikabel. Es existieren für dieses Problem eine Reihe von Approximationsalgorithmen, die eine gute aber nicht eine optimale Rundreise finden. So liefert die Christofides-Heuristik eine Rundreise die maximal 1,5-mal so lang ist wie die bestmögliche. Unter der Annahme, dass P ≠ NP (siehe P-NP-Problem), existiert kein effizienter Algorithmus für die Bestimmung einer optimalen Lösung, da dieses Problem NP-schwer ist.

Ein weiteres bekanntes Problem fragt, wie viele Farben man braucht um die Länder einer Landkarte einzufärben, sodass keine zwei benachbarten Länder die gleiche Farbe zugewiesen bekommen. Die Nachbarschaftsbeziehung der Länder kann man als planaren Graph repräsentieren. Das Problem kann nun als Knoten-Färbungsproblem modelliert werden. Nach dem Vier-Farben-Satz braucht man maximal 4 verschiedene Farben. Ob sich im Allgemeinen ein Graph mit weniger Farben einfärben lässt, kann man nach heutigem Wissensstand nicht effizient entscheiden. Das Problem gilt als eines der schwierigsten Probleme in der Klasse der NP-vollständigen Probleme. Unter der Voraussetzung, dass P≠ NP, ist selbst eine bis auf einen konstanten Faktor angenäherte Lösung nicht effizient 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‘, englisch Graph Drawing) eine Herausforderung. Besonders komplexe Netze werden erst durch ausgefeilte Autolayout-Algorithmen übersichtlich (siehe hierzu: Layout #Graphentheorie).

Teilgebiete

• Algebraische Graphentheorie
• Chemische Graphentheorie
• Extremale Graphentheorie
• Geometrische Graphentheorie
• Zufallsgraph (Probabilistische Graphentheorie)
• Topologische Graphentheorie
• Spektrale Graphentheorie: Die spektrale Graphentheorie untersucht Graphen anhand ihrer Adjazenzmatrizen, Inzidenzmatrizen oder Laplace-Matrizen durch die Analyse von Eigenwerten, Eigenvektoren und charakteristischen Polynomen.

Ungerichtete Graphen besitzen symmetrische Adjazenzmatrizen und deshalb reelle Eigenwerte. Alle Eigenwerte zusammengenommen werden als Spektrum des Graphen bezeichnet. Während die Adjazenzmatrix von der Knotensortierung abhängig ist, ist das Spektrum davon unabhängig.

Siehe auch

 Portal:Graphentheorie – Übersicht zu Wikipedia-Inhalten zum Thema Graphentheorie

• Netzwerkforschung
• Komplexes Netzwerk
• yEd, Graphviz - Software zur Visualisierung von Graphen

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

•  Wikibooks: Mathematik-Glossar: Graphentheorie – Lern- und Lehrmaterialien
• Links zum Thema Graphentheorie im Wikipedia:de:Open Directory Project