Graphentheorie

Ungerichteter Graph mit sechs Knoten. ⓘ

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. ⓘ

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. 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. ⓘ

Eine Zeichnung eines Graphen. ⓘ

Definitionen

In der Graphentheorie gibt es unterschiedliche Definitionen. Im Folgenden finden Sie einige der grundlegenden Definitionen von Graphen und verwandten mathematischen Strukturen. ⓘ

Graph

Ein Graph mit drei Eckpunkten und drei Kanten. ⓘ

In einer eingeschränkten, aber sehr gebräuchlichen Bedeutung des Begriffs ist ein Graph ein geordnetes Paar $G=(V,E)$ bestehend aus:

• $V$einer Menge von Scheitelpunkten (auch Knoten oder Punkte genannt);
• $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$eine Menge von Kanten (auch Verbindungen oder Linien genannt), die ungeordnete Paare von Scheitelpunkten sind (d. h. eine Kante ist mit zwei verschiedenen Scheitelpunkten verbunden). ⓘ

Um Mehrdeutigkeiten zu vermeiden, kann diese Art von Objekt auch als ungerichteter einfacher Graph bezeichnet werden. ⓘ

In der Kante $\{x,y\}$sind die Scheitelpunkte $x$ und $y$ werden als Endpunkte der Kante bezeichnet. Man sagt, die Kante verbindet $x$ und $y$ und einfallend auf $x$ und auf $y$. Ein Knoten kann in einem Graphen vorhanden sein und nicht zu einer Kante gehören. Mehrere Kanten, die nach der obigen Definition nicht zulässig sind, sind zwei oder mehr Kanten, die dieselben zwei Knoten verbinden. ⓘ

In einer allgemeineren Bedeutung des Begriffs, die mehrere Kanten zulässt, ist ein Graph ein geordnetes Tripel $G=(V,E,\phi )$ bestehend aus:

• $V$einer Menge von Scheitelpunkten (auch Knoten oder Punkte genannt);
• $E$, eine Menge von Kanten (auch Verbindungen oder Linien genannt);
• $\phi :E\to \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$eine Inzidenzfunktion, die jede Kante auf ein ungeordnetes Paar von Scheitelpunkten abbildet (d. h. eine Kante ist mit zwei verschiedenen Scheitelpunkten verbunden). ⓘ

Um Mehrdeutigkeiten zu vermeiden, kann diese Art von Objekt auch als ungerichteter Multigraph bezeichnet werden. ⓘ

Eine Schleife ist eine Kante, die einen Scheitelpunkt mit sich selbst verbindet. Graphen im Sinne der beiden obigen Definitionen können keine Schleifen enthalten, da eine Schleife, die einen Scheitelpunkt $x$ mit sich selbst verbindet, ist eine Kante (bei einem ungerichteten einfachen Graphen) oder eine Inzidenz (bei einem ungerichteten Multigraphen) $\{x,x\}=\{x\}$ die nicht in $\{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$. Um Schleifen zuzulassen, müssen die Definitionen also erweitert werden. Für ungerichtete einfache Graphen muss die Definition von $E$ geändert werden in $E\subseteq \{\{x,y\}\mid x,y\in V\}$. Für ungerichtete Multigraphen sollte die Definition von $\phi$ geändert werden in $\phi :E\to \{\{x,y\}\mid x,y\in V\}$. Um Mehrdeutigkeit zu vermeiden, können diese Arten von Objekten als ungerichtete einfache Graphen, die Schleifen zulassen, bzw. ungerichtete Multigraphen, die Schleifen zulassen (manchmal auch ungerichtete Pseudographen), bezeichnet werden. ⓘ

$V$ und $E$ Viele der bekannten Ergebnisse sind für unendliche Graphen nicht zutreffend (oder sehen ganz anders aus), da viele der Argumente im unendlichen Fall versagen. Außerdem wird $V$ oft als nicht-leer angenommen, aber $E$ darf die leere Menge sein. Die Ordnung eines Graphen ist $|V|$, seine Anzahl von Knotenpunkten. Die Größe eines Graphen ist $|E|$, seine Anzahl der Kanten. Der Grad oder die Wertigkeit eines Scheitelpunkts ist die Anzahl der Kanten, die mit ihm verbunden sind, wobei eine Schleife doppelt gezählt wird. Der Grad eines Graphen ist das Maximum der Grade seiner Scheitelpunkte. ⓘ

In einem ungerichteten einfachen Graphen der Ordnung n ist der maximale Grad jedes Scheitelpunkts n - 1 und die maximale Größe des Graphen ist n(n - 1)/2. ⓘ

Die Kanten eines ungerichteten einfachen Graphen, die Schleifen zulassen $G$ induzieren eine symmetrische homogene Beziehung ~ auf den Scheitelpunkten von $G$ die als Adjazenzrelation von $G$. Konkret bedeutet dies, dass für jede Kante $(x,y)$ihre Endpunkte $x$ und $y$ als benachbart zueinander, was als $x$ ~ $y$. ⓘ

Gerichtetes Diagramm

Ein gerichteter Graph mit drei Scheitelpunkten und vier gerichteten Kanten (der Doppelpfeil steht für eine Kante in jeder Richtung). ⓘ

Ein gerichteter Graph oder Digraph ist ein Graph, in dem die Kanten Orientierungen haben. ⓘ

In einer eingeschränkten, aber sehr gebräuchlichen Bedeutung des Begriffs ist ein gerichteter Graph ein geordnetes Paar $G=(V,E)$ bestehend aus:

• $V$einer Menge von Scheitelpunkten (auch Knoten oder Punkte genannt);
• $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$Ein gerichteter Graph ist ein geordnetes Paar von Kanten (auch gerichtete Kanten, gerichtete Verbindungen, gerichtete Linien, Pfeile oder Bögen genannt), die geordnete Paare von Scheitelpunkten sind (d. h. eine Kante ist mit zwei verschiedenen Scheitelpunkten verbunden). ⓘ

Um Mehrdeutigkeiten zu vermeiden, kann diese Art von Objekt auch als gerichteter einfacher Graph bezeichnet werden. ⓘ

In der Kante $(x,y)$ gerichtet von $x$ nach $y$sind die Scheitelpunkte $x$ und $y$ werden die Endpunkte der Kante genannt, $x$ das Ende der Kante und $y$ der Kopf der Kante. Man sagt, die Kante verbindet $x$ und $y$ und einfallend auf $x$ und auf $y$. Ein Knoten kann in einem Graphen vorhanden sein und nicht zu einer Kante gehören. Die Kante $(y,x)$ wird als invertierte Kante von $(x,y)$. Mehrfachkanten, die nach der obigen Definition nicht zulässig sind, sind zwei oder mehr Kanten, die sowohl den gleichen Schwanz als auch den gleichen Kopf haben. ⓘ

In einer allgemeineren Bedeutung des Begriffs, die mehrere Kanten zulässt, ist ein gerichteter Graph ein geordnetes Tripel $G=(V,E,\phi )$ bestehend aus:

• $V$einer Menge von Scheitelpunkten (auch Knoten oder Punkte genannt);
• $E$, eine Menge von Kanten (auch gerichtete Kanten, gerichtete Verbindungen, gerichtete Linien, Pfeile oder Bögen genannt)
• $\phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$eine Inzidenzfunktion, die jede Kante auf ein geordnetes Paar von Scheitelpunkten abbildet (d. h. eine Kante ist mit zwei verschiedenen Scheitelpunkten verbunden). ⓘ

Um Mehrdeutigkeiten zu vermeiden, kann diese Art von Objekt auch als gerichteter Multigraph bezeichnet werden. ⓘ

Eine Schleife ist eine Kante, die einen Scheitelpunkt mit sich selbst verbindet. Gerichtete Graphen im Sinne der beiden obigen Definitionen können keine Schleifen enthalten, da eine Schleife, die einen Scheitelpunkt $x$ mit sich selbst verbindet, die Kante ist (bei einem gerichteten einfachen Graphen) oder auf ihr liegt (bei einem gerichteten Multigraphen) $(x,x)$ die nicht in $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$. Um Schleifen zuzulassen, müssen die Definitionen also erweitert werden. Für gerichtete einfache Graphen ist die Definition von $E$ geändert werden in $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$. Für gerichtete Multigraphen wird die Definition von $\phi$ geändert werden in $\phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\right\}$. Um Mehrdeutigkeit zu vermeiden, können diese Arten von Objekten als gerichteter einfacher Graph, der Schleifen zulässt, bzw. als gerichteter Multigraph, der Schleifen zulässt (oder als Köcher) bezeichnet werden. ⓘ

Die Kanten eines gerichteten einfachen Graphen, der Schleifen zulässt $G$ ist eine homogene Beziehung ~ auf den Eckpunkten von $G$ die als Adjazenzrelation von $G$. Konkret bedeutet dies, dass für jede Kante $(x,y)$ihre Endpunkte $x$ und $y$ als benachbart zueinander, was als $x$ ~ $y$. ⓘ

Anwendungen

Der Netzwerkgraph, der von Wikipedia-Redakteuren (Kanten) gebildet wurde, die während eines Monats im Sommer 2013 zu verschiedenen Wikipedia-Sprachversionen (Scheitelpunkten) beigetragen haben. ⓘ

Graphen können zur Modellierung vieler Arten von Beziehungen und Prozessen in physikalischen, biologischen, sozialen und Informationssystemen verwendet werden. Viele praktische Probleme können durch Graphen dargestellt werden. Um ihre Anwendung auf reale Systeme zu betonen, wird der Begriff Netzwerk manchmal so definiert, dass er einen Graphen bezeichnet, in dem Attribute (z. B. Namen) mit den Eckpunkten und Kanten verbunden sind, und das Fach, das reale Systeme als Netzwerk ausdrückt und versteht, wird Netzwerkwissenschaft genannt. ⓘ

Computerwissenschaft

Der Zweig der Informatik, der als Datenstrukturen bekannt ist, verwendet Graphen, um Kommunikationsnetze, Datenorganisation, Rechengeräte, den Ablauf von Berechnungen usw. darzustellen. So kann beispielsweise die Linkstruktur einer Website durch einen gerichteten Graphen dargestellt werden, in dem die Eckpunkte Webseiten darstellen und die gerichteten Kanten Links von einer Seite zur anderen bedeuten. Ein ähnlicher Ansatz kann für Probleme in den sozialen Medien, im Reiseverkehr, in der Biologie, bei der Entwicklung von Computerchips, bei der Darstellung des Verlaufs von neurodegenerativen Krankheiten und in vielen anderen Bereichen gewählt werden. Die Entwicklung von Algorithmen zur Verarbeitung von Graphen ist daher von großem Interesse für die Informatik. Die Umwandlung von Graphen wird häufig formalisiert und durch Graph-Rewrite-Systeme dargestellt. Ergänzend zu Graphenumwandlungssystemen, die sich auf die regelbasierte In-Memory-Verarbeitung von Graphen konzentrieren, gibt es Graphendatenbanken, die auf die transaktionssichere, dauerhafte Speicherung und Abfrage von graphenstrukturierten Daten ausgerichtet sind. ⓘ

Linguistik

Graphentheoretische Methoden in verschiedenen Formen haben sich in der Linguistik als besonders nützlich erwiesen, da sich die natürliche Sprache oft gut für diskrete Strukturen eignet. Traditionell folgen Syntax und kompositionelle Semantik baumbasierten Strukturen, deren Ausdruckskraft auf dem Prinzip der Kompositionalität beruht, die in einem hierarchischen Graphen modelliert wird. Neuere Ansätze wie die kopfgesteuerte Phrasenstrukturgrammatik modellieren die Syntax der natürlichen Sprache mit typisierten Merkmalsstrukturen, die gerichtete azyklische Graphen sind. In der lexikalischen Semantik, insbesondere bei der Anwendung auf Computer, ist die Modellierung der Wortbedeutung einfacher, wenn ein bestimmtes Wort in Form von verwandten Wörtern verstanden wird; semantische Netzwerke sind daher in der Computerlinguistik wichtig. Auch andere Methoden in der Phonologie (z. B. die Optimalitätstheorie, die Gittergraphen verwendet) und der Morphologie (z. B. die Finite-State-Morphologie, die Finite-State-Transducer verwendet) sind bei der Analyse von Sprache als Graph üblich. Die Nützlichkeit dieses Bereichs der Mathematik für die Linguistik hat Organisationen wie TextGraphs sowie verschiedene "Netz"-Projekte wie WordNet, VerbNet und andere entstehen lassen. ⓘ

Physik und Chemie

Die Graphentheorie wird auch zur Untersuchung von Molekülen in der Chemie und Physik verwendet. In der Physik der kondensierten Materie kann die dreidimensionale Struktur komplizierter simulierter atomarer Strukturen quantitativ untersucht werden, indem Statistiken über graphentheoretische Eigenschaften im Zusammenhang mit der Topologie der Atome gesammelt werden. Außerdem "fassen die Feynman-Graphen und Rechenregeln die Quantenfeldtheorie in einer Form zusammen, die in engem Kontakt mit den experimentellen Zahlen steht, die man verstehen möchte." In der Chemie ist ein Graph ein natürliches Modell für ein Molekül, bei dem die Eckpunkte die Atome und die Kanten die Bindungen darstellen. Dieser Ansatz wird insbesondere bei der Computerverarbeitung von Molekülstrukturen verwendet, von chemischen Editoren bis hin zur Datenbanksuche. In der statistischen Physik können Graphen lokale Verbindungen zwischen interagierenden Teilen eines Systems sowie die Dynamik eines physikalischen Prozesses auf solchen Systemen darstellen. Systeme darstellen. In ähnlicher Weise können Graphen in den Computer-Neurowissenschaften zur Darstellung funktioneller Verbindungen zwischen Gehirnbereichen verwendet werden, die interagieren, um verschiedene kognitive Prozesse hervorzurufen, wobei die Eckpunkte verschiedene Bereiche des Gehirns und die Kanten die Verbindungen zwischen diesen Bereichen darstellen. Die Graphentheorie spielt eine wichtige Rolle bei der elektrischen Modellierung elektrischer Netze. Hier werden die Gewichte mit dem Widerstand der Drahtsegmente in Verbindung gebracht, um elektrische Eigenschaften der Netzstrukturen zu erhalten. Graphen werden auch zur Darstellung der mikroskaligen Kanäle poröser Medien verwendet, wobei die Eckpunkte die Poren und die Kanten die kleineren Kanäle darstellen, die die Poren verbinden. Die chemische Graphentheorie verwendet den molekularen Graphen als Mittel zur Modellierung von Molekülen. Graphen und Netzwerke sind hervorragende Modelle zur Untersuchung und zum Verständnis von Phasenübergängen und kritischen Phänomenen. Das Entfernen von Knoten oder Kanten führt zu einem kritischen Übergang, bei dem das Netzwerk in kleine Cluster zerfällt, was als Phasenübergang untersucht wird. Dieser Zusammenbruch wird mit Hilfe der Perkolationstheorie untersucht. ⓘ

Sozialwissenschaften

Graphentheorie in der Soziologie: Soziogramm von Moreno (1953). ⓘ

Die Graphentheorie ist auch in der Soziologie weit verbreitet, z. B. um das Prestige von Akteuren zu messen oder die Verbreitung von Gerüchten zu untersuchen, insbesondere durch den Einsatz von Software zur Analyse sozialer Netzwerke. Unter dem Oberbegriff der sozialen Netzwerke gibt es viele verschiedene Arten von Graphen. Bekanntschafts- und Freundschaftsgraphen beschreiben, ob Menschen einander kennen. Einflussdiagramme beschreiben, ob bestimmte Personen das Verhalten anderer beeinflussen können. Kollaborationsgraphen schließlich beschreiben, ob zwei Personen auf eine bestimmte Weise zusammenarbeiten, z. B. in einem Film mitspielen. ⓘ

Biologie

Die Graphentheorie ist auch in der Biologie und bei Naturschutzbemühungen nützlich, wo ein Knoten Regionen darstellen kann, in denen bestimmte Arten vorkommen (oder leben), und die Kanten Migrationspfade oder Bewegungen zwischen den Regionen darstellen. Diese Informationen sind wichtig, wenn es darum geht, Fortpflanzungsmuster zu untersuchen oder die Ausbreitung von Krankheiten und Parasiten zu verfolgen oder festzustellen, wie sich Veränderungen in der Bewegung auf andere Arten auswirken können. ⓘ

Graphen werden auch häufig in der Molekularbiologie und Genomik zur Modellierung und Analyse von Datensätzen mit komplexen Beziehungen verwendet. So werden beispielsweise graphenbasierte Methoden häufig verwendet, um bei der Einzelzell-Transkriptomanalyse Zellen zu Zelltypen zu "clustern". Eine weitere Anwendung ist die Modellierung von Genen oder Proteinen in einem Pfad und die Untersuchung der Beziehungen zwischen ihnen, wie z. B. Stoffwechselwege und genregulatorische Netzwerke. Evolutionsbäume, ökologische Netzwerke und hierarchische Cluster von Genexpressionsmustern werden ebenfalls als Graphenstrukturen dargestellt. ⓘ

Die Graphentheorie wird auch in der Konnektomik verwendet; Nervensysteme können als Graph dargestellt werden, wobei die Knoten Neuronen und die Kanten die Verbindungen zwischen ihnen sind. ⓘ

Mathematik

In der Mathematik sind Graphen in der Geometrie und bestimmten Bereichen der Topologie wie der Knotentheorie nützlich. Die algebraische Graphentheorie hat enge Verbindungen zur Gruppentheorie. Die algebraische Graphentheorie wurde in vielen Bereichen angewandt, darunter dynamische Systeme und Komplexität. ⓘ

Andere Themen

Eine Graphenstruktur kann erweitert werden, indem jeder Kante des Graphen ein Gewicht zugewiesen wird. Graphen mit Gewichten oder gewichtete Graphen werden verwendet, um Strukturen darzustellen, in denen paarweise Verbindungen einen numerischen Wert haben. Stellt ein Graph beispielsweise ein Straßennetz dar, könnten die Gewichte die Länge der einzelnen Straßen repräsentieren. Jeder Kante können mehrere Gewichte zugeordnet sein, z. B. die Entfernung (wie im vorherigen Beispiel), die Fahrzeit oder die Kosten. Solche gewichteten Graphen werden häufig zur Programmierung von GPS-Geräten und Reiseplanungs-Suchmaschinen verwendet, die Flugzeiten und -kosten vergleichen. ⓘ

Geschichte

Das Königsberger Brückenproblem ⓘ

Die von Leonhard Euler verfasste und 1736 veröffentlichte Abhandlung über die sieben Brücken von Königsberg gilt als die erste Abhandlung in der Geschichte der Graphentheorie. Diese Arbeit sowie die von Vandermonde verfasste Arbeit über das Ritterproblem setzten den von Leibniz initiierten Analysesitus fort. Eulers Formel über die Anzahl der Kanten, Eckpunkte und Flächen eines konvexen Polyeders wurde von Cauchy und L'Huilier untersucht und verallgemeinert und stellt den Beginn des als Topologie bekannten Zweigs der Mathematik dar. ⓘ

Mehr als ein Jahrhundert nach Eulers Arbeit über die Brücken von Königsberg und während Listing das Konzept der Topologie einführte, wurde Cayley durch sein Interesse an bestimmten analytischen Formen, die sich aus der Differentialrechnung ergeben, dazu veranlasst, eine bestimmte Klasse von Graphen, die Bäume, zu untersuchen. Diese Studie hatte viele Auswirkungen auf die theoretische Chemie. Die von ihm verwendeten Techniken betreffen hauptsächlich die Aufzählung von Graphen mit bestimmten Eigenschaften. Die enumerative Graphentheorie entstand dann aus den Ergebnissen von Cayley und den von Pólya zwischen 1935 und 1937 veröffentlichten grundlegenden Ergebnissen. Diese wurden 1959 von De Bruijn verallgemeinert. Cayley verknüpfte seine Ergebnisse über Bäume mit zeitgenössischen Studien über die chemische Zusammensetzung. Die Verschmelzung von Ideen aus der Mathematik mit denen aus der Chemie führte zu dem, was heute zur Standardterminologie der Graphentheorie gehört. ⓘ

Der Begriff "Graph" wurde insbesondere von Sylvester in einem 1878 in Nature veröffentlichten Aufsatz eingeführt, in dem er eine Analogie zwischen "quantischen Invarianten" und "Co-Varianten" von Algebra und Moleküldiagrammen zieht:

"[...] Jede Invariante und Kovariante wird so durch einen Graphen ausdrückbar, der genau mit einem Kekuléschen Diagramm oder Chemikographen identisch ist. [...] Ich gebe eine Regel für die geometrische Multiplikation von Graphen, d.h. für die Konstruktion eines Graphen zum Produkt von Invarianten oder Kovarianten, deren einzelne Graphen gegeben sind. [...]" (kursiv wie im Original). ⓘ

Das erste Lehrbuch über Graphentheorie wurde von Dénes Kőnig geschrieben und 1936 veröffentlicht. Ein weiteres Buch von Frank Harary, das 1969 veröffentlicht wurde, galt "weltweit als das endgültige Lehrbuch zu diesem Thema" und ermöglichte es Mathematikern, Chemikern, Elektroingenieuren und Sozialwissenschaftlern, miteinander zu sprechen. Harary spendete die gesamten Tantiemen zur Finanzierung des Pólya-Preises. ⓘ

Eines der berühmtesten und anregendsten Probleme der Graphentheorie ist das Vier-Farben-Problem: "Ist es wahr, dass jede in der Ebene gezeichnete Karte ihre Regionen mit vier Farben färben kann, und zwar so, dass zwei Regionen, die eine gemeinsame Grenze haben, unterschiedliche Farben haben?" Dieses Problem wurde erstmals 1852 von Francis Guthrie aufgeworfen, und die erste schriftliche Erwähnung findet sich in einem Brief von De Morgan an Hamilton aus demselben Jahr. Es wurden viele falsche Beweise vorgeschlagen, darunter die von Cayley, Kempe und anderen. Die Untersuchung und Verallgemeinerung dieses Problems durch Tait, Heawood, Ramsey und Hadwiger führte zur Untersuchung der Färbungen von Graphen, die in Flächen mit beliebigem Genus eingebettet sind. Taits Reformulierung führte zu einer neuen Klasse von Problemen, den Faktorisierungsproblemen, die insbesondere von Petersen und Kőnig untersucht wurden. Die Arbeiten von Ramsey über Färbungen und insbesondere die von Turán 1941 erzielten Ergebnisse waren der Ursprung eines anderen Zweigs der Graphentheorie, der Theorie der extremen Graphen. ⓘ

Das Vier-Farben-Problem blieb mehr als ein Jahrhundert lang ungelöst. Im Jahr 1969 veröffentlichte Heinrich Heesch eine Methode zur Lösung des Problems mit Hilfe von Computern. Ein 1976 von Kenneth Appel und Wolfgang Haken erstellter computergestützter Beweis macht grundlegend Gebrauch von dem von Heesch entwickelten Begriff des "Entladens". Der Beweis beinhaltete die Überprüfung der Eigenschaften von 1.936 Konfigurationen per Computer und wurde damals aufgrund seiner Komplexität nicht vollständig akzeptiert. Ein einfacherer Beweis, der nur 633 Konfigurationen berücksichtigt, wurde zwanzig Jahre später von Robertson, Seymour, Sanders und Thomas erbracht. ⓘ

Die eigenständige Entwicklung der Topologie zwischen 1860 und 1930 befruchtete die Graphentheorie durch die Arbeiten von Jordan, Kuratowski und Whitney. Ein weiterer wichtiger Faktor für die gemeinsame Entwicklung von Graphentheorie und Topologie war die Verwendung der Techniken der modernen Algebra. Das erste Beispiel für eine solche Anwendung stammt aus der Arbeit des Physikers Gustav Kirchhoff, der 1845 seine Kirchhoffschen Schaltungsgesetze zur Berechnung von Spannung und Strom in elektrischen Schaltungen veröffentlichte. ⓘ

Die Einführung probabilistischer Methoden in die Graphentheorie, insbesondere in der Studie von Erdős und Rényi über die asymptotische Wahrscheinlichkeit der Konnektivität von Graphen, führte zu einem weiteren Zweig, der als Zufallsgraphentheorie bekannt ist und eine fruchtbare Quelle für graphentheoretische Ergebnisse darstellt. ⓘ

… 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. ⓘ

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. ⓘ

Darstellung

Ein Graph ist eine Abstraktion von Beziehungen, die in der Natur vorkommen; daher kann er nicht an eine bestimmte Darstellung gekoppelt werden. Wie er dargestellt wird, hängt davon ab, inwieweit eine solche Darstellung für eine bestimmte Anwendung geeignet ist. Die gebräuchlichsten Darstellungsformen sind die visuelle, bei der in der Regel die Eckpunkte gezeichnet und durch Kanten verbunden werden, und die tabellarische, bei der die Zeilen einer Tabelle Informationen über die Beziehungen zwischen den Eckpunkten innerhalb des Graphen liefern. ⓘ

Visuell: Diagrammzeichnung

Graphen werden in der Regel visuell dargestellt, indem für jeden Scheitelpunkt ein Punkt oder ein Kreis gezeichnet wird und eine Linie zwischen zwei Scheitelpunkten gezogen wird, wenn diese durch eine Kante verbunden sind. Bei gerichteten Graphen wird die Richtung durch einen Pfeil angegeben. Wenn der Graph gewichtet ist, wird die Gewichtung auf dem Pfeil hinzugefügt. ⓘ

Eine Graphenzeichnung sollte nicht mit dem Graphen selbst (der abstrakten, nicht visuellen Struktur) verwechselt werden, da es mehrere Möglichkeiten gibt, die Graphenzeichnung zu strukturieren. Es kommt nur darauf an, welche Eckpunkte mit wie vielen Kanten mit welchen anderen verbunden sind, und nicht auf die genaue Anordnung. In der Praxis ist es oft schwierig zu entscheiden, ob zwei Zeichnungen denselben Graphen darstellen. Je nach Problembereich sind manche Layouts besser geeignet und leichter zu verstehen als andere. ⓘ

Die Pionierarbeit von W. T. Tutte war sehr einflussreich auf dem Gebiet des Zeichnens von Graphen. Neben anderen Errungenschaften führte er die Verwendung linearer algebraischer Methoden ein, um Graphen zu zeichnen. ⓘ

Das Zeichnen von Graphen kann auch Probleme umfassen, die sich mit der Kreuzungszahl und ihren verschiedenen Verallgemeinerungen befassen. Die Kreuzungszahl eines Graphen ist die Mindestanzahl von Schnittpunkten zwischen Kanten, die eine Zeichnung des Graphen in der Ebene enthalten muss. Für einen ebenen Graphen ist die Kreuzungszahl per Definition gleich Null. Es werden auch Zeichnungen auf anderen Flächen als der Ebene untersucht. ⓘ

Es gibt weitere Techniken zur Visualisierung eines Graphen abseits von Knoten und Kanten, darunter Kreispackungen, Schnittpunktgraphen und andere Visualisierungen der Adjazenzmatrix. ⓘ

Tabellarisch: Graphische Datenstrukturen

Die tabellarische Darstellung eignet sich gut für rechnerische Anwendungen. Es gibt verschiedene Möglichkeiten, Graphen in einem Computersystem zu speichern. Welche Datenstruktur verwendet wird, hängt sowohl von der Struktur des Graphen als auch von dem Algorithmus ab, mit dem der Graph bearbeitet wird. Theoretisch kann man zwischen Listen- und Matrixstrukturen unterscheiden, aber in konkreten Anwendungen ist die beste Struktur oft eine Kombination aus beiden. Listenstrukturen werden oft für spärliche Graphen bevorzugt, da sie weniger Speicherplatz benötigen. Matrixstrukturen hingegen bieten für einige Anwendungen einen schnelleren Zugriff, können aber große Mengen an Speicher verbrauchen. Die Implementierung von spärlichen Matrixstrukturen, die auf modernen parallelen Computerarchitekturen effizient sind, ist Gegenstand aktueller Untersuchungen. ⓘ

Zu den Listenstrukturen gehören die Kantenliste, ein Array von Knotenpaaren, und die Adjazenzliste, in der die Nachbarn jedes Knotens separat aufgeführt sind: Ähnlich wie die Kantenliste enthält jeder Knoten eine Liste der Knoten, an die er angrenzt. ⓘ

Zu den Matrixstrukturen gehören die Inzidenzmatrix, eine Matrix aus 0en und 1en, deren Zeilen Eckpunkte und deren Spalten Kanten darstellen, und die Adjazenzmatrix, bei der sowohl die Zeilen als auch die Spalten durch Eckpunkte indiziert sind. In beiden Fällen steht eine 1 für zwei benachbarte Objekte und eine 0 für zwei nicht benachbarte Objekte. Die Gradmatrix gibt den Grad der Scheitelpunkte an. Die Laplacian-Matrix ist eine modifizierte Form der Adjazenzmatrix, die Informationen über den Grad der Knoten enthält und für einige Berechnungen nützlich ist, z. B. für das Kirchhoff'sche Theorem über die Anzahl der überspannenden Bäume eines Graphen. Die Abstandsmatrix ist wie die Adjazenzmatrix sowohl in den Zeilen als auch in den Spalten durch die Knotenpunkte indiziert, enthält jedoch nicht in jeder Zelle eine 0 oder eine 1, sondern die Länge des kürzesten Weges zwischen zwei Knotenpunkten. ⓘ

Probleme

Aufzählung

Es gibt eine umfangreiche Literatur über grafische Aufzählung: das Problem, Graphen zu zählen, die bestimmte Bedingungen erfüllen. Ein Teil dieser Arbeit findet sich in Harary und Palmer (1973). ⓘ

Untergraphen, induzierte Untergraphen und Minoren

Ein häufiges Problem, das so genannte Untergraphen-Isomorphismus-Problem, besteht darin, einen festen Graphen als Untergraphen in einem gegebenen Graphen zu finden. Ein Grund für das Interesse an dieser Frage ist, dass viele Grapheneigenschaften für Untergraphen erblich sind, was bedeutet, dass ein Graph die Eigenschaft nur dann hat, wenn alle Untergraphen sie auch haben. Leider ist die Suche nach maximalen Teilgraphen einer bestimmten Art oft ein NP-komplettes Problem. Ein Beispiel:

• Die Suche nach dem größten vollständigen Teilgraphen wird als Cliquenproblem bezeichnet (NP-komplett). ⓘ

Ein Spezialfall der Untergraphenisomorphie ist das Graphenisomorphieproblem. Es fragt, ob zwei Graphen isomorph sind. Es ist weder bekannt, ob dieses Problem NP-komplett ist, noch ob es in polynomieller Zeit gelöst werden kann. ⓘ

Ein ähnliches Problem ist die Suche nach induzierten Untergraphen in einem gegebenen Graphen. Auch hier sind einige wichtige Grapheigenschaften in Bezug auf induzierte Teilgraphen erblich, d. h. ein Graph hat eine Eigenschaft nur dann, wenn alle induzierten Teilgraphen sie ebenfalls haben. Die Suche nach maximalen induzierten Teilgraphen einer bestimmten Art ist ebenfalls oft NP-komplett. Ein Beispiel:

• Die Suche nach dem größten kantenlosen induzierten Teilgraphen oder der größten unabhängigen Menge wird als unabhängiges Mengenproblem bezeichnet (NP-komplett). ⓘ

Ein weiteres solches Problem, das Minor-Containment-Problem, besteht darin, einen festen Graphen als Minor eines gegebenen Graphen zu finden. Ein Minor oder Subkontrakt eines Graphen ist ein beliebiger Graph, den man erhält, indem man einen Subgraphen nimmt und einige (oder keine) Kanten kontrahiert. Viele Eigenschaften von Graphen sind für Minoren erblich, was bedeutet, dass ein Graph eine Eigenschaft nur dann hat, wenn alle Minoren sie ebenfalls haben. Das Wagnersche Theorem besagt beispielsweise:

• Ein Graph ist planar, wenn er als Minor weder den vollständigen zweiseitigen Graphen K_3,3 (siehe das Drei-Häuser-Problem) noch den vollständigen Graphen K₅ enthält. ⓘ

Ein ähnliches Problem, das Subdivision-Containment-Problem, besteht darin, einen festen Graphen als Subdivision eines gegebenen Graphen zu finden. Eine Unterteilung oder ein Homöomorphismus eines Graphen ist jeder Graph, den man durch Unterteilung einiger (oder keiner) Kanten erhält. Die Eingrenzung von Unterteilungen hängt mit Grapheneigenschaften wie der Planarität zusammen. Das Kuratowski-Theorem besagt zum Beispiel:

• Ein Graph ist planar, wenn er als Unterteilung weder den vollständigen zweistufigen Graphen K_3,3 noch den vollständigen Graphen K₅ enthält. ⓘ

Ein weiteres Problem bei der Unterteilungseinschränkung ist die Kelmans-Seymour-Vermutung:

• Jeder 5-vertex-verbundene Graph, der nicht planar ist, enthält eine Unterteilung des vollständigen 5-Vertex-Graphen K₅.

Eine andere Klasse von Problemen hat mit dem Ausmaß zu tun, in dem verschiedene Arten und Verallgemeinerungen von Graphen durch ihre punktentfernten Untergraphen bestimmt werden. Ein Beispiel:

• Die Rekonstruktionsvermutung ⓘ

Zusammenhangskomponenten ⓘ

• zusammenhängend (im Allgemeinen k-zusammenhängend),
• bipartit (im Allgemeinen k-partit),
• planar,
• eulersch oder hamiltonisch sein. ⓘ

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. ⓘ

Graphenfärbung

Viele Probleme und Theoreme in der Graphentheorie haben mit verschiedenen Arten der Färbung von Graphen zu tun. Normalerweise ist man daran interessiert, einen Graphen so zu färben, dass keine zwei benachbarten Knoten die gleiche Farbe haben, oder mit anderen ähnlichen Einschränkungen. Man kann auch die Färbung von Kanten in Betracht ziehen (möglicherweise so, dass keine zwei zusammenfallenden Kanten die gleiche Farbe haben), oder andere Varianten. Zu den berühmten Ergebnissen und Vermutungen in Bezug auf die Färbung von Graphen gehören die folgenden:

• Vier-Farben-Theorem
• Theorem des starken perfekten Graphen
• Erdős-Faber-Lovász-Vermutung (ungelöst)
• Total coloring conjecture, auch Behzad's conjecture genannt (ungelöst)
• Listenfärbungs-Vermutung (ungelöst)
• Hadwiger-Vermutung (Graphentheorie) (ungelöst) ⓘ

Subsumtion und Vereinheitlichung

Theorien zur Modellierung von Beschränkungen betreffen Familien von gerichteten Graphen, die durch eine partielle Ordnung miteinander verbunden sind. In diesen Anwendungen sind die Graphen nach ihrer Spezifität geordnet, was bedeutet, dass Graphen mit mehr Einschränkungen - die spezifischer sind und daher eine größere Menge an Informationen enthalten - von Graphen mit allgemeineren Beschränkungen untergeordnet werden. Zu den Operationen zwischen Graphen gehören die Auswertung der Richtung einer Subsumtionsbeziehung zwischen zwei Graphen, falls vorhanden, und die Berechnung der Graphvereinigung. Die Vereinheitlichung zweier Argumentationsgraphen ist definiert als der allgemeinste Graph (oder die Berechnung desselben), der mit den Eingaben konsistent ist (d.h. alle Informationen enthält), sofern ein solcher Graph existiert; effiziente Vereinigungsalgorithmen sind bekannt. ⓘ

Für strikt kompositionale Bedingungsrahmen ist die Graphvereinheitlichung die hinreichende Erfüllbarkeits- und Kombinationsfunktion. Zu den bekannten Anwendungen gehören das automatische Beweisen von Theoremen und die Modellierung der Ausarbeitung von linguistischen Strukturen. ⓘ

Weg-Probleme

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 P ≠ NP (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. ⓘ

Netzwerkfluss

Es gibt zahlreiche Probleme, die sich vor allem aus Anwendungen ergeben, die mit verschiedenen Begriffen von Flüssen in Netzwerken zu tun haben, zum Beispiel:

• Max-Flow-Min-Cut-Theorem ⓘ

Sichtbarkeitsprobleme

• Museumswächter-Problem ⓘ

Überdeckungsprobleme

Überdeckungsprobleme in Graphen können sich auf verschiedene Mengenüberdeckungsprobleme auf Teilmengen von Knoten/Teilgraphen beziehen.

• Das Problem der dominierenden Menge ist ein Spezialfall des Problems der Mengenüberdeckung, bei dem die Mengen die geschlossenen Nachbarschaften sind.
• Das Vertex-Cover-Problem ist ein Spezialfall des Set-Cover-Problems, bei dem die zu deckenden Mengen alle Kanten sind.
• Das ursprüngliche Mengenüberdeckungsproblem, auch Treffermenge genannt, kann als Knotenüberdeckung in einem Hypergraphen beschrieben werden. ⓘ

Dekompositionsprobleme

Das Problem der Dekomposition, definiert als Partitionierung der Kantenmenge eines Graphen (mit so vielen Eckpunkten wie nötig, die die Kanten jedes Teils der Partition begleiten), hat eine Vielzahl von Fragestellungen. Häufig besteht das Problem darin, einen Graphen in Untergraphen zu zerlegen, die zu einem festen Graphen isomorph sind, z. B. die Zerlegung eines vollständigen Graphen in Hamiltonsche Zyklen. Andere Probleme spezifizieren eine Familie von Graphen, in die ein gegebener Graph zerlegt werden soll, z. B. eine Familie von Zyklen oder die Zerlegung eines vollständigen Graphen Kn in n - 1 spezifizierte Bäume mit jeweils 1, 2, 3, ..., n - 1 Kanten. ⓘ

Einige spezifische Zerlegungsprobleme, die untersucht wurden, sind:

• Arborizität, eine Zerlegung in so wenige Wälder wie möglich
• Zyklus-Doppeldeckung, eine Zerlegung in eine Sammlung von Zyklen, die jede Kante genau zweimal bedecken
• Kantenfärbung, eine Zerlegung in so wenige Übereinstimmungen wie möglich
• Graphenfaktorisierung, eine Zerlegung eines regulären Graphen in reguläre Untergraphen mit bestimmten Graden ⓘ

Graphenklassen

Bei vielen Problemen geht es darum, die Mitglieder verschiedener Klassen von Graphen zu charakterisieren. Einige Beispiele für solche Fragen sind unten aufgeführt:

• Aufzählung der Mitglieder einer Klasse
• Charakterisierung einer Klasse in Bezug auf verbotene Unterstrukturen
• Feststellung von Beziehungen zwischen Klassen (z. B. impliziert eine Eigenschaft von Graphen eine andere)
• Suche nach effizienten Algorithmen zur Entscheidung über die Zugehörigkeit zu einer Klasse
• Finden von Repräsentationen für Mitglieder einer Klasse ⓘ

Zusammenhang

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 ⓘ

Cliquenproblem

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

Knotenüberdeckung

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 Netzwerken

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

Matching im bipartiten Graphen ⓘ

Matching

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 Graphenprobleme

Zu den weiteren Graphenproblemen zählen

• das Finden einer stabilen Menge,
• das Graphzeichnen (hierfür existiert Software zur Visualisierung von Graphen: yEd, Graphviz) und
• die Transformation von Graphen anhand von regelbasierten Graphersetzungssystemen. Graphersetzungssysteme, die dem Aufzählen aller Graphen einer Graphsprache dienen, werden auch Graphgrammatik genannt ⓘ