www.wikidata.de-de.nina.az

Transitive Hülle Relation Die transitive Hülle bzw der transitive Abschluss einer zweistelligen Relation ist die kleinst

Transitive Hülle (Relation)

Die transitive Hülle bzw. der transitive Abschluss einer (zweistelligen) Relation ist die kleinste Erweiterung dieser Relation, die 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 Reflexivität noch fehlenden Paare auf der Diagonalen hinzufügt.

Anschauliches Beispiel Bearbeiten

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 Bearbeiten

Die transitive Hülle einer zweistelligen Relation auf einer Menge ist gegeben durch:

Die reflexive Hülle ist einfach die Vereinigung mit der Diagonalen (Identität), wodurch die Reflexivität erreicht wird:

Die reflexiv-transitive Hülle ergibt sich dann durch

Ergänzung: Eine weitere Hüllenbildung dieser Art ist die symmetrische Hülle:

Zur Äquivalenzhülle siehe: Äquivalenzrelation §Äquivalenzhülle.

Beispiele Bearbeiten

  • Ist gegeben durch die zwei Paare und , dann enthält zusätzlich das Paar . Für kommen die weiteren Paare , und dazu.
  • Ist die Nachfolgerrelation auf der Menge der natürlichen Zahlen (also ), dann ergibt sich als transitive Hülle von die Größer-Relation . Die reflexiv-transitive Hülle ist die Größer-Gleich-Relation .
  • Die Relation auf der Menge der 26 Buchstaben des lateinischen Alphabets sei gegeben durch und sind (in der gewöhnlichen Anordnung des Alphabets) direkt benachbart. Als transitive Hülle von 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 bereits reflexiv ist, gilt hier .

Eigenschaften Bearbeiten

  • ist die kleinste transitive Relation, die enthält.
  • ist die kleinste reflexive und transitive Relation, die 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 auf einer Menge ist die Schnittmenge aller transitiven Obermengen von , also
  • Die analoge Aussage gilt für die reflexiv-transitive Hülle.
  • Mit Hilfe der Potenzen bezüglich der Verkettung von Relationen lassen sich die beiden Hüllen einer Relation auch als (unendliche) Vereinigung schreiben:
  • Im Zusammenhang mit einer Relation auf einer Menge versteht man unter einem Weg eine endliche Sequenz von Elementen aus mit für alle mit . Die um 1 verminderte Länge der Sequenz ist die Länge des Wegs. Der Weg führt vom Anfangspunkt zum Endpunkt .
    Die durch erzeugte reflexiv-transitive Hülle kann als Relation dadurch beschrieben werden, dass genau dann gilt, wenn es einen Weg von nach gibt.
    Analog gilt für die transitive Hülle , dass genau dann gilt, wenn es einen Weg von nach mit einer Länge größer 0 gibt.
  • Es gibt endlich viele Elemente mit , und für jeweils oder .
  • Für reflexive Relationen gilt . Allerdings kann es auch für irreflexive Relationen vorkommen, dass der transitive Abschluss bereits reflexiv ist.
  • Für beliebige Relationen ist eine Quasiordnung.
  • Idempotenz der Hülloperatoren: .

Anwendungen Bearbeiten

In der Theoretischen Informatik werden Ableitungen in einer formalen Grammatik als Folgen von Ableitungsschritten definiert. Die Ableitbarkeit ist also der reflexiv-transitive Abschluss der Transitionsrelation .

Transitive Reduktion Bearbeiten

Das Gegenstück zur transitiven Hülle ist die transitive Reduktion. Eine transitive Reduktion einer Relation ist eine minimale Relation , so dass , 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: . Das folgende Bild zeigt für diesen Fall Graphen, die einer nichttransitiven binären Relation (links) und ihrer transitiven Reduktion (rechts) entsprechen:


Verwandte Begriffe:

  • Reflexive Reduktion: Die reflexive Reduktion einer Relation auf einer Menge ist die minimale Relation , mit derselben reflexiven Hülle. Das bedeutet, dass äquivalent ist zu oder .
  • Es gibt kein vergleichbares Konzept einer symmetrischen Reduktion von Relationen, etwa die (symmetrische) Relation . 

Siehe auch Bearbeiten

Weblinks Bearbeiten

  • Joost-Pieter Katoen: Datenstrukturen und Algorithmen, RWTH Aachen, Lehrstuhl für Informatik 2, 6. Juli 2010 (abgerufen am 16. April 2018)
  • Daniel Reinhold, Shenja Leiser: (Memento vom 6. März 2016 im Internet Archive; PDF; 236 KB), Humboldt-Universität Berlin, 6. Februar 2006 (abgerufen am 16. April 2018)
  • Metz 2010 – Hans-Rudolf Metz: 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: (Memento vom 29. September 2018 im Internet Archive; PDF; 36 KB), Universität Halle, Theoretische Informatik, WS 2010 (abgerufen am 16. April 2018)

Einzelnachweise Bearbeiten

  1. ↑ Kenneth H. Rosen: (Memento vom 21. August 2018 im Internet Archive), in: CS381 Discrete Structures, Old Dominion University, Norfolk, Virginia, 1999. Der Autor benutzt die Notationen , , .
  2. H. W. Lang: Mathematische Grundlagen: Menge, Relation, Abbildung, Hochschule Flensburg, 1997-2022, Abschnitt Relation
  3. Notation wie in Symmetric Closure, auf: ProofWiki vom 12. September 2016
  4. Kenneth Rosen: 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 .
  5. Siehe Metz 2010, S. 1. Im graphentheoretischen Sinn handelt es sich um einen gerichteten Weg (ohne Kantengewichte) der gegebenen Länge.
  6. Eric Weisstein: Transitive Reduction, Wolfram Research: Wolfram MathWorld 1999-2018
  7. Siehe Transitive reduction (englisch)
  8. Eric Weisstein: Reflexive Reduction, Wolfram Research: Wolfram MathWorld 1999-2018
  9. Notation folgt Definition:Reflexive Reduction, auf: ProofWiki vom 21. Februar 2018
  10. Symmetric Closure §Notes, auf: ProofWiki vom 12. September 2016
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die transitive Hulle bzw der transitive Abschluss einer zweistelligen Relation ist die kleinste Erweiterung dieser Relation die transitiv ist Sie kann mit dem Floyd Warshall Algorithmus berechnet werden Die reflexiv transitive Hulle bzw den reflexiv transitiven Abschluss der Relation erhalt man indem man zur transitiven Hulle die fur Reflexivitat noch fehlenden Paare auf der Diagonalen hinzufugt Inhaltsverzeichnis 1 Anschauliches Beispiel 2 Mathematische Definition 3 Beispiele 4 Eigenschaften 5 Anwendungen 6 Transitive Reduktion 7 Siehe auch 8 Weblinks 9 EinzelnachweiseAnschauliches Beispiel Bearbeiten nbsp Illustration des Beispiels durchgezogene Pfeile zeigen direkte Beziehungen an gestrichelte Pfeile die in der transitiven Hulle dazu kommenden BeziehungenGegeben 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 BDie transitive Hulle dieser Relation enthalt nun zusatzlich 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 EMathematische Definition BearbeitenDie transitive Hulle t R R displaystyle operatorname t R equiv R nbsp einer zweistelligen Relation R displaystyle R nbsp auf einer Menge M displaystyle M nbsp ist gegeben durch x t R y x R y n 0 x 1 x n M x R x 1 R x 2 R R x n R y displaystyle 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 nbsp 1 Die reflexive Hulle r R R displaystyle operatorname r R equiv R nbsp ist einfach die Vereinigung mit der Diagonalen Identitat wodurch die Reflexivitat erreicht wird x r R y x R y x y x R y displaystyle x operatorname r R y Leftrightarrow x R y Leftrightarrow x y lor x R y nbsp 2 1 d h R I M R displaystyle R mathrm I M cup R nbsp siehe Identitatsrelation Die reflexiv transitive Hulle R displaystyle R nbsp ergibt sich dann durch x R y x y x R y displaystyle x R y Leftrightarrow x y lor x R y nbsp Erganzung Eine weitere Hullenbildung dieser Art ist die symmetrische Hulle x s R y x R y x R y y R x displaystyle x operatorname s R y Leftrightarrow x R leftrightarrow y Leftrightarrow x R y lor y R x nbsp aquivalent zur Definition s R R R R displaystyle operatorname s R equiv R leftrightarrow R cup R nbsp 3 4 1 siehe inverse Relation Zur Aquivalenzhulle siehe Aquivalenzrelation Aquivalenzhulle Beispiele BearbeitenIst R displaystyle R nbsp gegeben durch die zwei Paare a b displaystyle a b nbsp und b c displaystyle b c nbsp dann enthalt R displaystyle R nbsp zusatzlich das Paar a c displaystyle a c nbsp Fur R displaystyle R nbsp kommen die weiteren Paare a a displaystyle a a nbsp b b displaystyle b b nbsp und c c displaystyle c c nbsp dazu Ist R displaystyle R nbsp die Nachfolgerrelation auf der Menge der naturlichen Zahlen also a R b a b 1 displaystyle a R b Longleftrightarrow a b 1 nbsp dann ergibt sich als transitive Hulle von R displaystyle R nbsp die Grosser Relation gt displaystyle gt nbsp Die reflexiv transitive Hulle ist die Grosser Gleich Relation displaystyle geq nbsp Die Relation R displaystyle R nbsp auf der Menge der 26 Buchstaben des lateinischen Alphabets sei gegeben durch a R b displaystyle alpha R beta Longleftrightarrow nbsp a displaystyle alpha nbsp und b displaystyle beta nbsp sind in der gewohnlichen Anordnung des Alphabets direkt benachbart Als transitive Hulle von R displaystyle R nbsp ergibt sich die Allrelation also die Relation die alle Paare uber der Grundmenge enthalt denn durch mehrfachen Ubergang zu einem Nachbarn kann man von einem Buchstaben jeden beliebigen anderen Buchstaben erreichen Da R displaystyle R nbsp bereits reflexiv ist gilt hier R R displaystyle R R nbsp Eigenschaften BearbeitenR displaystyle R nbsp ist die kleinste transitive Relation die R displaystyle R nbsp enthalt R displaystyle R nbsp ist die kleinste reflexive und transitive Relation die R displaystyle R nbsp enthalt Der Ubergang zur transitiven Hulle ist ein Hullenoperator im abstrakten Sinne Das Gleiche gilt fur die reflexiv transitive Hulle Die transitive Hulle einer Relation R displaystyle R nbsp auf einer Menge M displaystyle M nbsp ist die Schnittmenge aller transitiven Obermengen von R displaystyle R nbsp also R S M M S i s t t r a n s i t i v R S displaystyle R bigcap S subseteq M times M S mathrm ist transitiv R subseteq S nbsp Die Menge uber die hier der Durchschnitt gebildet wird ist nicht leer da sie stets die Allrelation M M displaystyle M times M nbsp enthalt Die analoge Aussage gilt fur die reflexiv transitive Hulle Mit Hilfe der Potenzen bezuglich der Verkettung displaystyle circ nbsp von Relationen lassen sich die beiden Hullen einer Relation R displaystyle R nbsp auch als unendliche Vereinigung schreiben R R 1 R 2 R 3 displaystyle R R 1 cup R 2 cup R 3 cup dots nbsp R R 0 R 1 R 2 displaystyle R R 0 cup R 1 cup R 2 cup dots nbsp Im Zusammenhang mit einer Relation R displaystyle R nbsp auf einer Menge M displaystyle M nbsp versteht man unter einem Weg eine endliche Sequenz c c 0 c 1 c n displaystyle c c 0 c 1 dotsc c n nbsp von Elementen aus M displaystyle M nbsp mit c i R c i 1 displaystyle c i R c i 1 nbsp fur alle i displaystyle i nbsp mit 0 i lt n displaystyle 0 leq i lt n nbsp Die um 1 verminderte Lange der Sequenz n N 0 displaystyle n in mathbb N 0 nbsp ist die Lange des Wegs Der Weg fuhrt vom Anfangspunkt c 0 displaystyle c 0 nbsp zum Endpunkt c n displaystyle c n nbsp Die durch R displaystyle R nbsp erzeugte reflexiv transitive Hulle R displaystyle R nbsp kann als Relation dadurch beschrieben werden dass a R b displaystyle a R b nbsp genau dann gilt wenn es einen Weg von a displaystyle a nbsp nach b displaystyle b nbsp gibt Analog gilt fur die transitive Hulle R displaystyle R nbsp dass a R b displaystyle a R b nbsp genau dann gilt wenn es einen Weg von a displaystyle a nbsp nach b displaystyle b nbsp mit einer Lange grosser 0 gibt 5 Es gibt endlich viele Elemente c 0 c 1 c n displaystyle c 0 c 1 dotsc c n nbsp mit c 0 a displaystyle c 0 a nbsp c n b displaystyle c n b nbsp und fur 0 i lt n displaystyle 0 leq i lt n nbsp jeweils c i R c i 1 displaystyle c i R c i 1 nbsp oder c i 1 R c i displaystyle c i 1 R c i nbsp Fur reflexive Relationen R displaystyle R nbsp gilt R R displaystyle R R nbsp Allerdings kann es auch fur irreflexive Relationen vorkommen dass der transitive Abschluss bereits reflexiv ist Fur beliebige Relationen R displaystyle R nbsp ist R displaystyle R nbsp eine Quasiordnung Idempotenz der Hulloperatoren R R R R R R R R displaystyle R R R R R R R leftrightarrow leftrightarrow R leftrightarrow nbsp Anwendungen BearbeitenIn der Theoretischen Informatik werden Ableitungen in einer formalen Grammatik als Folgen von Ableitungsschritten v w displaystyle v Rightarrow w nbsp definiert Die Ableitbarkeit ist also der reflexiv transitive Abschluss displaystyle Rightarrow nbsp der Transitionsrelation displaystyle Rightarrow nbsp Transitive Reduktion BearbeitenDas Gegenstuck zur transitiven Hulle ist die transitive Reduktion Eine transitive Reduktion einer Relation R displaystyle R nbsp ist eine minimale Relation R displaystyle R prime nbsp so dass R R displaystyle R R prime nbsp also eine minimale Relation mit derselben transitiven Hulle 6 Es gibt sowohl Relationen fur die keine transitive Reduktion existiert als auch solche fur die mehrere unterschiedliche transitive Reduktionen existieren Fur gerichtete endliche azyklische Graphen jedoch existiert die transitive Reduktion und ist eindeutig R R R 2 displaystyle R prime R setminus R 2 nbsp Das folgende Bild zeigt fur diesen Fall Graphen die einer nichttransitiven binaren Relation links und ihrer transitiven Reduktion rechts entsprechen 7 nbsp nbsp Verwandte Begriffe Reflexive Reduktion Die reflexive Reduktion einer Relation R displaystyle R nbsp auf einer Menge M displaystyle M nbsp ist die minimale Relation R displaystyle R neq nbsp mit derselben reflexiven Hulle Das bedeutet dass a R b displaystyle a R neq b nbsp aquivalent ist zu a R b a b displaystyle aRb land a neq b nbsp oder R R I M displaystyle R neq R setminus mathrm I M nbsp 8 9 Es gibt kein vergleichbares Konzept einer symmetrischen Reduktion von Relationen etwa die symmetrische Relation R R displaystyle R cap R nbsp 10 Siehe auch BearbeitenTransitive Hulle Menge Weblinks BearbeitenJoost Pieter Katoen Datenstrukturen und Algorithmen RWTH Aachen Lehrstuhl fur Informatik 2 6 Juli 2010 abgerufen am 16 April 2018 Daniel Reinhold Shenja Leiser Algorithmen zur Berechnung der Transitiven Hulle einer Datenbankrelation Memento vom 6 Marz 2016 im Internet Archive PDF 236 KB Humboldt Universitat Berlin 6 Februar 2006 abgerufen am 16 April 2018 Metz 2010 Hans Rudolf Metz Relationen Wege Hullen FH Giessen Friedberg Diskrete Mathematik Informatik SS 2010 Skript 16 2 Juni 2010 abgerufen am 1 Mai 2018 Renate Winter Transitive Hulle einer Relation Memento vom 29 September 2018 im Internet Archive PDF 36 KB Universitat Halle Theoretische Informatik WS 2010 abgerufen am 16 April 2018 Einzelnachweise Bearbeiten a b c Kenneth H Rosen Closure of Binary Relation Memento vom 21 August 2018 im Internet Archive in CS381 Discrete Structures Old Dominion University Norfolk Virginia 1999 Der Autor benutzt die Notationen t R displaystyle operatorname t R nbsp r R displaystyle operatorname r R nbsp s R displaystyle operatorname s R nbsp H W Lang Mathematische Grundlagen Menge Relation Abbildung Hochschule Flensburg 1997 2022 Abschnitt Relation Notation R displaystyle R leftrightarrow nbsp wie in Symmetric Closure auf ProofWiki vom 12 September 2016 Kenneth Rosen 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 s R displaystyle operatorname s R nbsp Siehe Metz 2010 S 1 Im graphentheoretischen Sinn handelt es sich um einen gerichteten Weg ohne Kantengewichte der gegebenen Lange Eric Weisstein Transitive Reduction Wolfram Research Wolfram MathWorld 1999 2018 Siehe Transitive reduction englisch Eric Weisstein Reflexive Reduction Wolfram Research Wolfram MathWorld 1999 2018 Notation folgt Definition Reflexive Reduction auf ProofWiki vom 21 Februar 2018 Symmetric Closure Notes auf ProofWiki vom 12 September 2016 Abgerufen von https de wikipedia org w index php title Transitive Hulle Relation amp oldid 239269428