14
1 Botanique
Un cas particulier important est celui où les nœuds internes sont d’arité 2 : il
s’agit de l’analogue non planaire de la classe B des arbres binaires complets. Soit
P (2) une telle classe ; elle vérifie l’équation récursive
P (2) = + (• × M 2 (P (2) )),
(1.4)
où la construction combinatoire M 2 (.) correspond à choisir un multi-ensemble de
taille 2, i.e., une paire (non ordonnée) de deux objets, distincts ou non. P (2) est
aussi isomorphe à l’ensemble des classes d’équivalence de l’ensemble des arbres
planaires finis de P {0,2} sous la relation R de la définition 1.14.
1.2 Arbres marqués
1.2.1 Définition des arbres marqués
Plutôt que le terme d’arbre étiqueté qui peut prêter à confusion avec les classes
combinatoires étiquetées, nous parlerons de préférence d’arbre marqué, dans
l’acception du terme introduit par Neveu [194].
Définition 1.15 Un arbre marqué est un couple
τ = (τ, (γ u ) u∈τ ) ,
où τ est un des arbres définis en section 1.1, et où les marques γ u sont des éléments
d’un ensemble
L’arbre non marqué τ est la forme de l’arbre marqué τ ; il est aussi noté π(τ ),
c’est l’ensemble des nœuds de l’arbre marqué.
Les marques peuvent être des couleurs, des nombres (le numéro de génération, . . . ),
des positions dans l’espace, des opérateurs logiques ou arithmétiques (∧, ∨, →
, +, ×, etc), des lettres d’un alphabet, etc. Nous donnons deux exemples d’arbres
marqués dans la figure 1.12.
Lorsque l’ensemble des marques est totalement ordonné, il arrive souvent que
seul l’ordre des marques soit important, non leur valeur. Cette idée conduit aux
notions d’arbre des rangs, de marquage canonique et de réordonnement que nous
définissons ci-dessous.
Fig. 1.12 Deux arbres
marqués : pour le premier
= {+, −, ∗, /} ∪ N ∪
{a, b, . . . , z} ; pour le second
= {∧, ∨} ∪ {a, b, . . . , z}
1 Botanique
Un cas particulier important est celui où les nœuds internes sont d’arité 2 : il
s’agit de l’analogue non planaire de la classe B des arbres binaires complets. Soit
P (2) une telle classe ; elle vérifie l’équation récursive
P (2) = + (• × M 2 (P (2) )),
(1.4)
où la construction combinatoire M 2 (.) correspond à choisir un multi-ensemble de
taille 2, i.e., une paire (non ordonnée) de deux objets, distincts ou non. P (2) est
aussi isomorphe à l’ensemble des classes d’équivalence de l’ensemble des arbres
planaires finis de P {0,2} sous la relation R de la définition 1.14.
1.2 Arbres marqués
1.2.1 Définition des arbres marqués
Plutôt que le terme d’arbre étiqueté qui peut prêter à confusion avec les classes
combinatoires étiquetées, nous parlerons de préférence d’arbre marqué, dans
l’acception du terme introduit par Neveu [194].
Définition 1.15 Un arbre marqué est un couple
τ = (τ, (γ u ) u∈τ ) ,
où τ est un des arbres définis en section 1.1, et où les marques γ u sont des éléments
d’un ensemble
L’arbre non marqué τ est la forme de l’arbre marqué τ ; il est aussi noté π(τ ),
c’est l’ensemble des nœuds de l’arbre marqué.
Les marques peuvent être des couleurs, des nombres (le numéro de génération, . . . ),
des positions dans l’espace, des opérateurs logiques ou arithmétiques (∧, ∨, →
, +, ×, etc), des lettres d’un alphabet, etc. Nous donnons deux exemples d’arbres
marqués dans la figure 1.12.
Lorsque l’ensemble des marques est totalement ordonné, il arrive souvent que
seul l’ordre des marques soit important, non leur valeur. Cette idée conduit aux
notions d’arbre des rangs, de marquage canonique et de réordonnement que nous
définissons ci-dessous.
Fig. 1.12 Deux arbres
marqués : pour le premier
= {+, −, ∗, /} ∪ N ∪
{a, b, . . . , z} ; pour le second
= {∧, ∨} ∪ {a, b, . . . , z}