Graphentheorie

Teilgebiet der diskreten Mathematik und der theoretischen Informatik

Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Betrachtungsgegenstand der Graphentheorie sind Graphen (Mengen von Knoten und Kanten), deren Eigenschaften und ihre Beziehungen zueinander.

Ungerichteter Graph mit sechs Knoten.

Graphen sind mathematische Modelle für netzartige Strukturen in Natur und Technik (wie soziale Strukturen, Straßennetze, Computernetze, elektrische Schaltungen, Versorgungsnetze oder chemische Moleküle). In der Graphentheorie untersucht man lediglich die abstrakte Netzstruktur an sich. Die Art, Lage und Beschaffenheit der Knoten und Kanten bleibt unberücksichtigt. Es verbleiben jedoch viele allgemeingültige Graphen-Eigenschaften, die bereits auf dieser Abstraktionsstufe untersucht werden können und sich in allgemeingültigen Aussagen (Sätze der Graphentheorie) wiederfinden.[1] Ein Beispiel hierfür ist das Handschlaglemma, wonach die Summe der Knotengrade in einem Graphen stets gerade ist (in der nebenstehenden Abbildung: vierzehn).

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. Graphen werden insbesondere durch die Datenstrukturen Adjazenzmatrix, Inzidenzmatrix oder Adjazenzliste repräsentiert.

GeschichteBearbeiten

 
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 grafisch) 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.

1852 bemerkte der Mathematiker und Botaniker Francis Gutherie, dass vier Farben reichen, um eine Landkarte so zu färben, dass zwei aneinander grenzende Länder stets unterschiedlich gefärbt sind. Viele Mathematiker beschäftigten sich mit diesem Färbungsproblem. Es dauerte jedoch bis 1976 bis der Vier-Farben-Satz mittels Computer bewiesen werden konnte.[2] Erst 1997 stellten Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas einen neuen Beweis vor.[3]

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

In der zweiten Hälfte des 20. Jahrhunderts hat William Thomas Tutte maßgeblich an der Weiterentwicklung der Graphentheorie gearbeitet und dieses Teilgebiet der Mathematik stark geprägt.

Teilgebiete der GraphentheorieBearbeiten

Teilgebiete der Graphentheorie sind:

Betrachteter GegenstandBearbeiten

 
Graph mit Artikulation und Brücke

In der Graphentheorie bezeichnet ein Graph eine Menge von Knoten (auch Ecken oder Punkte genannt) zusammen mit einer Menge von Kanten. Eine Kante ist hierbei eine Menge von genau zwei Knoten. Sie gibt an, ob zwei Knoten miteinander in Beziehung stehen, bzw. ob sie in der bildlichen Darstellung des Graphen verbunden sind. Zwei Knoten, die durch eine Kante verbunden sind, heißen benachbart oder adjazent. Wenn die Kanten statt durch Mengen durch geordnete 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. 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.

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

Ist die Menge der Knoten endlich, spricht man von endlichen Graphen, ansonsten von unendlichen Graphen.

GrapheigenschaftenBearbeiten

 
Zusammenhangskomponenten

Graphen können verschiedene Eigenschaften haben. So kann ein Graph

Es kann nach der Existenz spezieller Teilgraphen oder Minoren gefragt werden oder bestimmte Parameter untersucht werden, wie zum Beispiel Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite, Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, Bogenzusammenhangszahl, chromatische Zahl, Knotenüberdeckungszahl (Faktor), Unabhängigkeitszahl (Stabilitätszahl) oder Cliquenzahl. Zwei Graphen können isomorph (strukturell gleich) oder automorph zueinander sein.

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 fünf. Diese Aussage ist auch als der Vier-Farben-Satz bekannt.

 
gerichteter zyklischer Graph

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 exakt zu bestimmen. Allerdings kann in diesen Fällen der Einsatz von heuristischen Verfahren zu sinnvollen Näherungslösungen führen.

GraphenklassenBearbeiten

 
Bipartiter Graph

Grundsätzlich werden Graphen in gerichtete und ungerichtete Graphen unterteilt.

Aufgrund des Zusammenhangs unterscheidet man:

Aufgrund des Vorhandenseins bestimmter Eigenschaften lassen sich weitere Graphenklassen unterscheiden wie

Wenn ein Knoten besonders ausgezeichnet ist, spricht man von einer Wurzel bzw. einem gewurzeltem Graphen. Besondere Bedeutung haben gewurzelte Bäume unter anderem auch als Baumstruktur.

ProblemeBearbeiten

Die wichtigsten Probleme und Ergebnisse der Graphentheorie werden im Folgenden dargestellt:

 
Graphfärbung

FärbungBearbeiten

Ein 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 vier 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 PNP, ist selbst eine bis auf einen konstanten Faktor angenäherte Lösung nicht effizient möglich.

SuchproblemeBearbeiten

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. (siehe auch: Kategorie:Graphsuchalgorithmen)

 
Handlungsreisendenproblem

Durchlaufbarkeit von GraphenBearbeiten

Algorithmisch deutlich schwieriger ist die Bestimmung einer kürzesten Rundreise (siehe Problem des Handlungsreisenden), bei der alle Orte eines Straßennetzes 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 PNP (siehe P-NP-Problem), existiert kein effizienter Algorithmus für die Bestimmung einer optimalen Lösung, da dieses Problem NP-schwer ist.

Das Königsberger Brückenproblem fragt nach der Existenz eines Eulerkreises. Während sich das Eulerkreisproblem mittels Hierholzer-Verfahren in linearer Zeit lösen lässt, ist das Finden eines Hamiltonkreises (ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält) NP-schwierig. Beim Briefträgerproblem wird nach einem kürzesten Zyklus gefragt, der alle Kanten mindestens einmal durchläuft.

ZusammenhangBearbeiten

Beim Zusammenhang wird gefragt, ob bzw. über wie viele Wege zwei Knoten untereinander erreichbar sind. Dies spielt beispielsweise bei der Beurteilung der Versorgungsnetze hinsichtlich der kritischen (ausfallbedrohten Teile) eine Rolle.

 
Graph mit Cliquen

CliquenproblemBearbeiten

Die Frage nach dem Vorhandensein (ggf. maximaler) Cliquen sucht die Teile eines Graphen, die untereinander vollständig mit Kanten verbunden sind.

KnotenüberdeckungBearbeiten

Das Knotenüberdeckungsproblem sucht nach einer Teilmenge von Knoten eines Graphen, die von jeder Kante mindestens einen Endknoten enthält.

Flüsse und Schnitte in NetzwerkenBearbeiten

Mit der Frage nach dem maximalen Fluss lassen sich Versorgungsnetze hinsichtlich ihrer Kapazität beurteilen.

 
Matching im bipartiten Graphen

MatchingBearbeiten

Matchingprobleme, die sich auf Flussprobleme zurückführen lassen, fragen nach der optimalen Auswahl von Kanten, so dass keine zwei Kanten inzident zu einem Knoten sind. Damit lassen sich Zuordnungsprobleme, beispielsweise der Ressourcennutzung wie Raum- oder Maschinenbelegung lösen.

Weitere GraphenproblemeBearbeiten

Zu den weiteren Graphenproblemen zählen

Siehe auchBearbeiten

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

LiteraturBearbeiten

  • Martin Aigner: Graphentheorie: eine Entwicklung aus dem 4-Farben-Problem. 1984 (269 Seiten).
  • 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. 2. Auflage. Springer, Berlin/Heidelberg 2003, ISBN 3-540-00045-3.
  • Peter Tittmann: Graphentheorie. Eine anwendungsorientierte Einführung. 3. Auflage. Hanser, München 2019, ISBN 978-3-446-46052-2.

WeblinksBearbeiten

Wikibooks: Mathematik-Glossar: Graphentheorie – Lern- und Lehrmaterialien
Wiktionary: Graphentheorie – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

EinzelnachweiseBearbeiten

  1. Peter Tittmann: Graphentheorie. Eine anwendungsorientierte Einführung. 3., aktualisierte Auflage. München, ISBN 978-3-446-46052-2, S. 1.
  2. Peter Tittmann: Graphentheorie. Eine anwendungsorientierte Einführung. 3., aktualisierte Auflage. München, ISBN 978-3-446-46052-2, S. 76.
  3. Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas: The Four-Colour Theorem. In: Journal of Combinatorial Theory, Series B. Band 70, Nr. 1, 1997, ISSN 0095-8956, S. 2–44.
  4. James Joseph Sylvester: Chemistry and Algebra. In: Nature. Band 17, 1878, S. 284.
  5. Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson: Graph Theory 1736–1936. Oxford University Press, 1999, ISBN 0-19-853916-9.
  6. Arthur Cayley: Chemical Graphs. In: Philosophical Magazine. Band 47, 1874, S. 444–446.
  7. Dénes Kőnig: Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe. Akademische Verlagsgesellschaft, Leipzig 1936.