Graph

Ein Graph ist ein Gebilde, das aus Knoten und Kanten besteht. Jede Kante verbindet zwei Knoten oder einen Knoten mit sich selbst. Von einem Knoten können eine, mehrere oder keine Kanten ausgehen. Formal ist ein Graph also ein 2-Tupel, das aus einer Knotenmenge und einer Kantenmenge besteht und man schreibt: Graph G = (V,E) mit V: Knotenmenge und E: Kantenmenge

Die Buchstaben sind aus den englischen Begriffen abgeleitet: V ist die Menge von Knoten (Vertices) und E die Menge der Kanten (Edges).

Das Bild rechts veranschaulicht die Begriffe, man erkennt dort auch, wie man die Kanten darstellen kann, indem man die verbundenen Knoten in runden Klammern durch ein Komma getrennt angibt. In der Menge der Kanten fehlt (d,b), weil der Knoten d nicht mit dem Knoten b verbunden ist.