Transitieve afsluiting

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

${\displaystyle xR^{+}y}$ als er een rij elementen ${\displaystyle x_{0}=x,\,x_{1},\,\ldots ,\,x_{n}=y}$ bestaat met ${\displaystyle n\geq 1}$ en ${\displaystyle x_{i}Rx_{i+1}}$ voor ${\displaystyle 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 afsluiting ${\displaystyle R^{+}}$ een boog van knoop ${\displaystyle x}$ naar knoop ${\displaystyle y}$ als de graaf van ${\displaystyle R}$ een gericht pad met een of meer bogen bevat van ${\displaystyle x}$ naar ${\displaystyle y}$. De transitieve afsluiting van een gerichte, acyclische graaf is de graaf, die aangeeft welke knooppunten vanuit andere knopen zijn te bereiken.

De reflexief-transitieve afsluiting van iedere homogene tweeplaatsige relatie is een preorde.

• De relatie tussen superieuren en ondergeschikten in een organisatie heeft als transitieve afsluiting de relatie die van twee medewerkers bepaalt wie de hoogste functie heeft.

• Het routenetwerk van een luchtvaartmaatschappij verbindt de steden waartussen een directe vlucht is. De transitieve afsluiting hiervan verbindt die steden waartussen men met een of meer op elkaar aansluitende vluchten kan vliegen.

• In de verzameling natuurlijke getallen is de transitieve afsluiting van de relatie ${\displaystyle R}$ bepaald door ${\displaystyle aRb}$ als ${\displaystyle a=b+1}$, d.w.z. ${\displaystyle a}$ volgt op ${\displaystyle 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, zoals een ontologie, een sociaal netwerk, een citatie-index van wetenschappelijke publicaties of een database van hyperlinks uit het wereldwijde web. Hiervoor is het concept van transitieve afsluiting een bruikbaar hulpmiddel.

De transitieve afsluiting 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 afsluiting. De transitieve reductie van een tweeplaatsige relatie ${\displaystyle R}$ is de kleinste relatie die dezelfde transitieve afsluiting heeft als ${\displaystyle R}$. 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.

Een hasse-diagram is een graafrepresentatie van de transitieve reductie van een eindige, partieel geordende verzameling.