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)[1].

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[1].

Reformulation

En présence de la cyclicité et de la transitivité, l'asymétrie équivaut à la condition d'antiréflexivité[2] : ¬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[3].

Notes et références

1. (en) Vítězslav Novák, « Cyclically ordered sets », Czechoslovak Mathematical Journal, vol. 32, n^o 3,‎ 1982, p. 460-473 (lire en ligne).
2. Paul Ruet, « Variétés d'ordres », 2007.
3. (en) Zvi Galil (en) et Nimrod Megiddo, « Cyclic ordering is NP-complete », TCS, vol. 5, n^o 2,‎ 1977, p. 179-182 (lire en ligne).

Voir aussi

• Roland Fraïssé, « L'intervalle en théorie des relations ; ses généralisations, filtre intervallaire et clôture d'une relation », dans M. Pouzet et D. Richard, Orders: Descriptions and Roles, North-Holland, coll. « Annals of Discrete Mathematics » (n^o 23), 1984 (lire en ligne), p. 313-342
• (en) Nimrod Megiddo, « Partial and complete cyclic orders », Bull. Amer. Math. Soc., vol. 82, n^o 2,‎ 1976, p. 274-276 (lire en ligne)