Modallogik/Gerichteter Graph/Einführung/Textabschnitt

Für die Modelltheorie der Modallogik benötigen wir gerichtete Graphen. Dies ist mathematisch betrachtet einfach eine zweistellige Relation auf einer Menge.


Ein gerichteter Graph ist eine Menge versehen mit einer fixierten Relation .

Die Menge der Punkte nennt man auch die Knoten des Graphen und man sagt, dass ein Pfeil von nach geht, wenn ist. In dieser Weise werden gerichtete Graphen veranschaulicht. Ein Pfeil von einem Knoten zu sich selbst heißt Schleife.

Im Kontext von Ordnungsrelationen und Äquivalenzrelationen haben wir schon die Eigenschaften reflexiv, symmetrisch, transitiv kennengelernt. Einen symmetrischen gerichteten Graphen nennt man auch einen ungerichteten Graphen. In diesem Fall nennt man einen verbindenden Pfeil eine Kante. Wir besprechen einige weitere Begrifflichkeiten und Eigenschaften.


Es sei ein gerichteter Graph. Zu einer Teilmenge nennt man

die Vorgängermenge zu .


Es sei ein gerichteter Graph. Zu einer Teilmenge nennt man

die Nachfolgermenge zu .

Ein Knoten ohne Nachfolger, also ohne abgehenden Pfeil (also auch keine Schleife), heißt Sackgasse.


Eine Relation auf einer Menge heißt euklidisch, wenn zu mit und stets gilt.