imported>Graf Alge: Änderung 242443837 von MechJayTi rückgängig gemacht; war korrekt

2024-02-22T19:41:37Z

Änderung 242443837 von MechJayTi rückgängig gemacht; war korrekt

Neue Seite

Die '''transitive Hülle''' bzw. der '''transitive Abschluss''' einer (zweistelligen) [[Relation (Mathematik)|Relation]] ist die kleinste Erweiterung dieser Relation, die [[Transitive Relation|transitiv]] ist. Sie kann mit dem [[Floyd-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 [[Reflexive Relation|Reflexivität]] noch fehlenden Paare auf der [[Relation (Mathematik)#Homogene Relationen|Diagonalen]] hinzufügt.

== Anschauliches Beispiel ==
[[Datei:TransitiveHuelleBeispiel.svg|mini|Illustration des Beispiels: durchgezogene Pfeile zeigen direkte Beziehungen an, gestrichelte Pfeile die in der transitiven Hülle dazu kommenden Beziehungen]]
Gegeben sei eine Relation „Direkter-Vorgesetzter“ mit folgenden Beziehungen:

* C ist direkter Vorgesetzter von D und E
* B ist direkter Vorgesetzter von C
* A ist direkter Vorgesetzter von B

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

* A ist Vorgesetzter von B, C, D, E
* B ist Vorgesetzter von C, D, E
* C ist Vorgesetzter von D und E

== Mathematische Definition ==
Die transitive Hülle <math>\operatorname{t}(R) \equiv R^{+}</math> einer zweistelligen Relation <math>R</math> auf einer [[Menge (Mathematik)|Menge]] <math>M</math> ist gegeben durch:
:<math>x \ \operatorname{t}(R) \ y : \Leftrightarrow 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</math><ref name="BinRelClosure" />

Die reflexive Hülle <math>\operatorname{r}(R) \equiv R^{?}</math> ist einfach die Vereinigung mit der Diagonalen (Identität), wodurch die Reflexivität erreicht wird:
:<math>x \ \operatorname{r}(R) \ y : \Leftrightarrow x \ R^{?} \ y : \Leftrightarrow x = y \lor x \ R \ y</math>, <ref>H. W. Lang: [https://www.inf.hs-flensburg.de/lang/algorithmen/grundlagen/menge.htm Mathematische Grundlagen: Menge, Relation, Abbildung], Hochschule Flensburg, 1997-2022, Abschnitt ''Relation'' </ref><ref name="BinRelClosure" />   d. h. <math>R^{?} = \mathrm I_M \cup R</math> (siehe [[Relation (Mathematik)#Homogene Relationen|Identitätsrelation]]).

Die reflexiv-transitive Hülle <math>R^{*}</math> ergibt sich dann durch
:<math>x \ R^{*} \ y : \Leftrightarrow x = y \lor x \ R^{+} \ y</math>

Ergänzung: Eine weitere Hüllenbildung dieser Art ist die symmetrische Hülle:
:<math>x \ \operatorname{s}(R) \ y : \Leftrightarrow x \ R^{\leftrightarrow} \ y : \Leftrightarrow x \ R \ y \ \lor \ y \ R \ x</math>, äquivalent zur Definition <math>\operatorname{s}(R) \equiv R^{\leftrightarrow} := R \cup R^-</math><ref>Notation <math>R^{\leftrightarrow}</math> wie in [https://proofwiki.org/wiki/Definition:Symmetric_Closure Symmetric Closure], auf: ProofWiki vom 12. September 2016</ref><ref>Kenneth Rosen: [https://www.cs.rutgers.edu/~elgammal/classes/cs205/chapt74.pdf Closures of Relations], Rutgers School of Arts and Sciences, Department of Computer Sciences (CS), Discrete Mathematics and Its Applications: Section 6.4, S. TP 2f. Die des Autors ist {{nowrap|<math>\operatorname{s}(R)</math>.}}</ref><ref name="BinRelClosure">Kenneth H. Rosen: {{Webarchiv |url=http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html |text=Closure of Binary Relation |wayback=20180821011923}}, in: CS381 Discrete Structures, [[Old Dominion University]], Norfolk, Virginia, 1999. Der Autor benutzt die Notationen {{nowrap|<math>\operatorname{t}(R)</math>,}} {{nowrap|<math>\operatorname{r}(R)</math>,}} {{nowrap|<math>\operatorname{s}(R)</math>.}}</ref> (siehe [[Relation (Mathematik)#Umkehrrelation|inverse Relation]]).

Zur Äquivalenzhülle siehe: [[Äquivalenzrelation#Erzeugung von Äquivalenzrelationen|Äquivalenzrelation §Äquivalenzhülle]].

== Beispiele ==
* Ist <math>R</math> gegeben durch die zwei [[Geordnetes Paar|Paare]] <math>(a,b)</math> und <math>(b,c)</math>, dann enthält <math>R^{+}</math> zusätzlich das Paar <math>(a,c)</math>. Für <math>R^{*}</math> kommen die weiteren Paare <math>(a,a)</math>, <math>(b,b)</math> und <math>(c,c)</math> dazu.
* Ist <math>R</math> die Nachfolgerrelation auf der Menge der [[Natürliche Zahl|natürlichen Zahlen]] (also <math>a \,R \,b : \Longleftrightarrow a = b + 1</math>), dann ergibt sich als transitive Hülle von <math>R</math> die Größer-Relation <math>>\ </math>. Die reflexiv-transitive Hülle ist die Größer-Gleich-Relation <math>\ge </math>.
* Die Relation <math>R</math> auf der Menge der 26 Buchstaben des [[Lateinisches Alphabet|lateinischen Alphabets]] sei gegeben durch <math>\alpha \,R \,\beta : \Longleftrightarrow </math> <math>\alpha\ </math> und <math>\beta\ </math> sind (in der gewöhnlichen Anordnung des Alphabets) direkt benachbart. Als transitive Hülle von <math>R</math> ergibt sich die [[Allrelation]], also die Relation, die alle Paare über der Grundmenge enthält (denn durch mehrfachen Übergang zu einem Nachbarn kann man von einem Buchstaben jeden beliebigen anderen Buchstaben erreichen). Da <math>R^{+}</math> bereits reflexiv ist, gilt hier <math>R^{*} = R^{+}</math>.

== Eigenschaften ==
* <math>R^{+}</math> ist die kleinste transitive Relation, die <math>R</math> enthält.
* <math>R^{*}</math> ist die kleinste reflexive und transitive Relation, die <math>R</math> enthält.
* Der Übergang zur transitiven Hülle ist ein [[Hüllenoperator]] im abstrakten Sinne. Das Gleiche gilt für die reflexiv-transitive Hülle.
* Die transitive Hülle einer Relation <math>R</math> auf einer Menge <math>M</math> ist die [[Schnittmenge]] aller transitiven [[Obermenge]]n von <math>R</math>, also
*: <math>R^{+} = \bigcap\{S \subseteq M \times M | S \ \mathrm{ist \ transitiv}, R \subseteq S \}</math>.
:Die Menge, über die hier der Durchschnitt gebildet wird, ist nicht leer, da sie stets die Allrelation <math>M \times M</math> enthält.
* Die analoge Aussage gilt für die reflexiv-transitive Hülle.
* Mit Hilfe der Potenzen bezüglich der [[Komposition (Mathematik)#Komposition von Relationen|Verkettung]] <math>\circ</math> von Relationen lassen sich die beiden Hüllen einer Relation <math>R</math> auch als (unendliche) [[Vereinigungsmenge|Vereinigung]] schreiben:
*: <math>R^{+} = R^1 \cup R^2 \cup R^3 \cup \dots</math>
*: <math>R^{*} = R^0 \cup R^1 \cup R^2 \cup \dots</math>
* Im Zusammenhang mit einer Relation <math>R</math> auf einer Menge <math>M</math> versteht man unter einem ''Weg'' eine endliche [[Folge (Mathematik)|Sequenz]] <math>c = (c_0, c_1, \dotsc, c_n)</math> von Elementen aus <math>M</math> mit <math>c_i\ R\ c_{i+1}</math> für alle <math>i</math> mit <math>0\leq i<n</math>. Die um 1 verminderte Länge der Sequenz <math>n \in \N_0</math> ist die Länge des Wegs. Der ''Weg'' führt vom Anfangspunkt <math>c_0</math> zum Endpunkt {{nowrap|<math>c_n</math>.}}<br />Die durch <math>R</math> erzeugte reflexiv-transitive Hülle <math>R^{*}</math> kann als Relation dadurch beschrieben werden, dass <math>a\ R^{*}\ b</math> genau dann gilt, wenn es einen ''Weg'' von <math>a</math> nach <math>b</math> gibt.<br />Analog gilt für die transitive Hülle <math>R^{+}</math>, dass <math>a\ R^{+}\ b</math> genau dann gilt, wenn es einen ''Weg'' von <math>a</math> nach <math>b</math> mit einer Länge größer 0 gibt.<ref>Siehe {{Ankerlink|Metz 2010|o|d|Relationen, Wege, Hüllen}}, S. 1. Im graphentheoretischen Sinn handelt es sich um einen [[Weg (Graphentheorie)#Weg|gerichteten Weg]] (ohne Kantengewichte) der gegebenen Länge.</ref>
* Es gibt endlich viele Elemente <math>c_0, c_1, \dotsc, c_n</math> mit <math>c_0=a</math>, <math>c_n=b</math> und für <math>0\leq i<n</math> jeweils <math>c_i\ R\ c_{i+1}</math> oder <math>c_{i+1}\ R\ c_i</math>.
* Für reflexive Relationen <math>R</math> gilt <math>R^{*} = R^{+}</math>. Allerdings kann es auch für [[irreflexiv]]e Relationen vorkommen, dass der transitive Abschluss bereits reflexiv ist.
* Für beliebige Relationen <math>R</math> ist <math>R^{*}</math> eine [[Quasiordnung]].
* Idempotenz der Hülloperatoren: <math>R^{+\!+} = R^{+}, R^{*\!*} = R^{*}, R^{?\!?} = R^{?}, R^{\leftrightarrow\leftrightarrow} = R^{\leftrightarrow}</math>.

== Anwendungen ==
In der [[Theoretische Informatik|Theoretischen Informatik]] werden [[Ableitung (Informatik)|Ableitungen]] in einer [[Formale Grammatik|formalen Grammatik]] als Folgen von Ableitungsschritten <math>v \Rightarrow w</math> definiert. Die Ableitbarkeit ist also der reflexiv-transitive Abschluss <math>\Rightarrow^{*}</math> der [[Transitionsrelation]] <math>\Rightarrow</math>.

== Transitive Reduktion ==
Das Gegenstück zur transitiven Hülle ist die transitive Reduktion.
Eine transitive Reduktion einer Relation <math>R</math> ist eine minimale Relation <math>R^\prime</math>, so dass <math>R^+ = (R^\prime)^+</math>, also eine minimale Relation mit derselben transitiven Hülle.<ref>Eric Weisstein: [https://mathworld.wolfram.com/TransitiveReduction.html Transitive Reduction], Wolfram Research: Wolfram MathWorld 1999-2018</ref>

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 [[Graph (Graphentheorie)|Graph]]en jedoch existiert die transitive Reduktion und ist eindeutig: {{nowrap|<math>R^\prime = R^+ \setminus (R^+)^2</math>.}} Das folgende Bild zeigt für diesen Fall Graphen, die einer nichttransitiven binären Relation (links) und ihrer transitiven Reduktion (rechts) entsprechen:<ref>Siehe [[:en:Transitive reduction|Transitive reduction]] (englisch)</ref>
<div class="center">
{|
| [[Datei:tred-G.svg|124px]]
| [[Datei:tred-Gprime.svg|80px]]
|}
</div>

Verwandte Begriffe:
* Reflexive Reduktion: Die reflexive Reduktion einer Relation <math>R</math> auf einer Menge <math>M</math> ist die minimale Relation <math>R^{\ne}</math>, mit derselben reflexiven Hülle. Das bedeutet, dass <math>a\; R^{\ne}\; b</math> äquivalent ist zu <math>a R b \land a \ne b</math> oder {{nowrap|<math>R^{\ne} = R \setminus \mathrm I_M</math>.}}<ref>Eric Weisstein: [https://mathworld.wolfram.com/ReflexiveReduction.html Reflexive Reduction], Wolfram Research: Wolfram MathWorld 1999-2018</ref><ref>Notation folgt [https://proofwiki.org/wiki/Definition:Reflexive_Reduction Definition:Reflexive Reduction], auf: ProofWiki vom 21. Februar 2018</ref>
* Es gibt kein vergleichbares Konzept einer symmetrischen Reduktion von Relationen, etwa die (symmetrische) Relation {{nowrap|<math>R \cap R^-</math>.}} <ref>[https://proofwiki.org/wiki/Definition:Symmetric_Closure#Note Symmetric Closure §Notes], auf: ProofWiki vom 12. September 2016</ref>

== Siehe auch ==
*[[Transitive Hülle (Menge)]]

== Weblinks ==
* [[Joost-Pieter Katoen]]: [https://www-i2.informatik.rwth-aachen.de/i2/fileadmin/user_upload/documents/DASAL10/lec18_handout.pdf Datenstrukturen und Algorithmen], RWTH Aachen, Lehrstuhl für Informatik 2, 6. Juli 2010 (abgerufen am 16. April 2018)
* Daniel Reinhold, Shenja Leiser: {{Webarchiv |url=http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf |text=Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation |wayback=20160306054010 |format=PDF; 236 KB}}, Humboldt-Universität Berlin, 6. Februar 2006 (abgerufen am 16. April 2018)
* {{Ankerlink|Metz 2010|d|o}} – Hans-Rudolf Metz: [https://homepages.thm.de/~hg8070/dm10/sk16.pdf Relationen, Wege, Hüllen], FH Gießen-Friedberg, Diskrete Mathematik (Informatik), SS 2010 – Skript 16, 2. Juni 2010 (abgerufen am 1. Mai 2018)
* Renate Winter: {{Webarchiv |url=http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf |text=Transitive Hülle einer Relation |wayback=20180929230622 |format=PDF; 36 KB}}, Universität Halle, Theoretische Informatik, WS 2010 (abgerufen am 16. April 2018)

== Einzelnachweise ==
<references />

{{SORTIERUNG:Transitive Hulle}}
[[Kategorie:Mengenlehre]]

Transitive Hülle (Relation) - Versionsgeschichte

imported>Graf Alge: Änderung 242443837 von MechJayTi rückgängig gemacht; war korrekt