Transitiver Abschluss

Der transitive Abschluss einer Relation ist die kleinste Relation, die die ursprüngliche Relation enthält und die Transitivitätsbedingung erfüllt. Mit anderen Worten: Wenn die ursprüngliche Relation Verbindungen a → b und b → c hat, enthält der transitive Abschluss immer auch a → c.

Formale Definition

Hier bedeutet Rⁿ die n-fache Komposition der Relation mit sich selbst. Der transitive Abschluss enthält somit jede Verbindung, die durch endliche Längen-Ketten aus der ursprünglichen Relation erreichbar ist.

Beispiel

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

Der transitive Abschluss R⁺ = { (1,2), (2,3), (3,4), (1,3), (2,4), (1,4) }, weil (1,3) aus (1,2) und (2,3) folgt, (2,4) aus (2,3) und (3,4), und (1,4) aus (1,3) und (3,4) oder längeren Ketten.

Eigenschaften

• Der transitive Abschluss ist immer transitiv.
• Der transitive Abschluss enthält die ursprüngliche Relation: R ⊆ R⁺.
• Der transitive Abschluss ist die kleinste transitive Relation, die R enthält.
• Wenn R bereits transitiv ist, dann R⁺ = R.

Graphische Interpretation

In der Graphentheorie zeigt der transitive Abschluss, welche Punkte von einem gegebenen Punkt durch Pfade erreichbar sind. Zum Beispiel, wenn es einen Pfad von A nach B und B nach C gibt, enthält der transitive Abschluss die Verbindung von A nach C.

Zusammenfassung

Der transitive Abschluss ist eine Erweiterung einer Relation, die Transitivität sicherstellt und die wenigsten neuen Elemente hinzufügt. Dieses Konzept ist Schlüssel in der Mathematik, Algorithmen und Graphentheorie.

Übungsaufgabe