4
1 Botanique
Ces deux points de vue : arbre marqué, ou non marqué, vont apparaître dans ce
chapitre. Nous les soulignons à chaque fois. Ils permettent aussi de distinguer dans
le chapitre 2 comment l’aléa peut être introduit sur les arbres.
Ce chapitre est ainsi structuré en présentant les arbres, sous le double aspect
de structures finies ou potentiellement infinies, comme structures d’abord non
marquées, puis marquées, respectivement dans les sections 1.1 et 1.2 ; il se termine
par la section 1.3, qui présente les paramètres d’arbres que nous étudierons dans ce
livre.
Toutes nos analyses concernent les arbres enracinés, c’est-à-dire admettant un nœud
distingué appelé racine ; nous omettrons l’adjectif « enraciné » dans ce livre.
1.1 Arbres non marqués
Les sections 1.1.1 et 1.1.2 présentent les arbres planaires et les arbres binaires
respectivement. Dans chacun des cas, deux définitions sont possibles : une définition
récursive par classe combinatoire et une définition par numérotation canonique
des nœuds de l’arbre. Chacune des deux définitions sera utilisée par la suite.
L’appréciation du caractère « naturel » de chacune des deux définitions est
éminemment subjective. . .
Nous présentons ensuite en section 1.1.3 une bijection entre ces deux classes :
arbres planaires et arbres binaires, avant de considérer les arbres non planaires en
section 1.1.4.
1.1.1 Arbres planaires
Nous donnons ci-dessous deux définitions des arbres planaires, tout d’abord comme
ensemble de mots sur l’alphabet des entiers strictement positifs, puis comme classe
combinatoire. Les arbres planaires sont appelés ainsi parce que les enfants d’un
sommet sont ordonnés, et que ces arbres se dessinent assez naturellement dans le
plan en ordonnant de gauche à droite les enfants d’un même nœud.
A. Représentation canonique des arbres planaires Dans cette définition d’un
arbre planaire, les nœuds de l’arbre sont des mots finis sur N >0 , c’est-à-dire des
suites finies d’entiers strictement positifs.
1 Botanique
Ces deux points de vue : arbre marqué, ou non marqué, vont apparaître dans ce
chapitre. Nous les soulignons à chaque fois. Ils permettent aussi de distinguer dans
le chapitre 2 comment l’aléa peut être introduit sur les arbres.
Ce chapitre est ainsi structuré en présentant les arbres, sous le double aspect
de structures finies ou potentiellement infinies, comme structures d’abord non
marquées, puis marquées, respectivement dans les sections 1.1 et 1.2 ; il se termine
par la section 1.3, qui présente les paramètres d’arbres que nous étudierons dans ce
livre.
Toutes nos analyses concernent les arbres enracinés, c’est-à-dire admettant un nœud
distingué appelé racine ; nous omettrons l’adjectif « enraciné » dans ce livre.
1.1 Arbres non marqués
Les sections 1.1.1 et 1.1.2 présentent les arbres planaires et les arbres binaires
respectivement. Dans chacun des cas, deux définitions sont possibles : une définition
récursive par classe combinatoire et une définition par numérotation canonique
des nœuds de l’arbre. Chacune des deux définitions sera utilisée par la suite.
L’appréciation du caractère « naturel » de chacune des deux définitions est
éminemment subjective. . .
Nous présentons ensuite en section 1.1.3 une bijection entre ces deux classes :
arbres planaires et arbres binaires, avant de considérer les arbres non planaires en
section 1.1.4.
1.1.1 Arbres planaires
Nous donnons ci-dessous deux définitions des arbres planaires, tout d’abord comme
ensemble de mots sur l’alphabet des entiers strictement positifs, puis comme classe
combinatoire. Les arbres planaires sont appelés ainsi parce que les enfants d’un
sommet sont ordonnés, et que ces arbres se dessinent assez naturellement dans le
plan en ordonnant de gauche à droite les enfants d’un même nœud.
A. Représentation canonique des arbres planaires Dans cette définition d’un
arbre planaire, les nœuds de l’arbre sont des mots finis sur N >0 , c’est-à-dire des
suites finies d’entiers strictement positifs.