Ordre cyclique
# Ordre cyclique

En mathématiques, un ordre cyclique est un certain type de relation ternaire qui permet, typiquement, de décrire l'ordre de parcours naturel des points du cercle orienté. Les ordres cycliques ne sont donc pas des relations d'ordre (ces dernières sont binaires). Cependant, leur définition est apparentée à celle d'une relation d'ordre strict. Dans ce contexte, l'homologue d'un ordre strict total est un ordre cyclique total (en) ou ordre cyclique complet.

## Définition

Sur un ensemble donné, un ordre cyclique est une relation ternaire R :

* cyclique, c'est-à-dire invariante par permutation circulaire : R(x, y, z) ⇒ R(y, z, x) ;
* asymétrique : R(x, y, z) ⇒ ¬R(z, y, x) ;
* transitive : R(x, y, z) et R(x, z, u) ⇒ R(x, y, u).

Un ordre cyclique R est dit total s'il est de plus

* complet : x, y, z distincts ⇒ R(u, v, w) pour au moins l'un des six permutés (u, v, w) de (x, y, z),

donc pour exactement trois permutés : ou bien (x, y, z) et ses permutés circulaires, ou bien (x, z, y) et ses permutés circulaires.

## Reformulation

En présence de la cyclicité et de la transitivité, l'asymétrie équivaut à la condition d'antiréflexivité : ¬R(x, x, y).

En effet :

* la donnée d'une relation ternaire R équivaut à celle de la famille des relations $binairesR_x$ = R(x, ∙, ∙) ;
* si la relation ternaire R est cyclique, alors elle est :
   * asymétrique si et seulement si chaque $R_x$ est une relation (binaire) asymétrique : $R_x(y,$ z) ⇒ $¬R_x(z,$ y),
   * transitive si et seulement si chaque $R_x$ est une relation (binaire) transitive : $R_x(y,$ z) et $R_x(z,$ u) ⇒ $R_x(y,$ u),
   * antiréflexive si et seulement si chaque $R_x$ est une relation (binaire) antiréflexive : $¬R_x(y,$ y).

Or toute relation binaire asymétrique est antiréflexive, et toute relation binaire transitive et antiréflexive — c'est-à-dire tout ordre strict — est asymétrique.

En résumé :

   * Un ordre cyclique est une relation ternaire cyclique R dont les relations binaires $R_x$ associées sont des ordres stricts.

   * Un ordre cyclique total — ou ordre cyclique complet, ou cycle — est une relation ternaire cyclique R dont les relations binaires $R_x$ associées sont des ordres stricts totaux.

## Complétion

Le problème de la complétion des ordres cycliques contraste fortement avec celui des ordres usuels. Pour ces derniers, le théorème d'extension de Szpilrajn garantit que tout ordre partiel sur un ensemble E — fini ou infini — est prolongeable en un ordre total sur E, et dans le cas où E est fini, on dispose d'algorithmes linéaires qui fournissent un tel prolongement. Les ordres cycliques même finis, au contraire, ne sont pas toujours prolongeables en des ordres cycliques complets, et le problème de décision correspondant est NP-complet, car 3-SAT s'y réduit.

