Transitieve afsluiting: verschil tussen versies

834 bytes toegevoegd ,  10 jaar geleden
geen bewerkingssamenvatting
kGeen bewerkingssamenvatting
Geen bewerkingssamenvatting
<math> x_i \ R \ x_{i+1}</math> voor <math> 0 \leq i < n</math>.
 
Elke binaire relatie heeft een transitieve sluiting.
Als men de relaties voorstelt als een [[grafentheorie#Gerichte grafen|gerichte graaf]], bevat de graaf van de transitieve sluiting <math>R^{+}</math> een boog van knoop ''x'' naar knoop ''y'' als de graaf van <math>R</math> een gericht pad met één of meer bogen bevat van ''x'' naar ''y''.
 
Als men de relaties voorstelt als een [[grafentheorie#Gerichte grafen|gerichte graaf]], bevat de graaf van de transitieve sluiting <math>R^{+}</math> een boog van knoop ''x'' naar knoop ''y'' als de graaf van <math>R</math> 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 [[partiële orde#Strikte partiële orde|strikte partiële orde]] op de verzameling knopen.
 
==Voorbeelden==
 
*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 [[natuurlijk getal|natuurlijke getallen]] is de transitieve sluiting van de relatie <math>a \,R \,b : \Longleftrightarrow a = b + 1</math> ("a volgt op b") de relatie "is groter dan".
 
==Berekenen van de transitieve sluiting==
De transitieve sluiting van een relatie of graaf kan men bepalen met behulp van het [[Floyd-Warshall-algoritme]]. Dat algoritme bepaalt de kortste afstand tussen alle knopenparen in een gerichte graaf met een [[dynamische programmering]]smethode.
 
==Transitieve reductie==
29.082

bewerkingen