Transitieve afsluiting

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

als er een rij elementen bestaat met en voor

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 een boog van knoop naar knoop als de graaf van een gericht pad met een of meer bogen bevat van naar . 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.

VoorbeeldenBewerken

 
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 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   bepaald door   als  , d.w.z.   volgt op  , de relatie die van twee getallen bepaalt welke de grootste is.

BerekeningBewerken

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.

Transitieve reductieBewerken

De transitieve reductie is de tegenhanger van de transitieve afsluiting. De transitieve reductie van een tweeplaatsige relatie   is de kleinste relatie die dezelfde transitieve afsluiting heeft als  . 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.