Graph

aus www.iwiki.de, der freien Wissensdatenbank

Der Graph (v. griech.: γραφή grafí = Schrift, Graphie) bezeichnet in der Mathematik die Darstellung einer reellen Funktion. Graphen haben eine allgemeingültige Datenstruktur zum modellieren von Beziehungen zwischen Objekten. Die Objekte werden mittels Eckpunkten im Graphen dargestellt und wenn zwei dieser Objekte in Beziehung miteinander stehen durch eine Kante (Linie) verbunden.

Inhaltsverzeichnis

1 Definition
2 Charakteristik von Graphen
- 2.1 Gerichteter Graph
- 2.2 Gewichteter Graph
3 Beispiele
4 Weblinks

[bearbeiten]

Definition

Ein Graph G besteht aus einer Menge V(G) von Elementen (sog. Eckpunkte, Knoten oder Punkte) und einer Menge E(G) := {(x,y)|x,y $\in$ V(G)} von Knotenpaaren, sog. Kanten.

[bearbeiten]

Charakteristik von Graphen

Pfad:	Liste von Knoten in der jedes aufeinander folgende Knotenpaar eine Kante bildet
Länge:	Für einen Pfad mit k Knoten ist die Länge des Pfades k
Kreislauf:	Pfad in welchem der erste Knoten gleichzeitig der letzte ist und sich keine Kanten wiederholen.

[bearbeiten]

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.

[bearbeiten]

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