Chapitre 2
Aléa sur les arbres
Nous avons introduit dans le chapitre 1 les différents types d’arbres que nous
étudions dans ce livre. Nous expliquons ici de quelles manières il est possible
d’obtenir des arbres aléatoires. Les sections 2.1 et 2.2 traitent respectivement des
arbres non marqués et marqués. L’aléa sur les arbres digitaux fait appel à des notions
différentes et est présenté en section 2.3.
2.1 Aléa sur les arbres non marqués
Il y a plusieurs façons d’introduire de l’aléa sur les arbres non marqués, en voici
quelques-unes :
– L’arbre est choisi uniformément au hasard parmi tous les arbres dans un ensemble
d’arbres. Nous parlerons indifféremment de modèle uniforme, de modèle de
Catalan, ou de modèle combinatoire ; voir section 2.1.1.
– L’arbre lui-même grossit (pousse) de manière aléatoire. Nous présentons en section 2.1.3 le modèle le plus simple d’arbres de branchement, les arbres de GaltonWatson.
– L’arbre peut aussi pousser en faisant bourgeonner une feuille prise au hasard,
c’est le modèle « bourgeonnant » décrit dans la section 2.1.2.
2.1.1 Modèle de Catalan
Le plus simple pour choisir au hasard un arbre dans un ensemble d’arbres est le
choix uniforme. Appliqué aux arbres binaires de taille donnée n, ce modèle conduit
à donner à chaque arbre de cette taille une probabilité 1/C n , C n étant le nombre
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_2
41
Aléa sur les arbres
Nous avons introduit dans le chapitre 1 les différents types d’arbres que nous
étudions dans ce livre. Nous expliquons ici de quelles manières il est possible
d’obtenir des arbres aléatoires. Les sections 2.1 et 2.2 traitent respectivement des
arbres non marqués et marqués. L’aléa sur les arbres digitaux fait appel à des notions
différentes et est présenté en section 2.3.
2.1 Aléa sur les arbres non marqués
Il y a plusieurs façons d’introduire de l’aléa sur les arbres non marqués, en voici
quelques-unes :
– L’arbre est choisi uniformément au hasard parmi tous les arbres dans un ensemble
d’arbres. Nous parlerons indifféremment de modèle uniforme, de modèle de
Catalan, ou de modèle combinatoire ; voir section 2.1.1.
– L’arbre lui-même grossit (pousse) de manière aléatoire. Nous présentons en section 2.1.3 le modèle le plus simple d’arbres de branchement, les arbres de GaltonWatson.
– L’arbre peut aussi pousser en faisant bourgeonner une feuille prise au hasard,
c’est le modèle « bourgeonnant » décrit dans la section 2.1.2.
2.1.1 Modèle de Catalan
Le plus simple pour choisir au hasard un arbre dans un ensemble d’arbres est le
choix uniforme. Appliqué aux arbres binaires de taille donnée n, ce modèle conduit
à donner à chaque arbre de cette taille une probabilité 1/C n , C n étant le nombre
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_2
41