Transitieve afsluiting: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
wiskundig begrip |
|||
Regel 1:
De '''transitieve afsluiting''' <math>R^{+}</math> van een [[binaire relatie]] <math>R</math> op een [[verzameling (wiskunde)|verzameling]] <math>M</math> is de kleinste [[transitiviteit (wiskunde)|transitieve]] relatie op <math>M</math> die de oorspronkelijke relatie omvat.
Dit wil zeggen dat voor twee elementen <math>x</math> en <math>y</math> uit <math>M</math> geldt dat <math>x \ R^{+} \ y </math> slechts bestaat als er een rij elementen <math>x_0 \, x_1 \, \dots x_n</math> bestaat waarbij:
<math> x_0 = x</math>,
<math>x_n = y</math> en
<math> x_i \ R \ x_{i+1}</math> voor <math> 0 \leq i < n</math>.
Als men de relaties voorstelt als een [[grafentheorie#Gerichte grafen|gerichte graaf]], bevat de graaf van de transitieve sluiting <math>R{+}</math> een boog van knoop ''x'' naar knoop ''y'' als de graaf van <math>R</math> een gericht pad met één of meer bogen bevat van ''x'' naar ''y''.
==Voorbeelden==
[[Bestand:TransitiveHuelleBeispiel.svg|thumb|In dit voorbeeld wordt de oorspronkelijke relatie voorgesteld met volle pijlen. De pijlen in streepjeslijn komen erbij in de transitieve afsluiting.]]
*In een verzameling mensen kan men de relatie "is vader van" beschouwen. Daartoe kunnen bijvoorbeeld behoren:
**A is vader van B
**B is vader van C
**C is vader van D en E
:De transitieve sluiting van deze relatie "is vader van" kan men aanduiden als "is mannelijke voorouder van" of "is voorvader van". Ze omvat naast de reeds genoemde verbanden nog de volgende: A is voorvader van C, D en E; B is voorvader van D en E.
*De relatie "is de baas van" in een organisatie heeft als transitieve sluiting de relatie "is een hiërarchische overste van".
*In de verzameling van [[natuurlijk getal|natuurlijke getallen]] is de transitieve sluiting van de relatie <math>a \,R \,b : \Longleftrightarrow a = b + 1</math> ("a volgt op b") de relatie "is groter dan".
==Transitieve reductie==
De '''transitieve reductie''' is de tegenhanger van de transitieve sluiting. De transitieve reductie van een binaire relatie <math>R</math> is de kleinste relatie die dezelfde transitieve sluiting heeft als <math>R</math>.
Er bestaan relaties waarvoor er geen transitieve reductie bestaat. Er zijn ook relaties waarvoor er meerdere transitieve reducties bestaan. Als de graaf van de relatie een gerichte, acyclische graaf is, bestaat er evenwel steeds één unieke transitieve reductie.
[[Categorie:Algebra]]
[[Categorie:Verzamelingenleer]]
[[fr:Fermeture transitive]]
[[cs:Tranzitivní uzávěr]]
[[en:Transitive closure]]
[[es:Clausura transitiva]]
[[eu:Itxitura iragankor]]
[[de:Transitive Hülle]]
[[ja:推移閉包]]
[[pl:Domknięcie przechodnie]]
[[ru:Транзитивное замыкание]]
[[sr:Транзитивно затворење]]
[[uk:Транзитивне замикання]]
[[zh:传递闭包]]
| |||