Transitieve afsluiting

De transitieve afsluiting (Nederland) of transitieve sluiting (Vlaanderen) $R^{+}$ van een tweeplaatsige relatie $R$ op een verzameling $M$ is de kleinste transitieve relatie op $M$ die de oorspronkelijke relatie omvat. Deze kleinste relatie $R^{+}$ bestaat altijd, deze kan namelijk als volgt worden geconstrueerd:

$x\ R^{+}\ y$ als en slechts als er een rij elementen $x_{0}\,x_{1}\,\dots x_{n}$ met $n\geq 1$ bestaat waarbij $x_{0}=x$, $x_{n}=y$ en $x_{i}\ R\ x_{i+1}$ voor $0\leq i<n$

Deze vorm van afsluiting, gedefinieerd voor tweeplaatsige relaties, komt overeen met de definitie van afsluiting, gedefinieerd voor verzamelingen.

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 een of meer bogen bevat van $x$ naar $y$. De transitieve sluiting van een gerichte, acyclische graaf is de graaf, die aangeeft welke knooppunten vanuit andere knopen zijn te bereiken.

Voorbeelden

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 sluiting de relatie, die tussen twee medewerkers bepaalt, wie de hoogste functie heeft.

• 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$, dus van $a$ volgt op $b$ de relatie die van twee getallen bepaalt welke de grootste is.

• De bereikbaarheid van de gegevens is de essentiële maat voor de toegankelijkheid 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 wereldwijd web. Hiervoor is het concept van transitieve sluiting een bruikbaar hulpmiddel.

Berekening

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. 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.

Transitieve reductie

De transitieve reductie is de tegenhanger van de transitieve sluiting. De transitieve reductie van een tweeplaatsige relatie $R$ is de kleinste relatie die dezelfde transitieve sluiting heeft als $R$. Er bestaan relaties waarvoor er geen transitieve reductie bestaat, er zijn relaties waarvoor er verschillende transitieve reducties bestaan, maar als de graaf van de relatie een gerichte, acyclische graaf is, bestaat er evenwel steeds één unieke transitieve reductie. Een graaf met de transitieve reductie van een relatie heet het hasse-diagram van die relatie.