Das Kefk Network Wiki befindet sich im Testbetrieb.

Graph (Graphentheorie)

Aus Kefk.

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.

Inhaltsverzeichnis

1 Definition
- 1.1 Gerichteter Graph
- 1.2 Gewichteter Graph
2 Kategorisierung von Graphen
3 Literatur
4 Siehe auch

Definition

Ein Graph $G$ ist ein Paar zweier endlicher Mengen $V$ und $E$ . Dabei bezeichnet $V$ die Menge der im Graph enthaltenen Knoten 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“). Für $V$ und $E$ gelten die Bedingungen:

$V \not = \varnothing$ und $V \cap E = \varnothing$

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

$\Psi : E \mapsto V$

Gerichteter Graph

Ein Graph $G = (V, E)$ heißt gerichtet, wenn zu jedem $e\in E$ das durch $Ψ$ 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 $Ψ$ zugeordnete Paar ${v, v'}$ nicht geordnet ist, wenn also gilt:

Ψ(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

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Graph_%28Graphentheorie%29, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.

, ISBN 3540213910.