Bijection de Joyal - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

La bijection de Joyal consiste à "déplier", à l'aide de la correspondance fondamentale de Foata, la partie cyclique d'une application de \scriptstyle\ [\![1,n]\!] dans \scriptstyle\ [\![1,n]\!],\ pour en faire un arbre de Cayley. La bijection de Joyal permet de donner une démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir...) élégante de la formule, attribuée à Arthur Cayley, selon laquelle le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) d'arbres étiquetés à n sommets, appelés aussi arbres de Cayley, est :

n(n − 2).

La bijection de Joyal est aussi très utile pour l'étude des propriétés métriques des arbres étiquetés à n sommets.

Une application : une démonstration de la formule de Cayley

Notons \scriptstyle\ \mathcal{C}_n l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) des arbres de Cayley à n sommets. Pour calculer le cardinal de \scriptstyle\ \mathcal{C}_n, une des démonstrations consiste à établir une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y...), appelée bijection de Joyal, entre et l'ensemble des applications de \scriptstyle\ [\![1,n]\!] dans \scriptstyle\ [\![1,n]\!], noté usuellement \scriptstyle\ [\![1,n]\!]^{[\![1,n]\!]}. On a ainsi

n^n\ =\ \text{Card}\ [\![1,n]\!]^{[\![1,n]\!]}\ =\ \text{Card}\ \left(\mathcal{C}_n\times[\![1,n]\!]^2\right)\ =\ n^2\,\text{Card}\ \mathcal{C}_n.

Cette démonstration est attribuée à André Joyal par Aigner et Ziegler, ou encore par Pitman.

On peut voir comme l'ensemble des arbres de Cayley à n sommets, dont deux sommets sont marqués, de deux marques différentes. Le sommet portant la première marque peut être interprété comme la racine de l'arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en...). Les deux marques différentes peuvent être portées par le même sommet.

La bijection de Joyal permet aussi de mieux comprendre la topologie (La topologie est une branche des mathématiques concernant l'étude des déformations spatiales par...) d'un arbre de taille n, en étudiant la distance entre 2 sommets au hasard (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon...) d'un arbre au hasard. En effet, un élément tiré au hasard avec équiprobabilité dans \scriptstyle\ \Omega = \mathcal{C}_n\times[\![1,n]\!]^2 est un arbre de Cayley, avec deux points marqués, tiré au hasard : calculer la loi de différentes statistiques (La statistique est à la fois une science formelle, une méthode et une technique. Elle...) portant sur un arbre de Cayley, avec deux points marqués, tiré au hasard, revient à calculer le cardinal de différentes parties de l'univers (L'Univers est l'ensemble de tout ce qui existe et les lois qui le régissent.) \scriptstyle\ \Omega = \mathcal{C}_n\times[\![1,n]\!]^2.\ Pour cela il peut être plus simple de calculer le cardinal de l'image de ces parties par la bijection de Joyal.

Éléments cycliques et éléments transients

Dans l'ensemble de définition (En mathématiques, l' ensemble de définition D f  d'une fonction  f  dont l'...) de ƒ on peut distinguer les éléments cycliques (ou récurrents) des éléments transients : les éléments cycliques, figurés ci-contre en bleu (Bleu (de l'ancien haut-allemand « blao » = brillant) est une des trois couleurs...), sont les éléments x pour lesquels il existe nx > 0 tel que :

f^{n_x}(x)=x.

Par exemple, ci-contre, n12 = 1, n16 = 2, et n8 = 6. A chaque application ƒ de \scriptstyle\ [\![1,n]\!] dans \scriptstyle\ [\![1,n]\!],\ on peut associer la chaîne de Markov (Selon les auteurs, une chaîne de Markov est de manière générale un processus de...) dont la probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un...) de transition est définie par

p_{i,f(i)}=1,\qquad \forall i\in[\![1,n]\!].

Les éléments récurrents et les éléments transients de ƒ sont alors exactement les éléments récurrents et les éléments transients de cette chaîne (Le mot chaîne peut avoir plusieurs significations :) de Markov.

Représentation graphique d'une application

Représentation graphique de l'application ƒ = (12, 15, 2, 13, 10, 10, 13, 9, 19, 17, 18, 12, 15, 16, 20, 14, 2, 2, 13, 8).

Pour décrire la bijection de Joyal, il est commode d'utiliser une représentation de chaque application ƒ de \scriptstyle\ [\![1,n]\!] dans \scriptstyle\ [\![1,n]\!] à l'aide d'un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) orienté dont l'ensemble des sommets est \scriptstyle\ [\![1,n]\!], et où les arètes relient chaque élément à son image par ƒ. Par exemple, pour ƒ = (12, 15, 2, 13, 10, 10, 13, 9, 19, 17, 18, 12, 15, 16, 20, 14, 2, 2, 13, 8), c'est-à-dire, pour ƒ(1) = 12, ƒ(2) = 15, ƒ(3) = 2, ... on a la représentation graphique ci-contre.

Bijection de Joyal

Image de l'application ƒ par la bijection de Joyal. Le "début" (x=9) est coloré en vert (Le vert est une couleur complémentaire correspondant à la lumière qui a une longueur d'onde...), et la "fin" (y=14) en orange.
Image réciproque (L'image réciproque d'une partie B d'un ensemble Y par une application est le sous-ensemble de X...), par la bijection de Joyal, de l'arbre marqué obtenu en intervertissant les deux marques de l'arbre précédent.

On observe qu'une fois effacées les arètes entre les éléments cycliques de ƒ, la représentation de ƒ ainsi modifiée devient une forêt (Une forêt ou un massif forestier est une étendue boisée, relativement dense,...) (un graphe sans cycles, éventuellement non connexe, dont les composantes connexes sont précisément des arbres), chaque arbre de la forêt pouvant être vu comme enraciné en un des éléments cycliques de ƒ. En "replantant" chacun de ces arbres sur le sommet correspondant du graphe linéaire associé à l'arrangement (La notion d'arrangement est utilisée en probabilités, et notamment pour les...) de tous les éléments de C produit par la correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le...) de Foata, on obtient un arbre de Cayley avec deux sommets marqués.

Réciproquement, la donnée (Dans les technologies de l'information, une donnée est une description élémentaire,...) d'un arbre de Cayley T avec deux points x et y marqués, éventuellement égaux, l'un marqué "début" et l'autre "fin", par exemple, définit

  • une orientation (Au sens littéral, l'orientation désigne ou matérialise la direction de l'Orient (lever du soleil...) de chaque arète de T (par exemple, chaque arète de T est orientée du sommet le plus éloigné de la fin (y) vers le sommet le plus proche de y) ;
  • un unique chemin de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus...) minimale de x à y (il existe un chemin car un arbre est un graphe connexe, il existe un seul chemin minimal car un arbre est un graphe sans cycle) ;
  • une suite ordonnée de nombres de \scriptstyle\ [\![1,n]\!], \ notée ω  : la suite des labels des sommets apparaissant sur le chemin de longueur minimale entre x et y, lorsque ce chemin est parcouru de x à y. La suite ω commence donc par le label du sommet x et se termine donc par le label du sommet y. La longueur de la suite ω peut éventuellement être strictement inférieure à n.

A cette suite ω on peut appliquer la correspondance de Foata, pour trouver une permutation (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets...) τ des nombres constituant ω, permutation dont le graphe est une collection de cycles. Ces cycles sont délimités par les records vers le bas de la suite obtenue en renversant la suite ω, i.e. les records observés en parcourant le chemin de y vers x.

Sur l'exemple ci-contre, x = 9 et y = 14, et le chemin minimal est ω = (9, 19, 13, 15, 20, 8, 12, 16, 14). Les records de la suite renversée (14, 16, 12, 8, 20, 15, 13, 19, 9) sont successivement 14, 12 et 8, ce qui conduit à la décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils...) de τ en cycles disjoints :

\tau\ =\ (9, 19, 13, 15, 20, 8) (12) (16,14).

On retrouve bien ainsi les cycles de ƒ.

Une fois effacées les arètes composant le chemin de longueur minimale entre x et y, l'arbre de Cayley T ainsi modifié devient une forêt, chaque arbre de la forêt pouvant être vu comme enraciné en un des sommets du chemin entre x et y. En "replantant" chacun de ces arbres sur le sommet correspondant du graphe de τ, on obtient le graphe de ƒ.

A titre d'exemple, si l'on intervertit les rôles de x et y, on obtient un nouvel élément de \scriptstyle\ \mathcal{C}_n\times[\![1,n]\!]^2.\ Examinons son image réciproque (La réciproque est une relation d'implication.) g par la bijection de Joyal : l'ensemble des étiquettes des sommets apparaissant sur le chemin de y à x reste le même, mais la suite η obtenue est la suite inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de...) de la suite ω observée précédemment. Les records vers le bas de la suite renversée de η (à savoir la suite ω) sont alors 9 puis 8, conduisant à une décomposition en cycles (14, 16, 12, 8) (20, 15, 13, 19, 9) de la partie cyclique de g. On récupère alors, comme attendu, une application g = (12, 15, 2, 13, 10, 10, 13, 14, 20, 17, 18, 8, 19, 16, 13, 12, 2, 2, 9, 15) différente (En mathématiques, la différente est définie en théorie algébrique des...) de l'application ƒ qu'on avait au départ (voir ci-dessus).

Page générée en 0.021 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique