Wir freuen uns über jede Rückmeldung. Ihre Botschaft geht vollkommen anonym nur an das Administrator Team. Danke fürs Mitmachen, das zur Verbesserung des Systems oder der Inhalte beitragen kann. ACHTUNG: Wir können an Sie nur eine Antwort senden, wenn Sie ihre Mail Adresse mitschicken, die wir sonst nicht kennen!
unbekannter Gast
Anzeigen
Dies ist Version . Es handelt sich nicht um die aktuelle Version und kann folglich auch nicht geändert werden.
[Zurück zur aktuellen Version]    [Diese Version wiederherstellen]
vom 22.05.2014, aktuelle Version,

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 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, 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:

Weitere grundlegende Begriffe findet man in:

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:

Geschichte

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

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, engl. Graph Drawing) eine Herausforderung. Besonders komplexe Netze werden erst durch ausgefeilte Autolayout-Algorithmen übersichtlich.

Teilgebiete

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

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

Linkkatalog zum Thema Graphentheorie bei curlie.org (ehemals DMOZ)

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 0-19-853916-9.
  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.

Vorlage:Link FA