Wikipedia · einfach zusammengefasst · Stand
Graphentheorie
Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Betrachtungsgegenstand der …
Inhalt6 Abschnitte
Grundidee und Bedeutung
Die Graphentheorie ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Sie untersucht Graphen, also Mengen von Knoten und Kanten, ihre Eigenschaften und ihre Beziehungen zueinander. Graphen dienen als mathematische Modelle für netzartige Strukturen, zum Beispiel soziale Strukturen, Straßennetze, Verwandtschaftsbeziehungen, Computernetze, elektrische Schaltungen, Versorgungsnetze oder Moleküle.
Wichtig ist die Abstraktion: In der Graphentheorie zählt nicht, wie Knoten und Kanten konkret aussehen, wo sie liegen oder woraus sie bestehen. Untersucht wird nur die Netzstruktur. Dadurch lassen sich allgemeine Aussagen formulieren. Ein Beispiel ist das Handschlaglemma: Die Summe der Knotengrade in einem Graphen ist stets gerade; im abgebildeten Beispiel beträgt sie 14.
Für die Informatik ist die Graphentheorie besonders wichtig, weil viele algorithmische Probleme als Graphenprobleme formuliert werden können. Umgekehrt beruhen Lösungen graphentheoretischer Probleme oft auf Algorithmen. Viele Aufgaben der kombinatorischen Optimierung lassen sich in der Sprache der Graphentheorie beschreiben; graphentheoretische Probleme können auch als lineare ganzzahlige Optimierungsprobleme modelliert werden. Graphen werden häufig durch Adjazenzmatrix, Inzidenzmatrix oder Adjazenzliste repräsentiert.
Graphen und ihre Arten
Ein Graph besteht aus einer Menge von Knoten, auch Ecken oder Punkte genannt, und einer Menge von Kanten. Eine Kante ist eine Menge von genau zwei Knoten und zeigt, dass diese beiden Knoten in Beziehung stehen oder in einer Zeichnung verbunden sind. Zwei durch eine Kante verbundene Knoten heißen benachbart oder adjazent.
Wenn Kanten nicht als Mengen, sondern als geordnete Paare von Knoten angegeben werden, spricht man von gerichteten Graphen. Dann unterscheidet man zum Beispiel die Kante (a,b), also von Knoten a zu Knoten b, von der Kante (b,a), also von Knoten b zu Knoten a. Knoten und Kanten können außerdem Farben tragen, formal natürliche Zahlen, oder Gewichte, also rationale oder reelle Zahlen. Dann spricht man von knoten- oder kantengefärbten beziehungsweise knoten- oder kantengewichteten Graphen.
Komplexere Graphentypen sind Multigraphen, Hypergraphen und Petri-Netze. Bei Multigraphen ist die Kantenmenge eine Multimenge. Bei Hypergraphen kann eine Kante eine beliebig große Menge von Knoten darstellen; solche Kanten heißen Hyperkanten. Petri-Netze besitzen zwei Arten von Knoten. Ist die Menge der Knoten endlich, heißt der Graph endlich; sonst heißt er unendlich.
Eigenschaften und Klassen
Graphen können viele Eigenschaften besitzen. Ein Graph kann zusammenhängend sein, allgemein k-zusammenhängend, bipartit, allgemein k-partit, planar, eulersch oder hamiltonisch. Außerdem kann man nach speziellen Teilgraphen oder Minoren fragen oder bestimmte Parameter untersuchen. Dazu gehören Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite, Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, Bogenzusammenhangszahl, chromatische Zahl, Knotenüberdeckungszahl, Unabhängigkeitszahl beziehungsweise Stabilitätszahl und Cliquenzahl.
Zwei Graphen können isomorph sein, also strukturell gleich, oder automorph zueinander sein. Grapheneigenschaften können miteinander zusammenhängen. Zum Beispiel ist die Knotenzusammenhangszahl nie größer als die Kantenzusammenhangszahl; diese ist wiederum nie größer als der Minimalgrad des betrachteten Graphen. In ebenen Graphen ist die Färbungszahl immer kleiner als fünf. Diese Aussage ist als Vier-Farben-Satz bekannt.
Grundsätzlich unterscheidet man gerichtete und ungerichtete Graphen. Nach dem Zusammenhang gibt es azyklische Graphen wie Weg oder Pfad, Wald, Baum und DAG (directed acyclic graph), sowie zyklische Graphen wie Zyklus, Kreis und vollständige Graphen. Nach bestimmten Eigenschaften unterscheidet man unter anderem bipartite, graziöse, planare, reguläre, chordale, perfekte und magische Graphen. Wenn ein Knoten besonders ausgezeichnet ist, spricht man von einer Wurzel oder einem gewurzelten Graphen; gewurzelte Bäume sind unter anderem als Baumstruktur wichtig.
Wichtige Teilgebiete
Die Graphentheorie umfasst mehrere Teilgebiete. Die algorithmische Graphentheorie beschäftigt sich mit Algorithmen, die auf Graphen anwendbar sind. Die chemische Graphentheorie gehört zu den frühen Anwendungen und nutzt Graphen zur Beschreibung chemischer Molekülstrukturen.
Die extremale Graphentheorie untersucht, welche Graphen einer gegebenen Klasse einen bestimmten Graphenparameter maximieren oder minimieren. Geometrische und topologische Graphentheorie betrachten Einbettungen von Graphen in Ebenen und andere geometrische Objekte. In der Netzwerkforschung werden komplexe Netzwerke empirisch untersucht, mit Anwendungen etwa in Biologie, Wirtschaftswissenschaften und Soziologie.
Die probabilistische Graphentheorie nutzt Zufallsgraphen, um Eigenschaften für beliebig große Graphen nachzuweisen. Die spektrale Graphentheorie, auch algebraische Graphentheorie genannt, untersucht Graphen über ihre Adjazenzmatrizen und Laplace-Matrizen. Dabei werden Eigenwerte, Eigenvektoren und charakteristische Polynome analysiert. Ungerichtete Graphen haben symmetrische Adjazenzmatrizen und daher reelle Eigenwerte. Alle Eigenwerte zusammen heißen Spektrum des Graphen. Die Adjazenzmatrix hängt von der Knotensortierung ab, das Spektrum dagegen nicht.
Zentrale Probleme
Ein klassisches Problem ist die Graphfärbung. Dabei fragt man, wie viele Farben nötig sind, um zum Beispiel Länder einer Landkarte so einzufärben, dass benachbarte Länder unterschiedliche Farben haben. Die Nachbarschaft der Länder kann als planarer Graph dargestellt werden; das Problem wird dann als Knoten-Färbungsproblem modelliert. Nach dem Vier-Farben-Satz reichen maximal vier Farben. Ob ein allgemeiner Graph mit weniger Farben gefärbt werden kann, lässt sich nach heutigem Wissensstand nicht effizient entscheiden. Das Problem gehört zu den NP-vollständigen Problemen. Unter der Voraussetzung P≠NP ist selbst eine bis auf einen konstanten Faktor angenäherte Lösung nicht effizient möglich.
Suchprobleme fragen oft nach einer kürzesten Route zwischen zwei Orten in einem Straßennetz. Dazu werden Orte als Knoten und Verbindungen als Kanten modelliert. Die Kanten können gewichtet werden, etwa mit der Länge der Verbindung. Mit Algorithmen für kürzeste Pfade, zum Beispiel dem Algorithmus von Dijkstra, kann eine kürzeste Verbindung effizient gefunden werden.
Schwieriger ist die Suche nach einer kürzesten Rundreise, bei der alle Orte eines Straßennetzes genau einmal besucht werden müssen; dies ist das Problem des Handlungsreisenden. Die Zahl möglicher Rundreisen wächst faktoriell mit der Zahl der Orte. Deshalb ist ein naiver Algorithmus, der alle Rundreisen ausprobiert, nur für sehr kleine Netzwerke praktikabel. Es gibt Approximationsalgorithmen, die gute, aber nicht unbedingt optimale Rundreisen finden. Die Christofides-Heuristik liefert eine Rundreise, die maximal 1,5-mal so lang ist wie die bestmögliche. Unter der Annahme P≠NP gibt es keinen effizienten Algorithmus für eine optimale Lösung, da das Problem NP-schwer ist.
Weitere Aufgaben und Geschichte
Das Königsberger Brückenproblem fragt nach der Existenz eines Eulerkreises. Dieses Problem löste Leonhard Euler 1736 und zeigte, dass es für Königsberg keinen Rundgang gibt, der jede der sieben Brücken über den Pregel genau einmal benutzt. Das Eulerkreisproblem lässt sich mit dem Hierholzer-Verfahren in linearer Zeit lösen. Dagegen ist das Finden eines Hamiltonkreises NP-schwierig; ein Hamiltonkreis ist ein geschlossener Pfad, der jeden Knoten genau einmal enthält. Beim Briefträgerproblem sucht man einen kürzesten Zyklus, der alle Kanten mindestens einmal durchläuft.
Weitere wichtige Aufgaben betreffen den Zusammenhang, also ob und über wie viele Wege zwei Knoten erreichbar sind, etwa zur Beurteilung kritischer Teile in Versorgungsnetzen. Das Cliquenproblem fragt nach Teilmengen eines Graphen, in denen alle Knoten paarweise durch Kanten verbunden sind. Das Knotenüberdeckungsproblem sucht eine Teilmenge von Knoten, die von jeder Kante mindestens einen Endknoten enthält. Flussprobleme untersuchen zum Beispiel den maximalen Fluss und damit die Kapazität von Versorgungsnetzen. Matchingprobleme fragen nach einer optimalen Auswahl von Kanten, sodass keine zwei Kanten inzident zu einem Knoten sind; damit lassen sich Zuordnungsprobleme wie Raum- oder Maschinenbelegung modellieren.
Historisch gelten Euler und das Königsberger Brückenproblem als wichtige Anfänge der Graphentheorie. 1852 formulierte Francis Guthrie das Färbungsproblem für Landkarten. Der Vier-Farben-Satz wurde 1976 mithilfe eines Computers bewiesen; 1997 legten Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas einen neuen Beweis vor. Der Begriff Graph wurde 1878 von James Joseph Sylvester verwendet. Arthur Cayley gilt ebenfalls als Begründer der frühen Graphentheorie. Das erste Lehrbuch erschien 1936 von Dénes Kőnig. In der zweiten Hälfte des 20. Jahrhunderts prägte William Thomas Tutte die Weiterentwicklung der Graphentheorie stark.
