1.2 Arbres marqués
17
Fig. 1.15 Un arbre de
Cayley à 8 nœuds, marqué
avec les entiers 1, 2, . . . , 8 ;
pour la représentation
graphique, les enfants d’un
nœud sont ordonnés par ordre
croissant de marque
Définition 1.19 Soient un alphabet A et une fonction arité g de cet alphabet vers
N, telle qu’il existe au moins une lettre d’arité 0. Un symbole est un couple ((, g(()),
où ∈ A. Notons S = {((, g(()), , ∈ A} l’ensemble des symboles, 7 et E l’image
de A par la fonction arité, i.e., l’ensemble des valeurs p de N telles qu’il existe
au moins une lettre d’arité p. La famille simple d’arbres F sur l’ensemble de
symboles S est alors l’ensemble (P E , A) des arbres marqués par des lettres de A
de telle sorte que, pour tout nœud, son arité (i.e., le nombre de ses fils) soit égale à
l’arité de sa marque.
Remarque 1.20 La famille F ne contient pas l’arbre vide. L’existence d’au moins
un symbole d’arité 0 dans S assure qu’il existe des arbres finis dans F .
1.2.3 Arbres de Cayley
Un exemple classique d’arbres marqués est l’ensemble Cay des arbres de Cayley,
obtenus lorsque l’ensemble des formes d’arbres est Pó, l’ensemble des arbres
non planaires ou de Pólya, et qui sont des structures étiquetées au sens de la
section B.1.2, i.e., chaque nœud d’un arbre τ porte une marque distincte de
{1, . . . , |τ |}.
Définition 1.21 Un arbre de Cayley est un arbre τ non planaire marqué dont les
marques sont prises dans {1, . . . , |τ |} et sont toutes distinctes. L’ensemble des
arbres de Cayley est noté Cay.
En conséquence, un arbre de Cayley τ est son propre arbre des rangs :
C(τ ) = τ.
Pour représenter les arbres de Cayley, il est courant d’ordonner les enfants d’un
même nœud interne de gauche à droite, suivant l’ordre croissant de leurs marques ;
cf. la figure 1.15.
7 S est le graphe de la relation g.