Relationenkomposition

Die Komposition zweier Relationen erzeugt eine neue Relation, indem die erste mit der zweiten 'verbunden' wird. Wenn in der ersten Relation ein Element mit einem Zwischen-Element verbunden ist und in der zweiten Relation dieses Zwischen-Element mit einem Dritten verbunden ist, dann verbindet die Komposition das Erste mit dem Dritten.

Formale Definition

Mit anderen Worten: Zuerst wenden wir die S-Relation an, dann die R-Relation. Wenn S a mit b verbindet und R b mit c, dann verbindet die Komposition (R ∘ S) a mit c.

Beispiel für Komposition

Nehmen wir an, wir haben zwei Relationen:

• S = "Geschwister von"-Relation unter Menschen.
• R = "Kind von"-Relation unter Menschen.

Die R ∘ S-Komposition gibt an, wer das Kind meines Geschwisters ist – also mein Neffe/Nichte.

Eigenschaften

• Die Komposition ist nicht kommutativ: Im Allgemeinen R ∘ S ≠ S ∘ R.
• Die Komposition ist assoziativ: (R ∘ S) ∘ T = R ∘ (S ∘ T).
• Auch wenn R und S transitiv sind, ist ihre Komposition nicht notwendigerweise transitiv.

Weiteres Beispiel

Sei S = { (1,2), (2,3) } und R = { (2,4), (3,5) }. Dann ist die Komposition R ∘ S = { (1,4), (2,5) }, weil 1 mit 2 in S verbunden ist, 2 mit 4 in R, also 1 mit 4 in der Komposition; ähnlich 2 mit 3, und 3 mit 5, also (2,5) auch darin.

Zusammenfassung

Die Relationenkomposition ermöglicht es, zwei verschiedene Verbindungen nacheinander anzuwenden und so eine neue Verbindung zu erzeugen. Dies ist ein nützliches Werkzeug in Mathematik und Informatik, z.B. bei der Analyse von Graphen, Datenbanken und Funktionen.

Übungsaufgabe