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

modifier

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

modifier

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 binaires
    Rx = R(x, ∙, ∙) ;
  • si la relation ternaire R est cyclique, alors elle est :

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 Rx 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 Rx associées sont des ordres stricts totaux.

Complétion

modifier

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

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

Voir aussi

modifier
  • 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 » (no 23), (lire en ligne), p. 313-342
  • (en) Nimrod Megiddo, « Partial and complete cyclic orders », Bull. Amer. Math. Soc., vol. 82, no 2,‎ , p. 274-276 (lire en ligne)