Relation acyclique

En mathématiques, une relation acyclique est une relation sans cycle.

Plus précisément, une relation binaire R sur un ensemble E est dite :

• acyclique s'il n'existe pas de n-uplet $(x_1,\dots ,x_n)$ d'éléments de E distincts, avec n ≥ 2, tels que $x_{1}R{x}_2,x_{2}R{x}_3,\dots ,x_{n-1}R{x}_n,x_{n}R{x}_1$ ;
• strictement acyclique si elle est de plus antiréflexive.

Une relation est donc :

• acyclique si et seulement si sa clôture transitive est antisymétrique (ou encore : si sa clôture réflexive transitive est une relation d'ordre) ;
• strictement acyclique si et seulement si sa clôture transitive est asymétrique (ou encore : est un ordre strict).

Toute relation bien fondée est strictement acyclique.

La notion de relation strictement acyclique équivaut à celle de graphe orienté acyclique.