Kanten können gewichtet sein durch eine Kostenfunktion c : E .
Ein ungerichteter Graph G = (V,E) besteht aus
Knotenmenge
V und Kantenmenge
E P2(V) = 2 -elem. Teilmengen von V .
Mit Graphen können zwischen Objekten ( Knoten) binäre Beziehungen ( Kanten) modelliert werden.
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.