1.1 Arbres non marqués
5
Soit U l’ensemble des suites finies d’entiers strictement positifs. Il est commode
que la suite vide, notée ici 1 ε, appartienne à U . Ainsi
U = {ε} ∪
n≥1
(N >0 )
n
est l’ensemble des mots qui nomment canoniquement les nœuds de l’arbre. La
longueur d’une suite est notée |u| et |ε| = 0. La suite obtenue par concaténation
de u et v se note uv. Si un mot u s’écrit u = vw, alors v est un préfixe et w est un
suffixe de u.
Définition 1.1 Un arbre planaire τ est un sous-ensemble de U qui vérifie les trois
conditions suivantes
(i) ε ∈ τ (un arbre n’est pas vide, il contient au moins la racine) ;
(ii) ∀u, v ∈ U , si uv ∈ τ alors u ∈ τ (il est possible de remonter le long d’une
branche vers la racine) ;
(iii) ∀u ∈ U , si u ∈ τ , alors il existe M u (τ ) ∈ N tel que pour tout j ≥ 1,
uj ∈ τ si et seulement si 1 ≤ j ≤ M u (τ ).
L’ensemble des arbres planaires est noté P.
La dernière condition de la définition 1.1 traduit le fait que, dans un arbre
planaire τ , lorsqu’un nœud u a M u enfants, alors ces enfants – qui appartiennent
à τ – sont numérotés de 1 à M u . Il est tout à fait possible de définir des arbres qui
ne vérifient pas cette condition, ce sont les arbres préfixes ci-dessous.
Définition 1.2 Un arbre préfixe τ est un sous-ensemble de U qui vérifie les deux
conditions suivantes
(i) ε ∈ τ (un arbre n’est pas vide, il contient au moins la racine) ;
(ii) ∀u, v ∈ U , si uv ∈ τ alors u ∈ τ (il est possible de remonter le long d’une
branche vers la racine).
L’ensemble des arbres préfixes est noté Pref .
Nous donnons des exemples d’arbre planaire et d’arbre préfixe respectivement dans
les figures 1.1 et 1.2.
Un peu de vocabulaire Les définitions qui suivent sont valables pour tous les types
d’arbres que nous rencontrerons dans ce livre ; nous ne les répéterons donc pas pour
les classes d’arbres que nous présentons dans la suite de ce chapitre.
1 Nous avons ici sacrifié à l’usage en combinatoire des mots en notant par ε la suite vide et donc
la racine des arbres, mais dans d’autres contextes, probabilistes notamment, elle est généralement
désignée par ∅.
5
Soit U l’ensemble des suites finies d’entiers strictement positifs. Il est commode
que la suite vide, notée ici 1 ε, appartienne à U . Ainsi
U = {ε} ∪
n≥1
(N >0 )
n
est l’ensemble des mots qui nomment canoniquement les nœuds de l’arbre. La
longueur d’une suite est notée |u| et |ε| = 0. La suite obtenue par concaténation
de u et v se note uv. Si un mot u s’écrit u = vw, alors v est un préfixe et w est un
suffixe de u.
Définition 1.1 Un arbre planaire τ est un sous-ensemble de U qui vérifie les trois
conditions suivantes
(i) ε ∈ τ (un arbre n’est pas vide, il contient au moins la racine) ;
(ii) ∀u, v ∈ U , si uv ∈ τ alors u ∈ τ (il est possible de remonter le long d’une
branche vers la racine) ;
(iii) ∀u ∈ U , si u ∈ τ , alors il existe M u (τ ) ∈ N tel que pour tout j ≥ 1,
uj ∈ τ si et seulement si 1 ≤ j ≤ M u (τ ).
L’ensemble des arbres planaires est noté P.
La dernière condition de la définition 1.1 traduit le fait que, dans un arbre
planaire τ , lorsqu’un nœud u a M u enfants, alors ces enfants – qui appartiennent
à τ – sont numérotés de 1 à M u . Il est tout à fait possible de définir des arbres qui
ne vérifient pas cette condition, ce sont les arbres préfixes ci-dessous.
Définition 1.2 Un arbre préfixe τ est un sous-ensemble de U qui vérifie les deux
conditions suivantes
(i) ε ∈ τ (un arbre n’est pas vide, il contient au moins la racine) ;
(ii) ∀u, v ∈ U , si uv ∈ τ alors u ∈ τ (il est possible de remonter le long d’une
branche vers la racine).
L’ensemble des arbres préfixes est noté Pref .
Nous donnons des exemples d’arbre planaire et d’arbre préfixe respectivement dans
les figures 1.1 et 1.2.
Un peu de vocabulaire Les définitions qui suivent sont valables pour tous les types
d’arbres que nous rencontrerons dans ce livre ; nous ne les répéterons donc pas pour
les classes d’arbres que nous présentons dans la suite de ce chapitre.
1 Nous avons ici sacrifié à l’usage en combinatoire des mots en notant par ε la suite vide et donc
la racine des arbres, mais dans d’autres contextes, probabilistes notamment, elle est généralement
désignée par ∅.