Transitive Hülle (Relation)

Die transitive Hülle bzw. der transitive Abschluss einer (zweistelligen) Relation ist eine Erweiterung dieser Relation, die – vereinfacht gesagt – zusätzlich alle indirekt erreichbaren Paare enthält (und damit transitiv ist). Die transitive Hülle kann mit dem Warshall-Algorithmus berechnet werden.

Die reflexiv-transitive Hülle bzw. den reflexiv-transitiven Abschluss der Relation erhält man, indem man zur transitiven Hülle die für Reflexivität noch fehlenden Paare auf der Diagonalen hinzufügt.

Anschauliches Beispiel

Illustration des Beispiels: durchgezogene Pfeile zeigen direkte Beziehungen an, gestrichelte Pfeile die in der transitiven Hülle dazu kommenden Relationen

Gegeben sei eine Relation „Direkter-Vorgesetzter“ mit folgenden Beziehungen:

Die transitive Hülle dieser Relation enthält nun zusätzlich auch die indirekten Vorgesetzten:

Mathematische Definition

Die transitive Hülle R^{+} einer zweistelligen Relation R auf einer Menge M ist gegeben durch:

x\ R^{+}\ y:\Leftrightarrow \exists n\geq 0\ \exists x_{1},\dots ,x_{n}\in M:x\,R\,x_{1}\,R\,x_{2}\,R\dots \,R\,x_{n}\,R\,y

Die reflexiv-transitive Hülle R^{{*}} ergibt sich dann durch

x\ R^{*}\ y:\Leftrightarrow x=y\lor x\ R^{+}\ y

Beispiele

Eigenschaften

Die Menge, über die hier der Durchschnitt gebildet wird, ist nicht leer, da sie ja immer die Allrelation (also M\times M) enthält.

Anwendungen

In der Theoretischen Informatik werden Ableitungen in einer formalen Grammatik als Folgen von Ableitungsschritten v\Rightarrow w definiert. Die Ableitbarkeit ist also der reflexiv-transitive Abschluss \Rightarrow ^{{*}} der Transitionsrelation \Rightarrow .

Transitive Reduktion

Das Gegenstück zur transitiven Hülle ist die transitive Reduktion. Eine transitive Reduktion einer Relation R ist eine minimale Relation R^{\prime } so dass R^{+}=(R^{\prime })^{+}, also eine minimale Relation mit derselben transitiven Hülle.

Es gibt sowohl Relationen, für die keine transitive Reduktion existiert, als auch solche, für die mehrere unterschiedliche transitive Reduktionen existieren. Für gerichtete endliche azyklische Graphen jedoch existiert die transitive Reduktion und ist eindeutig: {\displaystyle R^{\prime }=R^{+}\setminus (R^{+})^{2}}.

Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 22.01. 2019