Ein Graph ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert. Die mathematischen Abstraktionen der Objekte werden dabei Knoten (auch Ecken) des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen Kanten (manchmal auch Bögen). Die Kanten können gerichtet oder ungerichtet sein. Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.
mini|Plan der Wiener U-Bahn
In einem U-Bahn-Netz stellt jeder Knoten eine U-Bahn-Station dar und jede Kante eine direkte Zugverbindung zwischen zwei Stationen. Die chemische Graphentheorie betrachtet Moleküle als Graphen, mit Atomen als Knoten und Molekularverbindungen als Kanten. Komplexe räumliche Gebilde wie Polyeder können als Graphen dargestellt werden (Schlegeldiagramm). Das Internet ist ein riesiger Graph aus Computern und Datenverbindungen.
Bäume wie etwa Stammbäume sind ein Sonderfall der Graphen und enthalten keine Zyklen.
Die mathematische Betrachtung von Graphen begann im 18. Jahrhundert mit dem Königsberger Brückenproblem.
Typen von Graphen
Ungerichteter Graph In ungerichteten Graphen werden die Verbindungen zwischen Knoten durch Kanten gekennzeichnet. Die Kanten haben keine Richtung. Jede Kante kann in beide Richtungen durchlaufen werden.
Gerichteter Graph (Digraph)
In Digraphen (von englisch directed graph, auch gerichtete Graphen genannt) werden Kanten statt durch Linien durch Pfeile gekennzeichnet, wobei der Pfeil von ihrem Anfangs- zu ihrem Endknoten zeigt. Dies verdeutlicht, dass jede Kante des Graphen nur in eine Richtung durchlaufen werden kann. Ein Spezialfall davon sind orientierte Graphen, in denen es keine ungerichteten Kanten gibt, d. h. gibt es eine Kante von Knoten A nach B, dann gibt es nie auch die umgekehrte Kante von B nach A.
Baum
Ein Baum ist in der Graphentheorie ein spezieller Typ von Graph, der zusammenhängend ist und keine geschlossenen Pfade, also Zyklen der Länge größer oder gleich 3, enthält. Bei allen Bäumen ist die Anzahl der Knoten offensichtlich um 1 größer als die Anzahl der Kanten.
Bäume haben sehr viele praktische Anwendungen, vor allem in der Informatik. Viele Algorithmen werden mithilfe von Bäumen programmiert. Zum Beispiel können Netzwerke, Verkehrsnetze oder Versorgungsnetze mit einer Breitensuche oder einer Tiefensuche effektiv durchlaufen werden. Im Bereich der künstlichen Intelligenz und der Strategiespiele ist die Alpha-Beta-Suche wichtig. Sie basiert auf Suchbäumen.
Multigraph mini|Multigraph: Mehrfachkanten werden durch eine gewichtete Kante visualisiert. Anstatt viele Kanten zu zeichnen, wird nur eine Kante gezeichnet und das Kantengewicht zeigt die Zahl der Kanten an.
In Multigraphen können zwei Knoten durch mehrere Kantenbei gerichteten Graphen: in derselben Richtung verbunden sein, was in einfachen Graphen nicht erlaubt ist. Außerdem dürfen Multigraphen Schleifen enthalten: Kanten, die zum selben Knoten führen, von dem sie ausgehen.
Planarer Graph
Ein planarer Graph ist ein Graph, der auf einer Ebene, mit Punkten für die Knoten und Linien für die Kanten, dargestellt werden kann, sodass sich keine Kanten schneiden. Jeder planare Graph hat einen dualen Graphen. Das ist ein Graph, wo jeder Fläche des Graphen ein Knoten zugeordnet ist, der innerhalb dieser Fläche liegt, und umgekehrt. Die Dualität von planaren Graphen ist immer gegenseitig, das heißt, der duale Graph des dualen Graphen jedes planaren Graphen ist der ursprüngliche planare Graph.
Für planare Graphen gilt der Eulersche Polyedersatz, der oft mit der Gleichung dargestellt wird.
Hypergraph Bei Hypergraphen verbindet eine Kante (auch Hyperkante genannt) nicht nur zwei, sondern mehrere Knoten gleichzeitig. Hypergraphen können beispielsweise durch mehrere planare Graphen mit Indizierung der Kanten dargestellt werden. Hypergraphen mit wenigen Kanten (sogenannte dünne Graphen) zeichnet man so, dass man eine Menge von Punkten zeichnet, die den Knoten entsprechen, und die zu einer Hyperkante gehörigen Punkte werden dann durch eine geschlossene Linie umkreist, die somit die Teilmenge der zu ihr gehörenden Knoten innerhalb aller Knoten angibt. Bei Hypergraphen mit vielen Kanten wird diese Darstellung aber schnell unübersichtlich. Weniger intuitiv, aber übersichtlicher ist es dann, einen Hypergraphen als bipartiten Meta-Graphen darzustellen, wobei die eine der beiden Bipartitionsmengen den Knoten des Hypergraphen, die andere Bipartitionsmenge den Hyperkanten des Hypergraphen entspricht. Die Kanten zwischen diesen beiden Bipartitionsmengen symbolisieren dann die Zugehörigkeit der Knoten zu den Hyperkanten.
Das Physik-Projekt von Stephen Wolfram (siehe auch: Wolfram Research und Mathematica) zur Erklärung der Grundlagen der Physik basiert unter anderem auf dem Raum der Regeln über Hypergraphen: „Und zumindest in einer gewissen Annäherung können wir dann sagen, dass Energie mit der Aktivität im Hypergraphen, die Information durch die Zeit fortpflanzt, assoziiert ist, während Impuls mit Aktivität assoziiert ist, die Information im Raum fortpflanzt.“Stephen Wolfram: Finally We May Have a Path to the Fundamental Theory of Physics… and It’s Beautiful abgerufen am 20. Januar 2024.
Definitionen Ein Graph ist ein geordnetes Paar , wobei eine Menge von Knoten (, oft auch Ecken genannt) und eine Menge von Kanten (, manchmal auch Bögen genannt) bezeichnet. Dabei ist in
ungerichteten Graphen ohne Mehrfachkanten eine Teilmenge aller 2-elementigen Teilmengen von , gerichteten Graphen ohne Mehrfachkanten eine Teilmenge des kartesischen Produkts , ungerichteten Graphen mit zusammengefassten Mehrfachkanten eine Multimenge über der Menge aller 2-elementigen Teilmengen von , also eine Funktion , gerichteten Graphen mit zusammengefassten Mehrfachkanten eine Multimenge über dem kartesischen Produkt , also eine Funktion , gerichteten Graphen mit eigenständigen Mehrfachkanten eine beliebige Menge, deren Elemente mit Hilfe von zwei Funktionen , die den Elementen einen Quell- bzw. Zielknoten zuordnen, als Kanten angesehen werden (so ein Graph ist dasselbe wie ein Funktor , wobei die recht überschaubare Kategorie mit zwei Objekten und zwei ausgezeichneten Pfeilen ist) Hypergraphen eine Teilmenge der Potenzmenge von .
gerahmt|Ungerichteter Graph ohne Mehrfachkanten gerahmt|Gerichteter Graph ohne Mehrfachkanten gerahmt|Ungerichteter Graph mit Mehrfachkanten gerahmt|Gerichteter Graph mitMehrfachkanten
Den Zusatz „ohne Mehrfachkanten“ lässt man gewöhnlich weg und nennt Graphen mit Mehrfachkanten Multigraphen. Ferner verzichtet man meist auf das Attribut „ungerichtet“ und kennzeichnet nur gerichtete Graphen explizit. Ungerichtete Graphen ohne Mehrfachkanten nennt man auch häufig schlicht oder einfach. Eine andere Bezeichnung für gerichtete Graphen ist Digraph (Directed Graph).
Abgeleitete Bezeichnungen Statt die Knoten- und Kantenmenge eines Graphen mit den Symbolen und zu identifizieren, kann man auch allgemeine Abbildungen und definieren, die einen Graphen auf dessen Knotenmenge oder Kantenmenge abbilden. Für zwei Graphen und bezeichnen also und sowie und .
Die Mehrdeutigkeit und wird bei dieser Notation in Kauf genommen, obwohl die Abbildungen etwas anderes darstellen als die mit ihr verbundene Knoten- und Kantenmenge. Als Konvention bietet sich an, mit bzw. ohne Argument Knoten- bzw. Kantenmenge zu bezeichnen, bzw. mit Argument bezeichnen dagegen die definierten Abbildungen.
Ist ein Graph, so sagt man allgemein ist Knoten bzw. Ecke von , wenn zu gehört. Außerdem bezeichnet man Kanten als ungerichtete Kante von , falls ein ungerichteter Graph ist. gerichtete Kante von , falls ein gerichteter Graph ist. Hyperkante von , falls ein Hypergraph ist.
In einer ungerichteten Kante bezeichnet man und als Endknoten von . In einer gerichteten Kante bezeichnet man als Startknoten und als Endknoten von .
Bei Multigraphen bezeichnet die Vielfachheit von . Wenn gilt, so spricht man von einer Multi- oder Mehrfachkante.
Hat eine Kante in gerichteten Graphen die Form , so spricht man von einer Schleife. Ist die Schleife in einem Multigraphen zugleich eine Mehrfachkante, so spricht man von einer Mehrfachschleife. Gerichtete Graphen ohne Schleifen nennt man schleifenlos oder schleifenfrei.
Als Knotenzahl eines Graphen bezeichnet man die Anzahl seiner Knoten, als Kantenzahl bezeichnet man die Anzahl seiner Kanten (in Multigraphen summiert man über die Vielfachheit der Kanten).
Zwei Knoten heißen benachbart, wenn eine Kante sie verbindet.
Spezialfälle Verbindet in einem gerichteten Graphen die Kante zwei Knoten, und die Kante dieselben Knoten in umgekehrter Richtung, kann man beide zusammen auch als eine ungerichtete Kante innerhalb des gerichteten Graphen betrachten. Im Falle von Mehrfachkanten müssen die Vielfachheiten beider Kanten übereinstimmen.
Gibt es zu jeder Kante eines gerichteten Graphen eine solche entgegengesetzte Kante im Graphen, so ist er ein symmetrischer Graph.
Einen Graphen, dessen Knotenmenge endlich ist, nennt man einen endlichen Graphen. Im Gegensatz dazu nennt man einen Graphen, dessen Knotenmenge unendlich ist, unendlichen Graphen. Meist betrachtet man nur endliche Graphen und lässt daher das Attribut „endlich“ weg, während man unendliche Graphen explizit kennzeichnet.
Teilgraphen, Wege und Zyklen mini|Ein gerichteter Graph mit Zyklus mini|Ein gerichteter Graph ohne Zyklus
Ein Teilgraph eines Graphen enthält nur Knoten und Kanten, die auch in enthalten sind. Ein von einer Knotenmenge U induzierter Teilgraph enthält die Knoten aus U und alle Kanten aus G zwischen diesen Knoten.
Eine Folge von paarweise verschiedenen Knoten , in der aufeinander folgende Knoten und im Graphen durch eine Kante verbunden sind, bezeichnet man als Weg, manchmal auch als Pfad. Gilt , und ist dies der einzige doppelte Knoten, spricht man von einem Zyklus oder Kreis. Eine Sequenz von benachbarten Knoten, in der sich Knoten wiederholen dürfen, bezeichnet man als Kantenfolge. Die Begriffe Weg, Pfad, Kantenfolge, Kreis und Zyklus werden in der Literatur zum Teil unterschiedlich definiert.
Enthält ein gerichteter Graph keinen Zyklus, nennt man ihn azyklisch oder zyklenfrei – also einen gerichteten azyklischen Graphen (). Ein solcher Graph lässt sich durch die Ergänzung aller Kanten, die gleichen Ausgangs- und Endknoten wie Wege haben, also die Umwege über andere Kanten zu einem Zielknoten abkürzen, zu einer (endlichen und diskreten) Halbordnung erweitern. Diesen Vorgang nennt man die Bildung der transitiven Hülle. Ein Hasse-Diagramm ist ein gerichteter azyklischer Graph, bei dem die durch das Transitivitätsgesetz implizierten Kanten weggelassen sind (transitive Reduktion).
Grundlegende Operationen Bei der Untersuchung von Grapheneigenschaften kommt es häufiger vor, dass man auf Graphen einfache Operationen anwenden muss, um möglichst kompakt und damit leichter verständlich schreiben zu können. Besonders häufig werden die üblichen Operationen der Mengenlehre (Vereinigung, Durchschnitt, Differenz und Komplement) auf Knoten- bzw. Kantenmengen von Graphen angewendet, sodass diese direkt auf Graphen definiert werden.
Sind und Graphen desselben Typs, so bezeichnet den Graphen, der entsteht, wenn man die Knoten- und Kantenmenge vereinigt, den Graphen, der entsteht, wenn man von der Kantenmenge von abzieht und den Graphen, der entsteht, wenn man von der Knotenmenge von abzieht und alle Kanten entfernt, die Knoten aus enthalten.
Man beachte dabei die unterschiedliche Definition der Begriffe Vereinigungsmenge und Differenzmenge für Mengen und Multimengen. Man schreibt auch abkürzend , falls Teilmenge von ist, , falls leer oder Teilmenge von ist, , falls , , falls , , falls und falls .
Kantenkontraktion und die Bildung des Komplementgraphen sind weitere Basisoperationen.
Bemerkungen