Transitieve afsluiting: verschil tussen versies

176 bytes toegevoegd ,  3 maanden geleden
geen bewerkingssamenvatting
(De transitieve afsluiting hoeft niet asymmetrisch of irreflexief te zijn.)
Geen bewerkingssamenvatting
De '''transitieve afsluiting''' (Nederland) of '''transitieve sluiting''' (Vlaanderen) <math>R^{+}</math> van een [[tweeplaatsige relatie]] <math>R</math> op een [[Verzameling (wiskunde)|verzameling]] <math>M</math> is de kleinste [[Transitiviteit (wiskunde)|transitieve]] relatie op <math>M</math> die de oorspronkelijke [[Relatie (wiskunde)|relatie]] omvat. Dat wil zeggen dat voor twee elementen <math>x</math> en <math>y</math> uit <math>M</math> geldt dat <math>x \ R^{+} \ y </math> slechts bestaat als er een rij elementen <math>x_0 \, x_1 \, \dots x_n</math> bestaat waarbij: <math> x_0 = x</math>, <math>x_n = y</math> en <math> x_i \ R \ x_{i+1}</math> voor <math> 0 \leq i < n</math>. Iedere tweeplaatsige relatie heeft een transitieve sluiting. Deze vorm van afsluiting, gedefinieerd voor tweeplaatsige relaties, komt overeen met de definitie van [[Afsluiting (verzameling)|afsluiting, gedefinieerd voor verzamelingen]].
 
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 <math>x</math> naar knoop <math>y</math> als de graaf van <math>R</math> een gericht pad met een of meer bogen bevat van <math>x</math> naar <math>y</math>. De transitieve sluiting van een gerichte, acyclische graaf is de graaf, die aangeeft welke [[Knooppunt (wiskunde)|knooppunten]] vanuit andere knopen zijn te bereiken.