Relation acyclique
# 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}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érence

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