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 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 = R(x, ∙, ∙) ; si la relation ternaire R est cyclique, alors elle est : asymétrique si et seulement si chaque R est une relation (binaire) asymétrique : R(y, z) ⇒ ¬R(z, y), transitive si et seulement si chaque R est une relation (binaire) transitive : R(y, z) et R(z, u) ⇒ R(y, u), antiréflexive si et seulement si chaque R est une relation (binaire) antiréflexive : ¬R(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é :
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..
Notes et références
Voir aussi
Catégorie:Théorie des ordres Catégorie:Cercle Catégorie:Relation (mathématiques)