Transitieve afsluiting: verschil tussen versies

De '''transitieve afsluiting''' (Nederland) of '''transitieve sluiting''' (Vlaanderen) <math>R^{+}</math> van een [[tweeplaatsige 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 (wiskunde)|relatie]] omvat. Deze kleinste relatie <math>R^{+}</math> bestaat altijd, deze kan namelijk als volgt worden geconstrueerd:

:<math>x \ RxR^{+} \ y </math> als en slechts als er een rij elementen <math>x_0=x ,\, x_1, \, \dotsldots,\, x_n=y</math> bestaat met <math>n\geqge 1</math> bestaat waarbij <math> x_0 = x</math>, <math>x_n = y</math> en <math> x_i \ R \ x_x_iRx_{i+1}</math> voor <math> 0 \leqle i < n</math>

Als men de relaties voorstelt als een [[Grafentheorie#Gerichte grafen|gerichte graaf]], bevat de graaf van de transitieve sluitingafsluiting <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 een of meer bogen bevat van <math>x</math> naar <math>y</math>. De transitieve sluitingafsluiting van een gerichte, acyclische graaf is de graaf, die aangeeft welke [[Knooppunt (wiskunde)|knooppunten]] vanuit andere knopen zijn te bereiken.

[[Afbeelding:TransitiveHuelleBeispiel.svg|thumbminiatuur|In dit voorbeeld wordt de oorspronkelijke relatie voorgesteld met volle pijlen. De pijlen in streepjeslijn komen er in de transitieve afsluiting bij.]]

* De relatie tussen superieuren en ondergeschikten in een [[organisatie]] heeft als transitieve sluitingafsluiting de relatie, die tussenvan twee medewerkers bepaalt, wie de hoogste functie heeft.

* Het routenetwerk van een luchtvaartmaatschappij verbindt de steden waartussen er een directe vlucht is. De transitieve sluitingafsluiting hiervan verbindt die steden waartussen men met ééneen of meer op elkaar aansluitende vluchten kan vliegen.

* In de verzameling van [[natuurlijkNatuurlijk getal|natuurlijke getallen]] is de transitieve sluitingafsluiting van de relatie <math>a \,R</math> \,bbepaald :door \Longleftrightarrow<math>aRb</math> als <math>a = b + 1</math>, dus vand.w.z. <math>a</math> volgt op <math>b</math>, de relatie die van twee getallen bepaalt welke de grootste is.

* De bereikbaarheid van de [[gegeven]]s is de essentiële maat voor de toegankelijkheid van [[database]]s, die een al dan niet hiërarchisch netwerk voorstellen, bijvoorbeeldzoals een [[Ontologie (informatica)|ontologie]], een [[sociaal netwerk]], een [[citatie-index]] van wetenschappelijke publicaties of een database van [[hyperlink]]s uit het [[wereldwijdWereldwijd web|wereldwijde web]]. Hiervoor is het concept van transitieve sluitingafsluiting een bruikbaar hulpmiddel.

De transitieve sluitingafsluiting 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. 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 [[bogenmatrix]], in plaats van het optellen van afstanden gebruikt men de [[logische conjunctie]] EN, en in plaats van het minimum de [[logische disjunctie]] OF.

De transitieve reductie is de tegenhanger van de transitieve sluitingafsluiting. De transitieve reductie van een tweeplaatsige relatie <math>R</math> is de kleinste relatie die dezelfde transitieve sluitingafsluiting heeft als <math>R</math>. Er bestaan relaties waarvoor er geen transitieve reductie bestaat, er zijn relaties waarvoor er verschillende transitieve reducties bestaan, maar als de relatie eindig en acyclisch is, bestaat er steeds één unieke transitieve reductie.