Quelltext der Seite Graph (Graphentheorie)

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 (Graphentheorie)|Knoten]]'' (auch ''Ecken'') des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen ''[[Kante (Graphentheorie)|Kanten]]'' (manchmal auch ''Bögen''). Die Kanten können [[Kante (Graphentheorie)#Kantenarten und ihre Notation|gerichtet]] oder [[Kante (Graphentheorie)#Kantenarten und ihre Notation|ungerichtet]] sein. Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.<ref name="Diestel2010">{{Literatur |Autor=[[Reinhard Diestel]] |Titel=Graphentheorie |Auflage=4. |Verlag=Springer |Ort=Berlin u.&nbsp;a. |Datum=2010 |ISBN=978-3-642-14911-5 |Seiten=1–34 |JahrEA=1996 |Online=[https://diestel-graph-theory.com/basic.html online: 4th elektronische Ausgabe 2010]}}</ref>

[[Datei:U-Bahn-Netz Wien 2019.png|mini|Plan der [[U-Bahn Wien|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ül]]e als Graphen, mit Atomen als Knoten und [[Molekularverbindung]]en als Kanten. Komplexe räumliche Gebilde wie [[Polyeder]] können als Graphen dargestellt werden ([[Schlegeldiagramm]]). Das [[Internet]] ist ein riesiger Graph aus [[Computer]]n und [[Datenverbindung]]en.

[[Baum (Graphentheorie)|Bäume]] wie etwa [[Stammbaum|Stammbäume]] sind ein Sonderfall der Graphen und enthalten keine [[Zyklus (Graphentheorie)|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 (Graphentheorie)|Knoten]] durch [[Kante (Graphentheorie)|Kanten]] gekennzeichnet. Die Kanten haben keine Richtung. Jede Kante kann in beide Richtungen durchlaufen werden.

=== Gerichteter Graph (Digraph) ===
{{Hauptartikel|Gerichteter Graph}}
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.<ref>{{Literatur |Hrsg=Claude Sammut, Geoffrey I. Webb |Titel=Directed Graphs |Sammelwerk=Encyclopedia of Machine Learning |Verlag=Springer US |Datum=2010 |Seiten=279 |DOI=10.1007/978-0-387-30164-8_218}}</ref> Ein Spezialfall davon sind ''orientierte Graphen'', in denen es keine ungerichteten Kanten gibt, d.&nbsp;h. gibt es eine Kante von Knoten A nach B, dann gibt es nie auch die umgekehrte Kante von B nach A.

=== Baum ===
{{Hauptartikel|Baum (Graphentheorie)}}
Ein [[Baum (Graphentheorie)|''Baum'']] ist in der [[Graphentheorie]] ein spezieller Typ von Graph, der zusammenhängend ist und keine geschlossenen [[Weg (Graphentheorie)|Pfade]], also [[Zyklus (Graphentheorie)|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 [[Algorithmus|Algorithmen]] werden mithilfe von Bäumen [[Programmierung|programmiert]]. Zum Beispiel können [[Netzwerk]]e, [[Verkehrsnetz]]e oder [[Versorgungsnetz]]e mit einer [[Breitensuche]] oder einer [[Tiefensuche]] effektiv durchlaufen werden. Im Bereich der [[Künstliche Intelligenz|künstlichen Intelligenz]] und der [[Strategiespiel]]e ist die [[Alpha-Beta-Suche]] wichtig. Sie basiert auf [[Suchbaum|Suchbäumen]].

=== Multigraph ===
[[Datei:CPT-Graphs-directed-weighted-ex1.svg|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.]]
{{Hauptartikel|Multigraph}}
In ''Multigraphen'' können zwei Knoten durch mehrere Kanten<ref name="MultDirected">bei gerichteten Graphen: in derselben Richtung</ref> verbunden sein, was in [[Einfacher Graph|einfachen Graphen]] nicht erlaubt ist. Außerdem dürfen Multigraphen Schleifen enthalten: Kanten, die zum selben Knoten führen, von dem sie ausgehen.<ref name="Diestel2010" />

=== Planarer Graph ===
{{Hauptartikel|Planarer Graph}}
Ein ''[[planarer Graph]]'' ist ein Graph, der auf einer Ebene, mit Punkten für die [[Knoten (Graphentheorie)|Knoten]] und Linien für die [[Kante (Graphentheorie)|Kanten]], dargestellt werden kann, sodass sich keine Kanten schneiden. Jeder planare Graph hat einen [[Dualität (Mathematik)#Geometrisch dualer Graph|dualen Graphen]]. Das ist ein Graph, wo jeder Fläche des Graphen ein [[Knoten (Graphentheorie)|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 [[Eulerscher Polyedersatz|Eulersche Polyedersatz]], der oft mit der [[Gleichung]] <math>E - K + F = 2</math> dargestellt wird.

=== Hypergraph ===
Bei ''Hypergraphen'' verbindet eine Kante (auch ''Hyperkante'' genannt) nicht nur zwei, sondern mehrere Knoten gleichzeitig. Hypergraphen können beispielsweise durch mehrere [[Planarer Graph|planare Graphen]] mit [[Index (Mathematik)|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 [[bipartit]]en 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.“<ref>Stephen Wolfram: [https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/?dateline=no ''Finally We May Have a Path to the Fundamental Theory of Physics… and It’s Beautiful''] abgerufen am 20. Januar 2024.</ref>

== Definitionen ==
Ein Graph <math>G</math> ist ein [[geordnetes Paar]] <math>(V, E)</math>, wobei <math>V</math> eine [[Mengenlehre|Menge]] von ''Knoten'' ({{enS|vertex/vertices}}, oft auch ''Ecken'' genannt) und <math>E</math> eine Menge von ''Kanten'' ({{enS|edge/edges}}, manchmal auch ''Bögen'' genannt) bezeichnet. Dabei ist <math>E</math> in

* ''ungerichteten Graphen ohne Mehrfachkanten'' eine [[Teilmenge]] aller 2-elementigen Teilmengen von <math>V</math><ref name="Diestel2010" />,
* ''[[Gerichteter Graph|gerichteten Graphen]] ohne Mehrfachkanten'' eine Teilmenge des [[Kartesisches Produkt|kartesischen Produkts]] <math>V \times V</math>,<ref>{{Literatur |Autor=Brigitte Werners |Titel=Grundlagen des Operations Research |Auflage=3 |Verlag=Springer |Ort=Berlin Heidelberg |Datum=2013 |ISBN=978-3-642-40101-5 |Seiten=175–209}}</ref>
* ''ungerichteten Graphen mit zusammengefassten Mehrfachkanten'' eine [[Multimenge]] über der Menge <math>W</math> aller 2-elementigen Teilmengen von <math>V</math>, also eine [[Funktion (Mathematik)|Funktion]] <math>E\colon W \to \N_0</math>,
* ''gerichteten Graphen mit zusammengefassten Mehrfachkanten'' eine Multimenge über dem kartesischen Produkt <math>V \times V</math>, also eine Funktion <math>E\colon V \times V \to \N_0</math>,
* ''gerichteten Graphen mit eigenständigen Mehrfachkanten'' eine beliebige Menge, deren Elemente mit Hilfe von zwei Funktionen <math>\mathrm{src},\mathrm{tgt} \colon E \to V</math>, die den Elementen einen Quell- bzw. Zielknoten zuordnen, als Kanten angesehen werden (so ein Graph ist dasselbe wie ein [[Funktor (Mathematik)|Funktor]] <math>G\colon \mathcal G \to \mathbf{Set}</math>, wobei <math>\mathcal G</math> die recht überschaubare Kategorie <math>\mathcal G = \{V \stackrel {\mathrm{src}} \longleftarrow E \stackrel {\mathrm{tgt}} \longrightarrow V\}</math> mit zwei Objekten und zwei ausgezeichneten Pfeilen ist)
* ''Hypergraphen'' eine Teilmenge der [[Potenzmenge]] von <math>V</math>.<ref name="Diestel2010" />

{|
| [[Datei:Graph ungerichtet.svg|gerahmt|Ungerichteter Graph ohne Mehrfachkanten]]
| [[Datei:Graph gerichtet.svg|gerahmt|Gerichteter Graph ohne Mehrfachkanten]]
| [[Datei:Graph ungerichtet Mehrfachkanten.svg|gerahmt|Ungerichteter Graph mit Mehrfachkanten]]
| [[Datei:Graph gerichtet Mehrfachkanten.svg|gerahmt|Gerichteter Graph mit<br />Mehrfachkanten]]
|}

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 <math>G</math> mit den Symbolen <math>V</math> und <math>E</math> zu identifizieren, kann man auch allgemeine [[Abbildung (Mathematik)|Abbildungen]] <math>V</math> und <math>E</math> definieren, die einen Graphen auf dessen Knotenmenge oder Kantenmenge abbilden. Für zwei Graphen <math>G_1=(V_1,E_1)</math> und <math>G_2 = (V_2, E_2)</math> bezeichnen also <math>V(G_1) := V_1</math> und <math>E(G_1) := E_1</math> sowie <math>V(G_2) = V_2</math> und <math>E(G_2) = E_2</math>.

Die Mehrdeutigkeit <math>V(G) = V</math> und <math>E(G) = E</math> 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 <math>V</math> bzw. <math>E</math> ohne [[Funktion (Mathematik)|Argument]] Knoten- bzw. Kantenmenge zu bezeichnen, <math>V</math> bzw. <math>E</math> mit Argument bezeichnen dagegen die definierten Abbildungen.

Ist <math>G</math> ein Graph, so sagt man allgemein <math>v</math> ist ''Knoten'' bzw. ''Ecke'' von <math>G</math>, wenn <math>v</math> zu <math>V(G)</math> gehört. Außerdem bezeichnet man Kanten <math>e \in E(G)</math> als
* ''ungerichtete Kante'' von <math>G</math>, falls <math>G</math> ein ungerichteter Graph ist.
* ''gerichtete Kante'' von <math>G</math>, falls <math>G</math> ein gerichteter Graph ist.
* ''Hyperkante'' von <math>G</math>, falls <math>G</math> ein Hypergraph ist.

In einer ungerichteten Kante <math>e = \lbrace v, w \rbrace</math> bezeichnet man <math>v</math> und <math>w</math> als ''Endknoten'' von <math>e</math>. In einer gerichteten Kante <math>e = (v, w)</math> bezeichnet man <math>v</math> als ''Startknoten'' und <math>w</math> als ''Endknoten'' von <math>e</math>.

Bei Multigraphen bezeichnet <math>E(G)(e)</math> die ''Vielfachheit'' von <math>e</math>. Wenn <math>E(G)(e) > 1</math> gilt, so spricht man von einer ''Multi-'' oder ''Mehrfachkante''.

Hat eine Kante <math>e</math> in gerichteten Graphen die Form <math>(v, v)</math>, so spricht man von einer ''Schleife''. Ist die Schleife <math>e</math> in einem Multigraphen <math>G</math> zugleich eine Mehrfachkante, so spricht man von einer ''Mehrfachschleife''. Gerichtete Graphen ohne Schleifen nennt man ''schleifenlos'' oder ''schleifenfrei''.

Als ''Knotenzahl'' <math>n(G) = \vert V(G) \vert</math> eines Graphen <math>G</math> bezeichnet man die Anzahl seiner Knoten, als ''Kantenzahl'' <math>m(G) = \vert E(G) \vert</math> 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 <math>e_1</math> zwei Knoten, und die Kante <math>e_2</math> 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''.<!-- Zwangsläufig ist in diesen auch die Kantenmenge endlich. // Mehrfachkanten? --> Im Gegensatz dazu nennt man einen Graphen, dessen Knotenmenge unendlich ist, ''[[Unendlicher Graph|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 {{Anker|Zyklisch/azyklisch}} {{Anker|Gerichteter azyklischer Graph}} ====
[[Datei:Directed graph, cyclic.svg|mini|Ein gerichteter Graph mit Zyklus]]
[[Datei:Directed acyclic graph.svg|mini|Ein gerichteter Graph ohne Zyklus]]

Ein [[Teilgraph]] <math>G'</math> eines Graphen <math>G</math> enthält nur Knoten und Kanten, die auch in <math>G</math> 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 <math>v_1,\ldots,v_n</math>, in der aufeinander folgende Knoten <math>v_i</math> und <math>v_{i+1}</math> im Graphen durch eine Kante verbunden sind, bezeichnet man als [[Weg (Graphentheorie)|Weg]], manchmal auch als ''Pfad''. Gilt <math>v_1 = v_n</math>, und ist dies der einzige doppelte Knoten, spricht man von einem [[Zyklus (Graphentheorie)|Zyklus]] oder ''Kreis''. Eine Sequenz von benachbarten Knoten, in der sich Knoten wiederholen dürfen, bezeichnet man als [[Weg (Graphentheorie)|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'' ({{enS|DAG, directed acyclic graph}}). Ein solcher Graph lässt sich durch die Ergänzung aller Kanten, die gleichen Ausgangs- und Endknoten wie [[Weg (Graphentheorie)|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 [[Transitive Hülle (Relation)|transitiven Hülle]]. Ein [[Hasse-Diagramm]] ist ein gerichteter azyklischer Graph, bei dem die durch das [[Transitive Relation|Transitivitätsgesetz]] implizierten Kanten weggelassen sind ([[Transitive Hülle (Relation)#Transitive Reduktion|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 <math>G_1=(V_1,E_1)</math> und <math>G_2=(V_2,E_2)</math> Graphen desselben [[Typen von Graphen in der Graphentheorie|Typs]], so bezeichnet
* <math>G_1+G_2</math> den Graphen, der entsteht, wenn man die Knoten- und Kantenmenge vereinigt,
* <math>G_1-E_2</math> den Graphen, der entsteht, wenn man <math>E_2</math> von der Kantenmenge von <math>G_1</math> abzieht und
* <math>G_1-V_2</math> den Graphen, der entsteht, wenn man <math>V_2</math> von der Knotenmenge von <math>G_1</math> abzieht und alle Kanten entfernt, die Knoten aus <math>V_2</math> enthalten.

Man beachte dabei die unterschiedliche Definition der Begriffe Vereinigungsmenge und [[Differenzmenge]] für [[Menge (Mathematik)|Mengen]] und [[Multimenge]]n. Man schreibt auch abkürzend
* <math>G_1 + E_2</math>, falls <math>V_2</math> Teilmenge von <math>V_1</math> ist,
* <math>G_1 + V_2</math>, falls <math>E_2</math> leer oder Teilmenge von <math>E_1</math> ist,
* <math>G_1+\{v,w\}</math>, falls <math>G_2 = (\{v,w\},\{\{v,w\}\})</math>,
* <math>G_1 + v</math>, falls <math>G_2 = (\{v\},\{\})</math>,
* <math>G_1 - \{v,w\}</math>, falls <math>E_2 = \{\{v,w\}\}</math> und
* <math>G_1 - v</math> falls <math>V_2=\{v\}</math>.

[[Kantenkontraktion]] und die Bildung des [[Komplementgraph]]en sind weitere Basisoperationen.

== Bemerkungen ==
Ungerichtete Graphen ohne Mehrfachkanten sind Spezialfälle von Hypergraphen.
Multigraphen, in denen keine Mehrfachkanten vorkommen, sind zwar nicht formal, aber anschaulich äquivalent zu Graphen ohne Mehrfachkanten, weshalb man auch diese als Graphen ohne Mehrfachkanten bezeichnet. Es gibt eine bijektive Zuordnung zwischen den beiden Varianten.
In diesem Sinne sind Graphen ohne Mehrfachkanten also Spezialfälle von Graphen mit Mehrfachkanten. Ähnlich verhält es sich mit ungerichteten Graphen, die in gewissem Sinn Spezialfälle von gerichteten Graphen sind. Ist ein gerichteter Graph symmetrisch und schleifenlos, so bezeichnet man diesen auch als ''ungerichtet'', da es auch hier eine einfache eineindeutige Zuordnung zwischen beiden Varianten gibt (siehe auch [[Adjazenzmatrix]]).

Es lassen sich natürlich auch ungerichtete Graphen mit Schleifen definieren, wobei man diese wohl am einfachsten wie eben als (formale) Spezialfälle von gerichteten Graphen definiert und die Bedingung der Schleifenlosigkeit weg lässt. Solche Graphen sind aber nur selten Gegenstand der Betrachtungen in der Graphentheorie.

Der wohl allgemeinste Typ von Graphen sind gerichtete [[Hypergraph]]en mit Mehrfachkanten. Jeder oben definierte Graphentyp kann dann als Spezialfall von diesem betrachtet werden. Solche Graphen sind aber so gut wie gar nicht Gegenstand der Betrachtungen in der Graphentheorie, weshalb sie hier auch nicht näher erläutert werden.

Sollen Graphen als Darstellung eines Sachverhaltes herhalten, werden Algorithmen benötigt, die für das [[Graphzeichnen]] benötigt werden. Diese Disziplin der Informatik hat sich in den letzten Jahren stets fortentwickelt und liefert Lösungen für unterschiedliche Visualisierungen, die auf Graphen beruhen.

== Erweiterungen ==
Graphen können mit weiteren Eigenschaften bzw. Informationen ergänzt werden.

=== Gefärbte Graphen ===
Eine Erweiterung von Graphen <math>G = (V, E)</math> zu [[Knotengefärbter Graph|knotengefärbten Graphen]] erhält man, indem das Tupel <math>(V, E)</math> zu einem Tripel <math>(V, E, f)</math> ergänzt wird. <math>f</math> ist eine Abbildung von <math>V</math> in die Menge der [[natürliche Zahl|natürlichen Zahlen]]. Anschaulich gibt man jedem Knoten damit eine Farbe.

Statt der Knoten kann man in Graphen ohne Mehrfachkanten und in Hypergraphen auch die Kanten färben und spricht dann von einem ''[[Kantengefärbter Graph|kantengefärbten Graphen]]''. Dazu erweitert man ebenfalls das Tupel <math>(V, E)</math> zu einem Tripel <math>(V, E, f)</math>, wobei <math>f</math> aber eine Abbildung von <math>E</math> (statt von <math>V</math>) in die Menge der [[natürliche Zahl|natürlichen Zahlen]] ist. Anschaulich gibt man jeder Kante damit eine Farbe. In Graphen mit Mehrfachkanten ist dies zwar prinzipiell auch möglich, aber schwieriger zu definieren, insbesondere, wenn Mehrfachkanten entsprechend ihrer Vielfachheit mehrere verschiedene Farben zugeordnet werden sollen.

Man beachte, dass die Begriffe „Färbung“ und „färben“ in der Graphentheorie auch eine speziellere Bedeutung besitzen. Exakt spricht man dann zwar von [[Färbung (Graphentheorie)|gültiger Färbung]], lässt das Attribut „gültig“ aber meist weg.

Analog gibt es auch ''benannte Graphen'' <math>(V, E, f, g)</math>, bei denen Knoten und/oder Kanten einen Namen tragen, und die Abbildungen <math>f</math> bzw. <math>g</math> den Knoten bzw. Kanten einen Namen zuordnen. Die zuvor abgebildeten Beispiele sind benannte Graphen, bei denen die Knoten mit Buchstaben benannt wurden. Dies wird oft bei Visualisierungen gemacht, so dass man besser über den Graphen diskutieren kann.

=== Gewichtete Graphen ===
Statt von knoten- bzw. kantengefärbten Graphen spricht man von [[Knotengewichteter Graph|knoten-]] bzw. [[Kantengewichteter Graph|kantengewichteten]] Graphen, falls <math>f</math> statt in die natürlichen Zahlen in die [[Reelle Zahl|reellen Zahlen]] abbildet. Knoten- bzw. kantengefärbte Graphen sind also Spezialfälle von knoten- bzw. kantengewichteten Graphen.

Man bezeichnet <math>f(v)</math> bzw. <math>f(e)</math> auch als ''Gewicht'' des Knotens <math>v</math> bzw. der Kante <math>e</math>. Zur Unterscheidung spricht man auch von ''Knotengewicht'' bzw. ''Kantengewicht''. Eine solche Gewichtung wird erforderlich, wenn die Information über Knotenbeziehungen nicht ausreicht. Fasst man beispielsweise das Straßennetz (vereinfacht) als Graph auf (Orte sind Knoten, die Orte verbindende Straßen sind Kanten), so könnte eine Gewichtung der Kanten Aufschluss über die Distanz zwischen zwei Orten geben. Die Kantengewichte eines Graphen können in einer quadratischen Gewichtsmatrix, der [[Adjazenzmatrix]], gesammelt werden.

=== Abbildungen zwischen Graphen ===
{{Anker|Homomorphismus}}
Schließlich lassen sich auch Abbildungen zwischen Graphen definieren. Interessant sind insbesondere solche, die mit der Struktur der beiden [[Verträglichkeit (Mathematik)|verträglich]] sind, so genannte [[Homomorphismus|„Homomorphismen“]].

Seien dazu <math>G_1=\left(V_1,E_1\right)</math> und <math>G_2=\left(V_2,E_2\right)</math> Graphen desselben Typs. Eine [[Funktion (Mathematik)|Abbildung]] <math>p\colon V_1\to V_2</math> heißt ''Homomorphismus'' zwischen <math>G_1</math> und <math>G_2</math>, falls gilt:
* In [[Ungerichteter Graph|ungerichteten]] [[Graph ohne Mehrfachkanten|Graphen ohne Mehrfachkanten]]:<br /> Ist <math>\{v,w\}</math> eine Kante von <math>G_1</math>, so ist <math>\{p(v),p(w)\}</math> eine Kante von <math>G_2</math>.
* In [[Gerichteter Graph|gerichteten]] Graphen ohne Mehrfachkanten:<br /> Ist <math>(v,w)</math> Kante von <math>G_1</math>, dann ist <math>(p(v),p(w))</math> Kante von <math>G_2</math>.
* In ungerichteten [[Graph mit Mehrfachkanten|Graphen mit Mehrfachkanten]]:<br /> <math>E_1(\{v,w\}) \le E_2(\{p(v),p(w)\})</math>, d.&nbsp;h. je zwei Ecken sind mit höchstens so vielen Kanten verbunden wie ihre Bildecken.
* In gerichteten Graphen mit Mehrfachkanten:<br /> <math>E_1(v,w) \le E_2(p(v),p(w))</math>.
* In gerichteten Graphen mit eigenständigen Mehrfachkanten:<br /> <math>p</math> hat einen dazugehörenden Partner <math>q\colon E_1 \to E_2</math> und für alle Kanten <math>e\in E_1</math> gilt <math>\mathrm{src}_2(q(e)) = p(\mathrm{src}_1(e))</math> sowie <math>\mathrm{tgt}_2(q(e)) = p(\mathrm{tgt}_1(e))</math> (werden <math>G_1</math> und <math>G_2</math> als Funktoren angesehen, ist ein Graphhomomorphismus gerade eine [[natürliche Transformation]]).
* In [[Hypergraph]]en:<br /> Ist <math>\{v_1,\cdots,v_k\}</math> Kante von <math>G_1</math>, so ist <math>\{p(v_1),\cdots,p(v_k)\}</math> Kante von <math>G_2</math>.

Das Bild ''p''(''G''<sub>1</sub>) ist dann ein [[Teilgraph]] von ''G''<sub>2</sub>. Ist ''p'' [[Bijektivität|umkehrbar]] und die [[Umkehrfunktion]] ebenfalls ein Homomorphismus, so ist ''p'' ein [[Isomorphie von Graphen|Isomorphismus]] von Graphen.

Zu beachten ist, dass die Knoten vor den Kanten einen Vorrang haben, indem ''p'' als [[Funktion (Mathematik)|Funktion]] nur auf den Knoten spezifiziert ist, die auf den Kanten lediglich eine induzierte Wirkung entfaltet.

== Kombinatorik ==
Die Anzahl der [[Einfacher Graph|einfachen]] ungerichteten Graphen mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] steigt rasant mit der Anzahl der Knoten und ist gleich <math>2^{\tfrac{n \cdot (n - 1)}{2}}</math>. Sie steigt also [[Exponentieller Verlauf|exponentiell]] zur Anzahl <math>\tfrac{n \cdot (n - 1)}{2}</math> der [[Kante (Graphentheorie)|Kanten]] des [[Vollständiger Graph|vollständigen Graphen]] <math>K_n</math>. Wenn die Knoten nicht nummeriert sind, [[Isomorphie von Graphen|isomorphe Graphen]] also nicht mitgezählt werden, ist diese Anzahl etwa [[Proportionalität|proportional]] zu <math>\tfrac{1}{n!} \cdot 2^{\tfrac{n \cdot (n - 1)}{2}}</math>, weil für die meisten [[Isomorphieklasse]]n alle <math>n!</math> Graphen, die sich durch [[Permutation]] der nummerierten Knoten ergeben, verschieden sind. Die folgende [[Tabelle]] zeigt die mit Hilfe eines [[Computer]]s bestimmten Anzahlen für <math>n \leq 8</math>:<ref>{{OEIS|A000088}}</ref>

{| class="wikitable" style="text-align:right"
! colspan="3"|Anzahl der einfachen ungerichteten Graphen
|-
! n
! mit nummerierten Knoten
!ohne nummerierte Knoten
|-
!1
|1
|1
|-
! 2
| 2
|2
|-
! 3
| 8
|4
|-
! 4
| 64
|11
|-
! 5
| 1.024
|34
|-
! 6
| 32.768
|156
|-
! 7
| 2.097.152
|1.044
|-
! 8
| 268.435.456
|12.346
|}

== Datenstrukturen ==
{| class="wikitable" align="right" style="margin-left:1em"
!Ungerichteter Graph
!Adjazenzmatrix
|-
|[[Datei:6n-graph2.svg|175px]]
|<math>\begin{pmatrix}
1 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{pmatrix}</math>
|}

Für die Repräsentation von Graphen im [[Computer]] gibt es im Wesentlichen zwei gebräuchliche Formen: die [[Adjazenzmatrix]] (auch Nachbarschaftsmatrix) und die [[Adjazenzliste]] (Nachbarschaftsliste). Die Bedeutung der beiden Darstellungen liegt darin, dass praktisch jede algorithmische Lösung graphentheoretischer Probleme auf wenigstens eine der beiden Repräsentationen zurückgreift. Eine weitere, aber seltener genutzte Möglichkeit zur Darstellung von Graphen im Computer ist die [[Inzidenzmatrix]], die man auch als Knoten-Kanten-Matrix bezeichnet.

Inzidenzmatrizen sind zwar aufwändiger zu implementieren und zu verwalten, bieten aber eine Reihe von Vorteilen gegenüber Adjazenzmatrizen. Zum einen verbrauchen sie bei fester Anzahl von Kanten stets nur linear viel Speicherplatz bezüglich der Anzahl der Knoten, was insbesondere bei dünnen Graphen (also Graphen mit wenig Kanten) von Vorteil ist, während die Adjazenzmatrix quadratischen Platzbedarf bezüglich der Anzahl Knoten besitzt (dafür aber kompakter bei dichten Graphen, also Graphen mit vielen Kanten ist). Zum anderen lassen sich viele graphentheoretische Probleme nur mit Adjazenzlisten in [[Zeitkomplexität|linearer Zeit]] lösen. In der Praxis verwendet man daher meist diese Form der Repräsentation.

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C++]] zeigt die [[Implementierung]] eines [[Gerichteter Graph|gerichteten Graphen]] mit [[Adjazenzliste]]n. Der gerichtete Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''DirectedGraph'' deklariert. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''main'' verwendet.<ref>Software Testing Help: [https://www.softwaretestinghelp.com/graph-implementation-cpp/ Graph Implementation In C++ Using Adjacency List]</ref>
<syntaxhighlight lang="cpp">
#include <iostream>
using namespace std;

// Deklariert den Datentyp für die Knoten des Graphen
struct Node
{
    int index;
    string value;
    Node* next;
};

// Deklariert den Datentyp für die Kanten des Graphen
struct Edge
{
    int startIndex;
    int endIndex;
};

// Deklariert die Klasse für den gerichteten Graphen
class DirectedGraph
{
public:
	Node* nodes;
	Node** headNodes;

    // Diese Methode fügt einen neuen Knoten in die Adjazenzliste des Graphen ein und gibt ihn als Rückgabewert zurück
    Node* insertNewNode(int index, string value, Node* node)
    {
        Node* newNode = new Node; // Erzeugt einen neuen Knoten vom Typ Node
        newNode->index = index; // Setzt den Index
        newNode->value = value; // Setzt den Wert
        newNode->next = node; // Setzt einen Zeiger auf den Nachfolger
        return newNode;
    }

    // Konstruktor, der den gerichteten Graphen mit den gegebenen Knoten und Kanten erzeugt
    DirectedGraph(Node mynodes[], Edge edges[], int numberOfEdges, int numberOfNodes)
    {
    	nodes = mynodes; //speichert Knoten
		headNodes = new Node*[numberOfNodes](); // Initialisiert ein Array von Zeigern für die Nachbarknoten
        for (int i = 0; i < numberOfEdges; i++) // for-Schleife, die alle Kanten des Graphen durchläuft
        {
            int startIndex = edges[i].startIndex; // Index des Startknotens der Kante
            int endIndex = edges[i].endIndex; // Index des Endknotens der Kante
            string value = nodes[endIndex].value; // Wert des Endknotens der Kante
            Node* newNode = insertNewNode(endIndex, value, headNodes[startIndex]); // Aufruf der Methode insertNewNode, um einen neuen Knoten einzufügen
            headNodes[startIndex] = newNode; // Setzt den Zeiger auf den neuen Knoten
        }
    }
};

// Gibt alle benachbarten Knoten von node auf der Konsole aus
void writeAdjacencyList(Node* node, Node* neighbor)
{
    cout << "Knoten (" <<  node->index << ", " << node->value << "): ";
    while (neighbor != nullptr)
    {
        cout << "(" << neighbor->index << ", " << neighbor->value << ") ";
        neighbor = neighbor->next;
    }
    cout << endl;
}

// Hauptmethode, die das Programm ausführt
int main()
{
    // Deklariert und initialisiert Arrays für die Knoten und Kanten
    Node nodes[] = { {0,"A"},{1,"B"},{2,"C"},{3,"D"},{4,"E"} };
    Edge edges[] = { {0,1},{0,2},{1,4},{2,3},{3,1},{4,3} };
    int numberOfNodes = sizeof(nodes) / sizeof(nodes[0]); // Ermittelt die Anzahl der Knoten
    int numberOfEdges = sizeof(edges) / sizeof(edges[0]); // Ermittelt die Anzahl der Kanten
    DirectedGraph directedGraph(nodes, edges, numberOfEdges, numberOfNodes); // Erzeugt den gerichteten Graphen mit den gegebenen Knoten und Kanten
    for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten des Graphen durchläuft
    {
        Node* headNode = directedGraph.headNodes[i];
        writeAdjacencyList(&nodes[i], headNode); // Gibt die Adjazenzliste für den Knoten node mit Nachbarn headNode aus
    }
}



</syntaxhighlight>

== Siehe auch ==
* [[Graphenspiele]]
* [[Kleine-Welt-Phänomen]] (Small-world-Netzwerk)
* [[Skalenfreies Netz]]
* [[Zufallsgraph]]
* [[Bandgraph]]
* [[Mengensystem]]

== Literatur ==
* {{Literatur
   |Autor=Thomas H. Cormen, [[Charles Leiserson]], [[Ronald L. Rivest]], Clifford Stein
   |Titel=Algorithmen – Eine Einführung
   |Auflage=2.
   |Verlag=Oldenbourg Wissenschaftsverlag
   |Ort=München
   |Datum=2007
   |ISBN=978-3-486-58262-8
   |Seiten=531–533}}
* {{Literatur
   |Autor=[[Reinhard Diestel]]
   |Titel=Graphentheorie
   |Auflage=4.
   |Verlag=Springer
   |Ort=Berlin u.&nbsp;a.
   |Datum=2010
   |ISBN=978-3-642-14911-5
   |JahrEA=1996
   |Online=[https://diestel-graph-theory.com/basic.html online: 4th Electronic Edition 2010, Free preview version]}}
* {{Literatur
   |Autor=Jürgen Ebert
   |Titel=Effiziente Graphenalgorithmen
   |Sammelwerk=Studien-Texte – Informatik
   |Verlag=Akademische Verlags-Gesellschaft
   |Ort=Wiesbaden
   |Datum=1981
   |ISBN=3-400-00424-3
   |Kommentar=Zugleich [[Habilitationsschrift]] an der [[Universität Osnabrück]] 1982}}
* {{Literatur
   |Autor=[[Dieter Jungnickel]]
   |Titel=Graphen, Netzwerke und Algorithmen
   |Auflage=3. vollständig überarbeitete und erweiterte
   |Verlag=BI-Wissenschafts-Verlag
   |Ort=Mannheim u.&nbsp;a.
   |Datum=1994
   |ISBN=3-411-14263-4
   |Online=[https://www.gbv.de/dms/ilmenau/toc/164094962.PDF Inhaltsverzeichnis]
   |Format=PDF
   |KBytes=1140}}
* {{Literatur
   |Autor=Manfred Nitzsche
   |Titel=Graphen für Einsteiger. Rund um das [[Haus vom Nikolaus]]
   |Sammelwerk=Studium
   |Auflage=3., überarbeitete und erweiterte
   |Verlag=Vieweg+Teubner
   |Ort=Wiesbaden
   |Datum=2009
   |ISBN=978-3-8348-0813-4}}

== Einzelnachweise ==
<references />

{{Gesprochene Version
| datum      = 2022-06-16
| datei      = De-Graph (Graphentheorie)-article.ogg
| länge      = 26:00
| größe      = 12,3 MB
| version    = 223378220
| sprecher   = Erwin Völkening
| geschlecht = männlich
| dialekt    = Hochdeutsch
}}
{{Normdaten|TYP=s|GND=4021842-9}}

[[Kategorie:Grundbegriff (Graphentheorie)]]