1.2 Arbres marqués
15
Définition 1.16 Soit τ un arbre marqué de taille finie, dont les marques appartiennent à un ensemble totalement ordonné. Soit π(τ ) la forme de cet arbre. L’arbre
des rangs de τ est l’arbre marqué C(τ ) obtenu en marquant les nœuds de l’arbre
π(τ ) par les entiers 1, 2, . . . , k, où k est le nombre de marques distinctes présentes
dans τ , et en respectant l’ordre des marques.
Nous appelons marquage canonique ce procédé de passage des marques aux
rangs – qui sont eux-mêmes des marques.
Définition 1.17 Soit τ un arbre marqué de taille finie k, k ≤ 1, dont les marques
x 1 , . . . , x k sont toutes distinctes et appartiennent à un ensemble totalement ordonné.
Le réordonnement ou statistique d’ordre de x 1 , . . . , x k est la permutation σ k ∈ S k
définie par
x σ k (1) < x σ k (2) < · · · < x σ k (k) .
(1.5)
La permutation σ
−1
k donne les rangs des marques. Ces rangs apparaissent sur l’arbre
des rangs.
La figure 1.13 donne un exemple d’arbre marqué à marques réelles, et de l’arbre des
rangs obtenu par marquage canonique.
Remarque 1.18 Le marquage canonique ne change évidemment pas la forme de
l’arbre : π(C(τ )) = π(τ ).
Attention : il n’est pas toujours possible, ou pertinent, de définir l’arbre des
rangs d’un arbre marqué ; cf. par exemple les deux arbres de la figure 1.12, où
l’ensemble des marques n’est pas « naturellement » totalement ordonné.
Fig. 1.13 En haut, un arbre
marqué τ de taille 9 dont les
marques sont dans R ; en bas
l’arbre des rangs C(τ ), dont
les marques sont les entiers
de 1 à 9, et qui est obtenu par
marquage canonique de τ
15
Définition 1.16 Soit τ un arbre marqué de taille finie, dont les marques appartiennent à un ensemble totalement ordonné. Soit π(τ ) la forme de cet arbre. L’arbre
des rangs de τ est l’arbre marqué C(τ ) obtenu en marquant les nœuds de l’arbre
π(τ ) par les entiers 1, 2, . . . , k, où k est le nombre de marques distinctes présentes
dans τ , et en respectant l’ordre des marques.
Nous appelons marquage canonique ce procédé de passage des marques aux
rangs – qui sont eux-mêmes des marques.
Définition 1.17 Soit τ un arbre marqué de taille finie k, k ≤ 1, dont les marques
x 1 , . . . , x k sont toutes distinctes et appartiennent à un ensemble totalement ordonné.
Le réordonnement ou statistique d’ordre de x 1 , . . . , x k est la permutation σ k ∈ S k
définie par
x σ k (1) < x σ k (2) < · · · < x σ k (k) .
(1.5)
La permutation σ
−1
k donne les rangs des marques. Ces rangs apparaissent sur l’arbre
des rangs.
La figure 1.13 donne un exemple d’arbre marqué à marques réelles, et de l’arbre des
rangs obtenu par marquage canonique.
Remarque 1.18 Le marquage canonique ne change évidemment pas la forme de
l’arbre : π(C(τ )) = π(τ ).
Attention : il n’est pas toujours possible, ou pertinent, de définir l’arbre des
rangs d’un arbre marqué ; cf. par exemple les deux arbres de la figure 1.12, où
l’ensemble des marques n’est pas « naturellement » totalement ordonné.
Fig. 1.13 En haut, un arbre
marqué τ de taille 9 dont les
marques sont dans R ; en bas
l’arbre des rangs C(τ ), dont
les marques sont les entiers
de 1 à 9, et qui est obtenu par
marquage canonique de τ