9.1 Definitionen

Ein gerichteter Graph G = (V,E) besteht aus
Knotenmenge V und Kantenmenge E $\subseteq$ V × V

gerichteter, gewichteter Graph

Kanten können gewichtet sein durch eine Kostenfunktion c : E $\rightarrow$ $\mathbb {Z}$ .

Ein ungerichteter Graph G = (V,E) besteht aus
Knotenmenge V und Kantenmenge E $\subseteq$ P₂(V) = 2 -elem. Teilmengen von V .

ungerichteter, gewichteter Graph

Mit Graphen können zwischen Objekten ( $\equiv$ Knoten) binäre Beziehungen ( $\equiv$ Kanten) modelliert werden.

Modellierung und Definitionen

Ein Weg ist eine Folge von adjazenten Knoten.
Ein Kreis ist ein Weg mit Anfangsknoten = Endknoten.
Ein Spannbaum ist ein kreisfreier Teilgraph, bestehend aus allen Knoten.
Eine Zusammenhangskomponente ist ein maximaler Teilgraph, bei dem zwischen je zwei Knoten ein Weg existiert.