Graphen sind eine Datenstruktur, mit der komplexe Beziehungen zwischen Daten dargestellt werden können.

Deutschland und Nachbarländer

Terminologie

Ein Graph besteht aus Kanten und Knoten (engl.: Vertex und Edge). Im obrigen Beispiel sind als Knoten Deutschland und seine Nachbarländer zu sehen. Als Kante bezeichnet man die Verbindung zweier Knoten, im Beispiel die gemeinsamen Grenzen.

Man kann durch einen Graphen einen Pfad legen. Dieser beschreibt eine bestimmte Reihenfolge, in dem man die einzelnen Knoten besucht. Eine Reise-Route von Belgien nach Polen über die Schweiz könnte zum Beispiel der Pfad BEDECHATCZPLBE \rightarrow DE \rightarrow CH \rightarrow AT \rightarrow CZ \rightarrow PL sein.

Belgien nach Polen

Besondere Pfade

Euler-Tour, Euler-Pfad

Eine Euler-Tour ist ein Pfad, der jeden Kante des Graphen genau ein mal besucht. Damit eine Euler-Tour zugleich ein Euler-Pfad ist, müssen Anfangs- und Endknoten verbunden sein.

Ein Euler-Pfad durch das Haus des Nikolaus:

Haus vom Nikolaus

Ein Graph besitzt eine Euler-Tour, wenn alle Knoten eine gerade Kardinalität, also eine gerade Anzahl an anliegenden Kanten, besitzen.

Hamilton-Zyklus

Ein Hamilton-Zyklus ist ein Pfad, der jeden Knoten des Graphen einmal enthält.

Hamilton-Zyklus

Jede Euler-Tour ist zugleich ein Hamilton-Zyklus. Im Gegensatz zur Euler-Tour, die sich leicht finden lässt, ist das finden eines Hamilton-Zyklus’ NP-vollständig.

Gerichtete Graphen

Eine Kante verbindet zwei Punkte. Wenn sie zusätzlich eine Richtung enthält, in der sie verbindet, spricht man von einem gerichteten Graphen.

graphviz-bc94abd44d7abd8cab2f4c4438cab151 digraph { scale=0.7 Alice -> Bob Bob -> Carl Bob -> Alice Gustav -> Friedrich Friedrich -> Elena Elena -> Dora Elena -> Carl Dora -> Bob Friedrich -> Carl Alice -> Elena Gustav -> Alice Friedrich -> Alice Friedrich -> Bob Friedrich -> Gustav } %3 Alice Alice Bob Bob Alice->Bob Elena Elena Alice->Elena Bob->Alice Carl Carl Bob->Carl Gustav Gustav Gustav->Alice Friedrich Friedrich Gustav->Friedrich Friedrich->Alice Friedrich->Bob Friedrich->Carl Friedrich->Gustav Friedrich->Elena Elena->Carl Dora Dora Elena->Dora Dora->Bob

Dieser Graph stellt ein kleines soziales Netwerk dar. Eine Kante ABA \rightarrow B bedeutet hier “A folgt B”, im Beispiel folgt Gustav also Friedrich und Alice.

Ein gerichteter Graph darf nur gerichtete Kanten enthalten, ein ungerichteter Graph nur ungerichtete. Eine ungerichtete Kante lässt sich immer durch zwei gerichtete Kanten zwischen den beiden Knoten übersetzen.

Gewichtete Kanten

Man kann Graphen um eine Gewichtung einzelner Kanten erweitern. Dann kann eine Kante neben der Information, welche beiden Knoten miteinander verbunden sind, auch zusätzliche Informationen speichern.

graphviz-a850347cdec35622da6df52cebe964fd digraph { DE -> NL [label="85,886 Mrd €", weight="85.886.368.000"]; NL -> DE [label="91,373 Mrd €", weight="91.373.944.000"]; DE -> BE [label="44,268 Mrd €", weight="44.268.388.000"]; BE -> DE [label="44,268 Mrd €", weight="44.268.388.000"]; DE -> LU [label="5,773 Mrd €", weight="5.773.964.000"]; LU -> DE [label="3,419 Mrd €", weight="3.419.324.000"]; NL -> BE [label="51,883 Mrd €", weight="51.883.704.699"]; BE -> NL [label="48,176 Mrd €", weight="48.176.139.425"]; NL -> LU [label="1.265 Mrd €", weight="1.265.722.812"]; LU -> NL [label="1.014 Mrd €", weight="1.014.461.856"]; BE -> LU [label="6.582 Mrd €", weight="6.582.281.453"]; LU -> BE [label="2.813 Mrd €", weight="2.813.947.802"]; } %3 DE DE NL NL DE->NL 85,886 Mrd € BE BE DE->BE 44,268 Mrd € LU LU DE->LU 5,773 Mrd € NL->DE 91,373 Mrd € NL->BE 51,883 Mrd € NL->LU 1.265 Mrd € BE->DE 44,268 Mrd € BE->NL 48,176 Mrd € BE->LU 6.582 Mrd € LU->DE 3,419 Mrd € LU->NL 1.014 Mrd € LU->BE 2.813 Mrd €

In diesem Graph sieht man zum Beispiel die Handelsvolumina zwischen den Deutschland, Belgien, Luxemburg und den Niederlanden.

TL;DR

Graphen bestehen aus Knoten und Kanten, die jeweils zwei Knoten mit einander verbinden. Enthalten die Kanten Richtungsinformationen, so spricht man von einem gerichteten Graphen. Speicher die Kanten Werte, so spricht man von einem gewichteten Graphen.

Mit Graphen kann man einfach komplexe Beziehungen, zum Beispiel ein soziales Netzwerk oder eine Karte, darstellen.