gerichteter Graph

Ein gerichteter Graph oder Digraph (von englisch directed graph) besteht aus * einer Menge von Knoten (englisch vertex/vertices, oft auch Ecken genannt) und * einer Menge geordneter Knotenpaare von Kanten. Die Kanten eines gerichteten Graphen sind gerichtete Kanten (englisch directed edge/edges, manchmal auch Bögen). Diese werden häufig als Pfeile dargestellt und können nur in einer Richtung durchlaufen werden. Im Gegensatz dazu sind die Kanten eines ungerichteten Graphen ungeordnete Knotenpaare .Gerichtete Graphen werden dazu benutzt, Objekte und die dazwischenliegenden Verbindungen, beispielsweise von endlichen Automaten, darzustellen.