Binäre Relationen (1)


Zwischen gerichteten Graphen und binären Relationen  besteht ein unmittelbarer Zusammenhang: eine binäre Relation R über einer Grundmenge M ist eine Menge von Paaren R  MM, welche bestehende Beziehungen zwischen den Elementen von M beschreibt; für <a,b>R schreibt man gerne aRb. Der zugehörige gerichtete Graph (M,R) heißt Relationsgraph oder auch Pfeildiagramm zu R; er beschreibt anschaulich dieselbe Information.

Für die technische Darstellung von binären Relationen haben wir dieselben Möglichkeiten zur Verfügung wie bei gerichteten Graphen; dazu kommen noch ein paar Sonderfälle. Oft wird die Inzidenzmatrix nicht mit Wahrheitswerten, sondern mit den Werten 0 (für FALSE) und 1 (für TRUE) besetzt, das kann manchmal bequem sein.

Aus der Darstellung als Inzidenzmatrix sieht man leicht, daß die Anzahl der möglichen Relationen auf einer gegebenen Grundmenge außerordentlich groß ist, nämlich 2**(n**2) für n Knoten (für nur 3  Knoten gibt es bereits 512 Relationen, und die meisten davon sind völlig uninteressant).

Für die Praxis bedeutsam sind Relationen mit speziellen Eigenschaften:


zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36