Matrixdarstellung von Relationen

Eine Relation kann anschaulich und leicht handhabbar mit einer Matrix dargestellt werden. Die Matrixdarstellung ist besonders nützlich für computerbasierte Verarbeitung und Graphenanalyse.

Formale Beschreibung

Sei A = {a₁, a₂, …, aₙ} eine Menge und R eine Relation auf A. Die Matrix der Relation ist eine n×n 0-1-Matrix M, wobei:

Die Zeilen und Spalten sind nach den Elementen von A in derselben Reihenfolge indiziert. Der Eintrag M[i,j] ist 1, wenn eine Verbindung von a_i zu a_j besteht, andernfalls 0.

Beispiel

Sei A = {1,2,3}, R = { (1,2), (2,3) }.

Die Matrix ist:

Zeile 1 (für 1): Verbunden mit 2, also zweiter Eintrag 1. Zeile 2 (für 2): Verbunden mit 3, also dritter Eintrag 1. Alle anderen 0.

Eigenschaften in Matrixform

• Reflexive Relationen haben 1en auf der Hauptdiagonalen.
• Symmetrische Relationen haben eine symmetrische Matrix bezüglich der Hauptdiagonalen.
• Für transitive Relationen können Potenzen der Matrix (Komposition) neue Verbindungen erzeugen.
• Die Matrixdarstellung erleichtert die Implementierung computerbasierter Algorithmen.

Zusammenfassung

Die Matrixdarstellung von Relationen ist eine einfache Methode, Verbindungen festzuhalten: Wir zeigen alle Verbindungen zwischen Elementen der Menge in 0-1-Matrixform. Das ist besonders nützlich in der Graphenanalyse und computerbasierten Verarbeitung.

Übungsaufgabe