Erreichbarkeitsrelation

Die Erreichbarkeitsrelation hängt mit einer gegebenen Relation zusammen und zeigt, ob ein Element von einem anderen durch direkte oder indirekte Verbindungen in Folge erreichbar ist. Dieses Konzept hängt eng mit dem transitiven Abschluss zusammen.

Formale Definition

Sei R eine Relation auf einer Menge A. Die Erreichbarkeitsrelation R* ist so definiert, dass (a,b) ∈ R* genau dann, wenn es eine endliche Kette a = x₀, x₁, …, xₙ = b von Elementen gibt, in der jedes (x_i, x_{i+1}) ∈ R.

Das umfasst die leere Kette für Reflexivität: Jedes Element erreicht sich selbst (n=0, R^0 = Identität).

Graphische Interpretation

In Graphentermen, wenn wir die Relation R als gerichteten Graphen darstellen (Knoten = Elemente von A, Kanten = Paare in R), dann besteht die Erreichbarkeitsrelation R* aus allen Paaren (a,b), bei denen es einen gerichteten Pfad von a nach b im Graphen gibt.

Beispiel: Sei A = {a,b,c}, R = {(a,b), (b,c)}. Dann R* = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c)}, weil a b direkt erreicht, b c direkt, und a c über b.

Eigenschaften

• Die Erreichbarkeitsrelation ist immer reflexiv.
• Die Erreichbarkeitsrelation ist immer transitiv.
• Wenn die ursprüngliche Relation symmetrisch ist, ist die Erreichbarkeitsrelation auch symmetrisch.
• Die Erreichbarkeitsrelation entspricht dem reflexiven transitiven Abschluss der Relation.

Zusammenfassung

Die Erreichbarkeitsrelation zeigt, ob ein Element von einem anderen durch direkte oder indirekte Verbindungs-Ketten erreichbar ist. Dieses Konzept ist grundlegend in der Graphentheorie, Algorithmen und Netzwerkanalyse.

Übungsaufgabe