engl.: digraph

Ein gerichteter Graph (engl. digraph) G = (V , E ) besteht aus

• einer endlichen Menge V von Knoten (engl. vertices)
• einer Menge E ⊆ V × V von Kanten (engl. edges)

Ist (va, ve) eine Kante, dann nennt man

• va den Anfangs- oder Startknoten oder die Quelle
• ve den Endknoten oder das Ziel

der Kante. ve heißt von va direkt erreichbar und Nachfolger von va; va Vorgänger von ve.

Graphen bieten für eine große Klasse von Problemen ein geeignetes abstraktes Modell.