Gerichteter Graph

Ein gerichteter Graph oder Digraph (von englisch directed graph) besteht aus

• einer Menge ${\displaystyle V}$ von Knoten (englisch vertex/vertices, oft auch Ecken genannt) und
• einer Menge geordneter Knotenpaare ${\displaystyle E\subseteq V\times V}$ von Kanten.

Die Kanten ${\displaystyle (v,w)\in E}$ 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 ${\displaystyle \{v,w\}}$. Gerichtete Graphen werden dazu benutzt, Objekte und die dazwischenliegenden Verbindungen, beispielsweise von endlichen Automaten, darzustellen.