Transitive Hülle (Relation)
(Weitergeleitet von Reflexiv-transitive Hülle)
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
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 <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: 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 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 Symmetric Closure, auf: ProofWiki vom 12. September 2016</ref><ref>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 {{#if:trim|<math>\operatorname{s}(R)</math>.}}</ref><ref name="BinRelClosure">Kenneth H. Rosen: <templatestyles src="Webarchiv/styles.css" />{{#if:20180821011923
| {{#ifeq: 20180821011923 | *
| {{#if: Closure of Binary Relation | {{#invoke:WLink|getEscapedTitle|Closure of Binary Relation}} | {{#invoke:Webarchiv|getdomain|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20180821011923}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Closure of Binary Relation | {{#invoke:WLink|getEscapedTitle|Closure of Binary Relation}} | {{#invoke:Webarchiv|getdomain|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20180821011923}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Closure of Binary Relation | {{#invoke:WLink|getEscapedTitle|Closure of Binary Relation}} | {{#invoke:Webarchiv|getdomain|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: Closure of Binary Relation | {{#invoke:WLink|getEscapedTitle|Closure of Binary Relation}} | {{#invoke:Webarchiv|getdomain|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Closure of Binary Relation | {{#invoke:WLink|getEscapedTitle|Closure of Binary Relation}} | {{#invoke:Webarchiv|getdomain|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Closure of Binary Relation | {{#invoke:WLink|getEscapedTitle|Closure of Binary Relation}} | {{#invoke:Webarchiv|getdomain|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20180821011923|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html}}
|| {{#if: || }}
}}{{#if: Closure of Binary Relation
| {{#if: {{#invoke:WLink|isBracketedLink|Closure of Binary Relation}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://www.cs.odu.edu/~cs381/cs381content/relation/closure/closure.html }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}}, in: CS381 Discrete Structures, Old Dominion University, Norfolk, Virginia, 1999. Der Autor benutzt die Notationen {{#if:trim|<math>\operatorname{t}(R)</math>,}} {{#if:trim|<math>\operatorname{r}(R)</math>,}} {{#if:trim|<math>\operatorname{s}(R)</math>.}}</ref> (siehe inverse Relation).
Zur Äquivalenzhülle siehe: Äquivalenzrelation §Äquivalenzhülle.
Beispiele
- Ist <math>R</math> gegeben durch die zwei 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ü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 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 Obermengen 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 Verkettung <math>\circ</math> von Relationen lassen sich die beiden Hüllen einer Relation <math>R</math> auch als (unendliche) 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 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 {{#if:trim|<math>c_n</math>.}}
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.
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 Metz 2010, S. 1. Im graphentheoretischen Sinn handelt es sich um einen 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 irreflexive 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 Theoretischen Informatik werden Ableitungen in einer 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: 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 Graphen jedoch existiert die transitive Reduktion und ist eindeutig: {{#if:trim|}} Das folgende Bild zeigt für diesen Fall Graphen, die einer nichttransitiven binären Relation (links) und ihrer transitiven Reduktion (rechts) entsprechen:<ref>Siehe Transitive reduction (englisch)</ref>
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 {{#if:trim|}}<ref>Eric Weisstein: Reflexive Reduction, Wolfram Research: Wolfram MathWorld 1999-2018</ref><ref>Notation folgt Definition:Reflexive Reduction, auf: ProofWiki vom 21. Februar 2018</ref>
- Es gibt kein vergleichbares Konzept einer symmetrischen Reduktion von Relationen, etwa die (symmetrische) Relation {{#if:trim|<math>R \cap R^-</math>.}} <ref>Symmetric Closure §Notes, auf: ProofWiki vom 12. September 2016</ref>
Siehe auch
Weblinks
- 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: <templatestyles src="Webarchiv/styles.css" />{{#if:20160306054010
| {{#ifeq: 20160306054010 | *
| {{#if: Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation | {{#invoke:WLink|getEscapedTitle|Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation}} | {{#invoke:Webarchiv|getdomain|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20160306054010}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation | {{#invoke:WLink|getEscapedTitle|Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation}} | {{#invoke:Webarchiv|getdomain|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20160306054010}} im Internet Archive{{#if: PDF; 236 KB | ; PDF; 236 KB }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation | {{#invoke:WLink|getEscapedTitle|Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation}} | {{#invoke:Webarchiv|getdomain|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: PDF; 236 KB | ; PDF; 236 KB }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation | {{#invoke:WLink|getEscapedTitle|Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation}} | {{#invoke:Webarchiv|getdomain|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: PDF; 236 KB | ; PDF; 236 KB }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation | {{#invoke:WLink|getEscapedTitle|Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation}} | {{#invoke:Webarchiv|getdomain|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: PDF; 236 KB | ; PDF; 236 KB }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation | {{#invoke:WLink|getEscapedTitle|Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation}} | {{#invoke:Webarchiv|getdomain|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20160306054010|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf}}
|| {{#if: || }}
}}{{#if: Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation
| {{#if: {{#invoke:WLink|isBracketedLink|Algorithmen zur Berechnung der Transitiven Hülle einer Datenbankrelation}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch: PDF; 236 KB
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/ws0506/se_graphen/Arbeiten/3_vortrag_leiser_reinhold.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}}, 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: <templatestyles src="Webarchiv/styles.css" />{{#if:20180929230622
| {{#ifeq: 20180929230622 | *
| {{#if: Transitive Hülle einer Relation | {{#invoke:WLink|getEscapedTitle|Transitive Hülle einer Relation}} | {{#invoke:Webarchiv|getdomain|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20180929230622}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Transitive Hülle einer Relation | {{#invoke:WLink|getEscapedTitle|Transitive Hülle einer Relation}} | {{#invoke:Webarchiv|getdomain|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20180929230622}} im Internet Archive{{#if: PDF; 36 KB | ; PDF; 36 KB }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Transitive Hülle einer Relation | {{#invoke:WLink|getEscapedTitle|Transitive Hülle einer Relation}} | {{#invoke:Webarchiv|getdomain|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: PDF; 36 KB | ; PDF; 36 KB }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: Transitive Hülle einer Relation | {{#invoke:WLink|getEscapedTitle|Transitive Hülle einer Relation}} | {{#invoke:Webarchiv|getdomain|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: PDF; 36 KB | ; PDF; 36 KB }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Transitive Hülle einer Relation | {{#invoke:WLink|getEscapedTitle|Transitive Hülle einer Relation}} | {{#invoke:Webarchiv|getdomain|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: PDF; 36 KB | ; PDF; 36 KB }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Transitive Hülle einer Relation | {{#invoke:WLink|getEscapedTitle|Transitive Hülle einer Relation}} | {{#invoke:Webarchiv|getdomain|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20180929230622|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf}}
|| {{#if: || }}
}}{{#if: Transitive Hülle einer Relation
| {{#if: {{#invoke:WLink|isBracketedLink|Transitive Hülle einer Relation}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch: PDF; 36 KB
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://nirvana.informatik.uni-halle.de/~theo/THEOlehre/Grundlagen/ws10/transitHuelle.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}}, Universität Halle, Theoretische Informatik, WS 2010 (abgerufen am 16. April 2018)
Einzelnachweise
<references />