Graph (Graphentheorie)

Ein Graph ist in der Graphentheorie ein Gebilde aus Knoten (auch Ecken oder Punkte), die durch Kanten verbunden sein können. Obwohl Graphen vielfach durch eine Zeichnung dargestellt werden, sind sie „nur“ mathematische Strukturen. Dies bedeutet vor allem, dass verschiedene Bilder denselben Graphen darstellen können.

Die zeichnerische Darstellung eines einfachen ungerichteten Graphen mit sechs Knoten und sieben hier unbenannten Kanten

Definition

Ein Graph $G$ ist ein Paar zweier endlicher Mengen $V$ und $E$. Dabei bezeichnet $V$ die Menge der im Graph enthaltenen Knoten (oder Ecken) und $E$ die Menge der Kanten des Graphen. Die Bezeichnungen der Mengen entstammen dem Englischen: $V$ für vertex (engl. für „Knoten“) und $E$ für edge (engl. für „Kante“). E bezeichnet also nicht die Eckenmenge. Für $V$ und $E$ gilt $V\cap E=\emptyset$ und in der Regel auch $V\neq \emptyset$, also das Ausschließen eines sogenannten Nullgraphen.

Außerdem besitzt jeder Graph eine auf der Kantenmenge E definierte Abbildung $\Psi$ mit

$\Psi :E\mapsto V^{2}$

Gerichteter Graph

Ein Graph $G=(V,E)$ heißt gerichtet, wenn zu jedem $e\in E$ das durch $\Psi$ zugeordnete Paar $(v,v')$ geordnet ist ($v,v'\in V$) . Anschaulich bedeutet ein gerichteter Graph, dass sich die Kante $e\in E$ von einem Knoten $v\in V$ zu einem Knoten $v'\in V$ durch einen Pfeil darstellen lässt.

Ein Graph $G=(V,E)$ heißt ungerichtet, wenn zu jedem $e\in E$ das durch $\Psi$ zugeordnete Paar $\{v,v'\}$ nicht geordnet ist, wenn also gilt:

$\Psi (e)=\{v,v'\}=\{v',v\}$

Es sei angemerkt, dass in einem Graphen $G$ durchaus gerichtete Kanten zusammen mit ungerichteten Kanten auftreten können.

Gewichteter Graph

Ein Graph heißt gewichtet (auch: bewertet), wenn die Kantenmenge $E$ mit Werten versehen ist. Die Bewertung eines Graphen wird durch eine quadratische Bewertungsmatrix

$B\in \mathbb {R} ^{m\times m}$ mit $m=|V|$

beschrieben.

In praktischen Anwendungen können die Bewertungen zum Beispiel Kosten, Gewinnen oder Zeiten entsprechen.

Kategorisierung von Graphen

Man unterscheidet in der Graphentheorie vor allem zwischen ungerichteten und gerichteten Graphen sowie Graphen mit Mehrfachkanten und ohne Mehrfachkanten. Hypergraphen sind eine weitere Form von Graphen, die untersucht werden.

Literatur

• Reinhard Diestel: Graphentheorie, Auflage: 3. Springer, 2006, ISBN 3-540-21391-0. 
• Jürgen Ebert: Effiziente Graphenalgorithmen. Akademische Verlagsgesellschaft, Wiesbaden 1981, ISBN 3-400-00424-3. 

Siehe auch

• Repräsentation von Graphen im Computer, z. B. mittels einer Adjazenzmatrix
• Typen von Graphen in der Graphentheorie
• Wege, Pfade, Zyklen und Kreise in Graphen
• Polybaum