Dans cet article, nous allons analyser Ordre cyclique, un sujet qui a suscité un grand intérêt ces derniers temps. Ordre cyclique est un sujet qui a retenu l'attention de nombreuses personnes en raison de sa pertinence dans différents domaines, de la science à la culture populaire. De plus, Ordre cyclique a fait l'objet de nombreux débats et discussions, ce qui a contribué à son importance croissante dans la société actuelle. Tout au long de cet article, nous explorerons différents aspects liés à Ordre cyclique, depuis son origine et son évolution jusqu'à son impact aujourd'hui. Grâce à une analyse détaillée, nous essaierons de faire la lumière sur ce sujet et de fournir un aperçu plus complet et plus approfondi de 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.
Sur un ensemble donné, un ordre cyclique est une relation ternaire R :
Un ordre cyclique R est dit total s'il est de plus
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.
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 :
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.
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.