Relation acyclique

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

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

• acyclique s'il n'existe pas de n-uplet ${\displaystyle (x_{1},\dots ,x_{n})}$ d'éléments de E distincts, avec n ≥ 2, tels que ${\displaystyle x_{1}Rx_{2},~x_{2}Rx_{3},~\dots ,~x_{n-1}Rx_{n},~x_{n}Rx_{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.

Références

1. (en) Patrick Doreian, Vladimir Batagelj (en) et Anuška Ferligoj, Generalized Blockmodeling, CUP, 2005 (lire en ligne), p. 122.