Graph

Mathematik

Grafische Darstellung einer Funktion im Koordinatensystem.

Operations Research

1. Begriff: Ein Graph besteht aus einer nichtleeren Menge von V und einer Menge E mit V ∩ E = 0 sowie einer auf E definierten Abbildung w, die jedem Element k aus E genau ein Paar i und j von Elementen aus V zuordnet. Wird auch als Netzwerk bezeichnet.

2. Typen: a) Ungerichteter Graph: Das jedem Element k E zugewiesene Paar von Elementen aus V ist nicht geordnet. Die Elemente von E werden Kanten genannt.

b) Gerichteter Graph: Das jedem Element p E zugewiesene Paar von Elementen aus V ist geordnet (p = (i, j)). Ein Knoten i heißt Vorgänger bzw. Nachfolger des Knoten j, falls ein Pfeil (i, j) bzw. (j, i) existiert. Vorgänger und Nachfolger werden als Nachbarn bezeichnet.

Vgl. auch Flussgraph, bewerteter Digraph.

3. Schreibweise: Bei der Schreibweise wird auf die Angabe der Inzidenzabbildung verzichtet. Sie wird implizit berücksichtigt, indem E als Menge von nicht geordneten oder geordneten Knotenpaaren angegeben wird. Ein ungerichteter Graph wird mit G (V, E), ein gerichteter Graph mit G (V, E) beschrieben.

4. Darstellung: Anschaulich kann jeder Knoten geometrisch mit einem Punkt oder Kreis und jede Kante (bzw. jeder Pfeil) mit einer Verbindungslinie (bzw. gerichteten Verbindungslinie) zwischen den zugeordneten Knoten identifiziert werden. Diese geometrische Darstellung eines Graphen nennt man Diagramm bzw. Pfeildiagramm.

Bild in Originalgröße zeigen