Wikipedia

Transitieve afsluiting: verschil tussen versies

Artikel Overleg

Transitieve afsluiting (bewerken)

Versie van 24 mrt 2022 21:42

257 bytes verwijderd ,  3 maanden geleden
geen bewerkingssamenvatting
k (Robot: Verplaatsing van 12 interwikilinks. Deze staan nu op Wikidata onder d:q1501387)
Geen bewerkingssamenvatting
De '''transitieve afsluiting''' (Nederland) of '''transitieve sluiting''' (Vlaanderen) <math>R^{+}</math> van een [[binairetweeplaatsige relatie]] <math>R</math> op een [[verzamelingVerzameling (wiskunde)|verzameling]] <math>M</math> is de kleinste [[transitiviteitTransitiviteit (wiskunde)|transitieve]] relatie op <math>M</math> die de oorspronkelijke [[Relatie (wiskunde)|relatie]] omvat. Dat 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>. Iedere tweeplaatsige relatie heeft een transitieve sluiting.
 
Als men de relaties voorstelt als een [[grafentheorieGrafentheorie#Gerichte grafen|gerichte graaf]], bevat de graaf van de transitieve sluiting <math>R^{+}</math> een boog van knoop ''<math>x''</math> naar knoop ''<math>y''</math> als de graaf van <math>R</math> een gericht pad met ééneen of meer bogen bevat van ''<math>x''</math> naar ''<math>y''</math>. De transitieve sluiting van een gerichte, acyclische graaf is de "bereikbaarheidsgraaf"graaf, die aangeeft welke knopen[[Knooppunt bereikbaar zijn(wiskunde)|knooppunten]] vanuit andere knopen zijn te bereiken. Het is een [[partiëlePartiële orde#Strikte partiële orde|strikte partiële orde]] op de verzameling knopenknooppunten.▼
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>.
 
== Voorbeelden ==▼
Elke binaire relatie heeft een transitieve sluiting.
[[BestandAfbeelding:TransitiveHuelleBeispiel.svg|thumb|In dit voorbeeld wordt de oorspronkelijke relatie voorgesteld met volle pijlen. De pijlen in streepjeslijn komen erbijer in de transitieve afsluiting bij.]]▼
 
* De relatie "istussen desuperieuren baasen van"ondergeschikten in een [[organisatie]] heeft als transitieve sluiting de relatie, "isdie eentussen hiërarchischetwee overstemedewerkers van"bepaalt, wie de hoogste functie heeft.▼
▲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''. De transitieve sluiting van een gerichte, acyclische graaf is de "bereikbaarheidsgraaf" die aangeeft welke knopen bereikbaar zijn vanuit andere knopen. Het is een [[partiële orde#Strikte partiële orde|strikte partiële orde]] op de verzameling knopen.
 
* Het routenetwerk van een luchtvaartmaatschappij verbindt de steden waartussen er een directe vlucht is. De transitieve sluiting hiervan verbindt die steden waartussen men met één of meer op elkaar aansluitende vluchten kan vliegen.▼
▲==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
 
* In de verzameling van [[natuurlijk getal|natuurlijke getallen]] is de transitieve sluiting van de relatie <math>a \,R \,b : \Longleftrightarrow a = b + 1</math>, ("dus van <math>a</math> volgt op <math>b")</math> de relatie "isdie grotervan dan"twee getallen bepaalt welke de grootste is.▼
: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.
 
"Bereikbaarheid"* De bereikbaarheid van de [[gegeven]]s is eende belangrijkessentiële conceptmaat bijvoor hetde bevragentoegankelijkheid van [[database]]s, die een al dan niet hiërarchisch netwerk voorstellen, bijvoorbeeld een [[Ontologie (informatica)|ontologie]], een [[sociaal netwerk]], een [[citatie-index]] van wetenschappelijke publicaties of een database van [[hyperlink]]s uit het [[World Widewereldwijd Webweb]]. Hiervoor is het concept van transitieve sluiting een bruikbaar hulpmiddel.▼
▲*De relatie "is de baas van" in een organisatie heeft als transitieve sluiting de relatie "is een hiërarchische overste van".
 
== Berekening ==
▲*Het routenetwerk van een luchtvaartmaatschappij verbindt de steden waartussen er een directe vlucht is. De transitieve sluiting hiervan verbindt die steden waartussen men met één of meer op elkaar aansluitende vluchten kan vliegen.
De transitieve sluiting van een relatie of graaf kan men bepalen met behulp van het algoritme van Warshall, dat een speciaal geval is van het [[Floyd-Warshall-algoritme]]. Dit algoritme bepaalt met dynamische programmering de kortste afstand tussen alle knopenparen in een gewogen gerichte graaf met een [[dynamische programmering]]smethode. In het algoritme van Warshall beschouwt men een niet-gewogen gerichte graaf;, men kan ook zeggen dat alle bogen een gewicht hebben dat gelijk is aan 1. Men werkt dan met de [[binaire matrix|binaire]] [[bogenmatrix]];, in plaats van het optellen van afstanden gebruikt men de [[logische conjunctie]] EN en in plaats van het minimum de [[logische disjunctie]] OF.▼
 
== Transitieve reductie ==▼
▲*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".
De transitieve reductie is de tegenhanger van de transitieve sluiting. De transitieve reductie van een tweeplaatsige 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 meerdereverschillende transitieve reducties bestaan. Als de graaf van de relatie een gerichte, acyclische graaf is, bestaat er evenwel steeds één unieke transitieve reductie.▼
 
==Berekenen van de transitieve sluiting==
▲De transitieve sluiting van een relatie of graaf kan men bepalen met behulp van het algoritme van Warshall, dat een speciaal geval is van het [[Floyd-Warshall-algoritme]]. Dit algoritme bepaalt de kortste afstand tussen alle knopenparen in een gewogen gerichte graaf met een [[dynamische programmering]]smethode. In het algoritme van Warshall beschouwt men een niet-gewogen gerichte graaf; men kan ook zeggen dat alle bogen een gewicht hebben dat gelijk is aan 1. Men werkt dan met de [[binaire matrix|binaire]] [[bogenmatrix]]; in plaats van het optellen van afstanden gebruikt men de [[logische conjunctie]] EN en in plaats van het minimum de [[logische disjunctie]] OF.
 
==Toepassing==
▲"Bereikbaarheid" is een belangrijk concept bij het bevragen van [[database]]s, die een al dan niet hiërarchisch netwerk voorstellen, bijvoorbeeld een [[Ontologie (informatica)|ontologie]], een [[sociaal netwerk]], een [[citatie-index]] van wetenschappelijke publicaties of een database van [[hyperlink]]s uit het [[World Wide Web]]. Hiervoor is het concept van transitieve sluiting een bruikbaar hulpmiddel.
 
▲==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]]
Overgenomen van "https://nl.wikipedia.org/wiki/Speciaal:MobielVerschillen/61394952"