Transitieve afsluiting

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De transitieve afsluiting (Nederland) of transitieve sluiting (Vlaanderen) R^{+} van een binaire relatie R op een verzameling M is de kleinste transitieve relatie op M die de oorspronkelijke relatie omvat.

Dit wil zeggen dat voor twee elementen x en y uit M geldt dat x \ R^{+} \ y slechts bestaat als er een rij elementen x_0 \, x_1 \, \dots x_n bestaat waarbij:  x_0 = x, x_n = y en  x_i \ R \ x_{i+1} voor  0 \leq i < n.

Elke binaire relatie heeft een transitieve sluiting.

Als men de relaties voorstelt als een gerichte graaf, bevat de graaf van de transitieve sluiting R^{+} een boog van knoop x naar knoop y als de graaf van R 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 strikte partiële orde op de verzameling knopen.

Voorbeelden[bewerken]

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".
  • 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.
  • In de verzameling van natuurlijke getallen is de transitieve sluiting van de relatie a \,R \,b : \Longleftrightarrow a = b + 1 ("a volgt op b") de relatie "is groter dan".

Berekenen van de transitieve sluiting[bewerken]

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 programmeringsmethode. 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 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[bewerken]

"Bereikbaarheid" is een belangrijk concept bij het bevragen van databases, die een al dan niet hiërarchisch netwerk voorstellen, bijvoorbeeld een ontologie, een sociaal netwerk, een citatie-index van wetenschappelijke publicaties of een database van hyperlinks uit het World Wide Web. Hiervoor is het concept van transitieve sluiting een bruikbaar hulpmiddel.

Transitieve reductie[bewerken]

De transitieve reductie is de tegenhanger van de transitieve sluiting. De transitieve reductie van een binaire relatie R is de kleinste relatie die dezelfde transitieve sluiting heeft als R.

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.