X Informatique MP 2011

Thème de l'épreuve Transmission dans les arbres
Principaux outils utilisés arbres, algorithmique
Mots clefs arbre, arbre binomial, diamètre, diffusion, échange total, profondeur, modèle « du téléphone »

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
              

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE ­ ÉCOLES NORMALES SUPÉRIEURES

FILIÈRE

CONCOURS D'ADMISSION 2011

MP SPÉCIALITÉ INFO

COMPOSITION D'INFORMATIQUE ­ A ­ (XULC)
(Durée : 4 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête 
de la copie.

Transmission dans les arbres
On étudie dans ce problème des algorithmes de transmission d'informations dans 
les arbres,
avec le modèle dit "du téléphone". Dans la partie I, on étudie les arbres 
binomiaux. Dans la
partie II, on considère plusieurs calculs élémentaires sur les arbres. Dans la 
partie III, on étudie
la diffusion de l'information à partir de la racine de l'arbre. Dans la partie 
IV, on s'intéresse à
l'échange total d'informations entre tous les noeuds d'un arbre. Les parties I 
et II sont indépendantes.

Algorithmes et programmes
­ Pour les questions qui demandent la conception d'un algorithme : il s'agit de 
donner une
description concise mais précise, en français, d'un algorithme effectuant la 
tâche indiquée.
­ Pour les questions qui demandent l'écriture d'un programme : il s'agit 
d'exprimer votre algorithme dans un langage de programmation de votre choix. La 
lisibilité de votre programme
(notamment : mise en évidence de sa structure, indentation, commentaires 
pertinents) sera
prise en compte dans l'évaluation.
­ Lorsqu'elle est demandée, la complexité d'un algorithme ou d'un programme ne 
sera pas
calculée exactement mais seulement estimée en ordre de grandeur, avec des 
expressions du
type O(m+n), O(m2 log n), etc., où m, n, . . . sont des paramètres en entrée de 
l'algorithme.
­ Lorsqu'une question demande d'écrire un programme, et qu'une certaine 
complexité est
exigée, on ne demande pas de faire la preuve que le programme proposé a 
effectivement
cette complexité.

Définitions
­ Un arbre T = (r, L) est défini par la donnée d'un entier r, appelé noeud, et 
d'une liste
d'arbres L, éventuellement vide. Si la liste L est vide, on dit que r est un 
noeud externe.
Sinon, la liste L comprend  éléments Ti = (ri , Li ), 1  i  , on dit que r est 
un noeud
interne, que les noeuds ri sont les fils de r, et que r est le père des ri .

1

­ Tous les noeuds de T sont supposés distincts. On note N (T ) l'ensemble de 
tous les noeuds
de T et nbn(T ) leur nombre.
­ Dans un arbre, les voisins d'un noeud sont son père (s'il existe) et ses fils.
­ Entre deux noeuds s et t de T il existe un unique chemin, composé de noeuds 
x0 , x1 , . . . , xk
deux à deux distincts, tels que x0 = s, xk = t, et xi et xi+1 sont voisins pour 
0  i  k - 1.
On note chemin(s, t) ce chemin et on dit que k est sa longueur.
­ Le noeud r est appelé la racine de T .
­ La profondeur d'un noeud s est la longueur de chemin(s, r) ; en particulier, 
la racine r a
pour profondeur 0. La profondeur de T est le maximum de la profondeur de ses 
noeuds.
Les arbres seront représentés en Caml et en Pascal de la manière suivante :
{ Pascal }
type arbre = ^noeud ;
liste_arbre = ^element ;
noeud = record n :integer ; l :liste_arbre ; end ;
element = record a :arbre ; r :liste_arbre ; end ;

(* Caml *)
type arbre =
| Noeud of int * arbre list ; ;

Certaines questions font par ailleurs intervenir des listes d'entiers, qui 
seront représentées par
le type liste suivant :
type liste == int list ; ;

type liste = ^entier ;
entier = record e :integer ; s :liste ; end ;

Partie I.

Arbres binomiaux

Dans cette partie, on étudie des arbres particuliers, appelés "binomiaux".
Soit k un entier positif ou nul. Un arbre binomial d'ordre k est défini comme 
suit :
­ un arbre binomial d'ordre 0 est réduit à sa racine ;
­ si k > 0, un arbre binomial d'ordre k est de la forme (rk , (Tk-1 , . . . , 
T1 , T0 )) où chaque Ti
est un arbre binomial d'ordre i.
Dans la suite, Bk désigne un arbre binomial d'ordre k.
Question 1

Dessiner B4 , avec une numérotation des noeuds de votre choix.

Question 2

Quel est le nombre de noeuds de Bk ? Combien sont externes ?

Question 3 Pour k > 0, montrer qu'on peut aussi définir récursivement Bk à 
l'aide de deux
copies de Bk-1 .
Question 4 Écrire une fonction copie qui prend en arguments un entier n et un 
arbre T et
renvoie une copie de l'arbre T dans laquelle chaque noeud de numéro i est 
remplacé par un noeud
de numéro i + n.
2

(* Caml *) copie : int -> arbre -> arbre
{ Pascal } function copie(n : integer ; t : arbre) : arbre ;

Question 5 Écrire une fonction bin qui prend en argument un entier k  0 et qui 
renvoie l'arbre
Bk , avec une numérotation des noeuds de votre choix. On garantira une 
complexité proportionnelle
au nombre de noeuds de Bk .
(* Caml *) bin : int -> arbre
{ Pascal } function bin(k : integer) : arbre ;

Question 6 Quelle est la profondeur de Bk ? Quelle est la longueur maximale 
d'un chemin
entre deux noeuds ?
Question 7

Combien de noeuds ont une profondeur donnée  ?

Question 8 Pour n  1, on définit Cn comme un arbre de racine r et à n noeuds, 
qu'on obtient
avec la numérotation suivante des noeuds : la racine r a le numéro 1, et le 
père du noeud de
numéro i, où 2  i  n, est le noeud de numéro i - 2log2 i-1 , où la notation x 
désigne le plus
petit entier supérieur ou égal à x. Dessiner C16 . Justifier que la définition 
de Cn conduit bien à
un arbre. Donner, sans la justifier, une relation entre Bk et C2k .
Question 9 Écrire une fonction cn qui prend en argument un entier n  1 et qui 
renvoie
l'arbre Cn . On garantira une complexité O(n).
(* Caml *) cn : int -> arbre
{ Pascal } function cn(n : integer) : arbre ;

Partie II.

Fonctions élémentaires sur les arbres

Question 10 Écrire une fonction profondeur qui prend en argument un arbre T et 
renvoie sa
profondeur. On garantira une complexité O(nbn(T )).
(* Caml *) profondeur : arbre -> int
{ Pascal } function profondeur(t : arbre) : integer ;

Question 11 Écrire une fonction noeud_externe_max qui prend en argument un 
arbre T et
qui renvoie le numéro d'un noeud externe de T de profondeur maximale. En cas 
d'égalité, on
choisira arbitrairement. On garantira une complexité O(nbn(T )).
(* Caml *) noeud_externe_max : arbre -> int
{ Pascal } function noeud_externe_max(t : arbre) : integer ;
3

Question 12 Soit T un arbre de racine r et s un noeud de T . Écrire une 
fonction chemin
qui prend en arguments T et s et renvoie l'unique chemin de r à s sous la forme 
d'une liste
d'entiers [x0 ; x1 ; . . . ; xk ] avec x0 = r, xk = s et xi père de xi+1 pour 0 
 i < k. On garantira une
complexité O(nbn(T )).
(* Caml *) chemin : arbre -> int -> liste
{ Pascal } function chemin(t : arbre ; s : integer) : liste ;

Question 13 Soit T un arbre et s un noeud de T . On définit l'arbre obtenu par 
changement
de racine s, noté pivot(T , s), comme l'arbre T  de racine s dont les noeuds 
sont les mêmes que
ceux de T et tel que deux noeuds sont voisins dans T  si et seulement s'ils le 
sont dans T .
Écrire une fonction pivot qui prend en arguments T et s et renvoie l'arbre 
pivot (T , s).
On garantira une complexité O(nbn(T )). S'il y a plusieurs tels arbres T  , on 
en choisit un
arbitrairement.
(* Caml *) pivot : arbre -> int -> arbre
{ Pascal } function pivot(t : arbre ; s : integer) : arbre ;

Question 14 Étant donné un arbre T , on définit son diamètre comme la longueur 
du plus
long chemin dans T . Soit r1 l'un des noeuds externes de T de profondeur 
maximale, et T  =
pivot(T , r1 ) l'arbre obtenu à partir de T par changement de racine r1 . 
Montrer que le diamètre
de T est égal à la profondeur de T  .
Question 15
son diamètre.

En déduire une fonction diametre qui prend en argument un arbre et qui renvoie

(* Caml *) diametre : arbre -> int
{ Pascal } function diametre(t : arbre) : integer ;

Question 16 Soit T un arbre de diamètre D. Montrer que D est la plus grande 
profondeur
d'un arbre obtenu par changement arbitraire de racine et que  D2  est la plus 
petite profondeur
d'un arbre obtenu par changement arbitraire de racine.

Partie III.

Diffusion dans les arbres

On étudie dans cette partie le problème de la diffusion dans les arbres. La 
racine r de l'arbre
T = (r, L) possède un message qu'elle doit transmettre à tous les autres 
noeuds. La diffusion
procède par étapes, toutes de temps unitaire. À une étape donnée, chacun des 
noeuds déjà en
possession du message le transmet à un et un seul de ses fils (sauf si tous ses 
fils l'ont déjà reçu).
Une diffusion D est caractérisée par un ensemble de fonctions : à chaque noeud 
interne v de
l'arbre, avec nv fils, on associe une fonction injective fv qui numérote ses 
fils de 1 à nv dans
l'ordre dans lequel v leur transmet le message.

4

Pour v  N (T ), on note tD (v) le numéro de l'étape à laquelle v reçoit le 
message :

0
si v = r,
tD (v) =
tD (v  ) + fv (v) si v  est le père de v.
Voici un exemple :
·
·
·

3

·
·
·

·
·
·

Un arbre

·

·
·
·

1

·

1
1

·
2

1
·

·
·

0

1

1

·

·

2
·
·

3

2

4

3

2

3

4

3

4

1

Valeurs des fonctions fv

1

Valeurs des numéros
des étapes tD (v)

La durée de la diffusion est son nombre d'étapes, soit t(D) = maxvN (T ) tD 
(v). Une diffusion
est optimale si sa durée est minimale parmi les durées de toutes les diffusions.

Diffusion dans les arbres binomiaux
On considère l'arbre binomial Bk défini dans la partie I. Tout noeud interne v 
a pour fils les
racines r1 , . . . , rnv d'arbres binomiaux B0 , B1 , . . . , Bnv -1 . La 
numérotation naturelle s'obtient en
posant fv (ri ) = i pour chaque noeud v et chaque i, 1  i  nv , tandis que la 
numérotation
renversée s'obtient en posant fv (ri ) = nv - i + 1.
Question 17 Quelle est la durée de la diffusion qui choisit la numérotation 
naturelle pour
chaque noeud ?
Question 18 Même question pour la diffusion qui choisit la numérotation 
renversée pour
chaque noeud.
Question 19 Quelle est la durée d'une diffusion optimale dans Bk ? Justifier 
votre réponse.

Diffusion dans un arbre quelconque
Question 20 Proposer un algorithme pour déterminer une diffusion optimale dans 
un arbre
T quelconque. Quelle est sa complexité en fonction de nbn(T ) ?
Question 21 Écrire une fonction diffusion_optimale qui prend en argument un 
arbre T et
qui calcule la durée d'une diffusion optimale pour T . (On pourra supposer que 
le langage de
programmation contient une fonction qui trie un tableau ou une liste d'entiers.)
(* Caml *) diffusion_optimale : arbre -> int
{ Pascal } function diffusion_optimale(t : arbre) : integer ;
5

Durée de la diffusion optimale
Question 22 Donner une borne supérieure pour la durée d'une diffusion optimale 
dans un
arbre arbitraire à n noeuds, et exhiber pour tout n un arbre pour lequel cette 
borne est atteinte.
Question 23 Donner une borne inférieure pour la durée d'une diffusion optimale 
dans un arbre
arbitraire à n noeuds, et exhiber pour tout n un arbre pour lequel cette borne 
est atteinte.

Partie IV.

Échange total dans les arbres

On étudie dans cette partie le problème de l'échange total dans les arbres. 
Chaque noeud v
de l'arbre possède un message msgv qu'il doit transmettre à tous les autres 
noeuds. L'échange
total procède par étapes, toutes de temps unitaire. Lors d'une étape, certaines 
paires de voisins
s'échangent tous les messages qu'ils ont reçus dans les étapes précédentes ; 
chaque noeud ne peut
communiquer qu'avec un seul voisin lors d'une étape donnée. La durée d'un 
échange total est
son nombre d'étapes, et son trafic est le nombre d'échanges entre voisins ayant 
eu lieu au cours
de l'algorithme. Voici un exemple pour un arbre à 4 noeuds, dont la durée est 3 
et le trafic 5 :
Étape 0

Étape 1
msg2
msg1

msg1 , msg2
msg1 , msg2

msg3

msg3 , msg4
msg3 , msg4

msg4
Étape 2

Étape 3
msg1 , msg2
msg3 , msg4

msg1 , msg2
msg3 , msg4
msg1 , msg2

msg1 , msg2
msg3 , msg4

msg1 , msg2
msg3 , msg4

msg1 , msg2
msg3 , msg4
msg1 , msg2
msg3 , msg4

msg3 , msg4

Échange total dans les arbres binomiaux
On revient dans cette question sur l'arbre binomial Bk d'ordre k  1 introduit 
dans la partie I.
Question 24 Proposer un algorithme d'échange total dans Bk dont la durée est 2k 
- 1.
Question 25 Montrer que tout échange total dans Bk a une durée au moins égale à 
2k - 1.

6

Question 26 Plus généralement, donner une borne inférieure pour la durée de 
tout échange
total dans un arbre T quelconque à n  2 noeuds.

Échange total de trafic minimal
Soit T un arbre à n  2 noeuds. On considère l'échange total suivant, où il y a 
un seul échange
à chaque étape :
1. Tant que l'arbre contient au moins trois noeuds :
(a) On choisit un noeud externe s (arbitrairement s'il y en a plusieurs), qui 
effectue un
échange avec son père ;
(b) On efface le noeud s de l'arbre.
2. Les deux derniers noeuds échangent leur information et possèdent désormais 
les messages
de tous les noeuds de T .
3. On effectue à nouveau tous les échanges de l'étape 1, dans l'ordre inverse, 
pour propager
l'information à tous les noeuds.
Question 27 Montrer que le trafic de l'échange total précédent est égal à 2n - 
3.
Question 28 Écrire une fonction echange_total qui prend en argument un arbre T 
et renvoie
la liste des n - 2 noeuds externes successivement retirés de l'arbre T par 
l'étape 1 de l'algorithme
d'échange total ci-dessus. On garantira une complexité O(nbn(T )).
(* Caml *) echange_total : arbre -> liste
{ Pascal } function echange_total(t : arbre) : liste ;

Question 29 Montrer que le trafic de tout échange total dans un arbre à n  2 
noeuds est au
moins égal à 2n - 3.

7

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP 2011 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par
Vincent Puyhaubert (Professeur en CPGE) et Guillaume Batog (ENS Cachan).

Ce sujet aborde le problème de la transmission d'information dans les arbres,
selon le modèle dit « du téléphone ». On considère ainsi un arbre comme un 
réseau de
communication, dans lequel les noeuds sont les acteurs du réseau et les arêtes 
sont les
canaux par lesquels peuvent transiter les messages. Dans un tel réseau, au 
moins deux
types de protocoles de communication peuvent être intéressants. Dans le premier,
un des acteurs possède un message qu'il souhaite transmettre à tous les autres :
c'est le problème de la diffusion. Dans le second, chaque acteur possède un 
message,
et l'objectif consiste à transmettre l'ensemble des messages à tous les acteurs 
du
réseau : c'est le problème de l'échange total.
Il est souvent plus naturel de considérer des graphes généraux pour modéliser de
tels réseaux de communication. Cependant, en se limitant au cas des arbres, ce 
sujet
étudie déjà un grand nombre de difficultés du domaine. Le sujet est divisé en 
quatre
parties dont les deux premières sont indépendantes.
· La première partie introduit une classe d'arbres particuliers, les arbres 
binomiaux, qui seront utilisés dans la suite pour donner des exemples des 
protocoles
de communication.
· La deuxième partie, majoritairement algorithmique, introduit quelques 
fonctions élémentaires sur les arbres, tels que la profondeur ou le diamètre.
· La troisième partie résout le problème de la diffusion dans les arbres, en 
commençant par la diffusion dans les arbres binomiaux. On cherche ensuite la 
durée
optimale d'un protocole de diffusion. Des bornes inférieures et supérieures sont
données, ainsi que des exemples de classes d'arbres qui atteignent ces bornes.
· La quatrième partie résout le problème d'échange total dans les arbres, en 
commençant à nouveau par l'échange total dans les arbres binomiaux. Dans la 
suite,
le sujet propose de minimiser la durée d'un protocole d'échange total, puis son
trafic (nombre total de messages échangés).
Il s'agit d'un sujet long, comportant à la fois des questions théoriques de 
niveau
avancé et des questions algorithmiques demandant beaucoup de vigilance et de 
clairvoyance. Il est nécessaire de bien maîtriser la partie du programme sur 
les arbres pour
aborder le plus sereinement possible ce sujet. Du point de vue de la 
programmation,
ce sujet permet de réviser les fonctions récursives et doublement récursives.

Indications
Partie I
2 Le nombre de noeuds d'un arbre de la forme (r, L) vaut la somme du nombre de
noeuds des arbres de la liste L à laquelle on ajoute 1 pour le noeud r.
3 Dans l'arbre de la question 1, essayer de repérer deux copies de l'arbre B3 .
4 Utiliser la fonction Caml map, de type ('a -> 'b) -> 'a list -> 'b list, qui
prend en argument une fonction f ainsi qu'une liste [a1 ;... ;an] et renvoie la
liste [f a1 ;... ;f an].
5 Utiliser la construction de la question 3, puis appliquer la fonction de la 
question 4
avec un paramètre n bien choisi.
6 La profondeur d'un arbre de la forme (r, L), non réduit à sa racine, vaut le 
maximum des profondeurs des arbres de la liste L auquel on ajoute 1. Montrer 
ainsi
que Bk possède un unique noeud à profondeur maximale. Pour construire un chemin 
de longueur maximale, utiliser la définition de la question 3 et concaténer
des chemins des deux copies de Bk-1 .
7 En notant uk, le nombre de noeuds à profondeur  dans l'arbre Bk , utiliser la
caractérisation de la question 3 pour exhiber une formule de récurrence reliant
les nombres uk, , uk-1, et uk-1,-1 .
8 Justifier que Cn est un arbre par récurrence sur n.
9 Commencer par montrer que les fils du noeud j dans Cn sont tous les noeuds
d'indice j + 2k pour k vérifiant j 6 2k 6 n - j.
Partie II
11 Modifier légèrement la fonction de la question 10 afin qu'elle renvoie à la 
fois la
profondeur de l'arbre et un noeud qui possède cette profondeur.
12 Pour un noeud s fixé, écrire deux fonctions mutuellement récursives qui 
prennent
en argument un arbre ou une liste d'arbres et recherchent un chemin vers s.
Par défaut, si s ne fait pas partie de l'arbre ou de la liste d'arbres donnés, 
on peut
par exemple renvoyer le chemin vide.
13 On pourra commencer par décrire une opération de rotation d'un arbre, qui
consiste à réaliser un échange de la racine avec un de ses fils. Ensuite, en 
s'aidant
de la fonction chemin pour trouver le noeud auquel on veut appliquer le 
changement de racine, on applique une succession de rotations le long de ce 
chemin.
14 Montrer d'abord que la profondeur de T  est inférieure ou égale à D. Montrer
ensuite qu'il existe un chemin partant de r1 de longueur maximale parmi les
chemins de T .
15 Fusionner les résultats des questions précédentes de la partie II.
16 Pour la première partie de la question, utiliser la question 14. Pour la 
seconde
partie, commencer par montrer que la profondeur de tout pivot T  est supérieure
ou égale à D/2, puis construire un arbre de profondeur D/2 obtenu par 
changement de racine, en considérant le noeud au milieu d'un chemin de longueur
maximale dans T .

Partie III
17 Trouver une relation de récurrence reliant les durées de diffusion dans les 
arbres Bk .
La simplifier en remarquant que la suite de ces durées est croissante.
18 Procéder de la même manière qu'à la question 17 en utilisant la construction 
de
la question 3.
19 Combien de fils possède la racine de Bk ?
20 En supposant que l'arbre T est de la forme (r, (T1 , . . . , T )) et qu'on 
dispose de
diffusions optimales pour les arbres T1 , . . . , T , comment en déduire une 
diffusion
optimale pour T à l'aide d'une approche gloutonne ?
21 Utiliser l'algorithme que vous avez décrit dans la question 20 en ne 
calculant que
la durée de la diffusion et pas la diffusion elle-même.
22 Combien de messages peuvent être transmis dans le pire des cas à chaque 
étape ?
23 Montrer par récurrence sur k, qu'après k étapes, au plus 2k noeuds possèdent 
le
message. Utiliser l'arbre Cn défini dans la question 8 pour fournir un exemple
d'arbre qui atteint la borne inférieure et le prouver en utilisant le résultat 
de la
question 19.
Partie IV
24 Construire par récurrence un algorithme d'échange total dans l'arbre Bk tel
qu'après k étapes, la racine possède les messages de tous les noeuds. Les k 
dernières
étapes pourront utiliser l'algorithme de diffusion étudié dans la question 18.
25 Montrer que pour tout arbre la durée de tout échange total est supérieure ou
égale au diamètre de l'arbre, et conclure en utilisant le résultat de la 
question 6.
26 Montrer que le nombre total de messages transmis double au plus à chaque 
étape.
28 Il s'agit de procéder à un parcours de l'arbre, en commençant par exemple 
par le
noeud externe le plus à droite de l'arbre.
29 Après avoir remarqué que tout algorithme d'échange total contient un échange
entre chaque voisin de l'arbre, montrer par l'absurde qu'il n'existe pas de tel
algorithme avec un trafic inférieur ou égal à 2(n - 2). Pour cela, montrer qu'il
existe deux paires de voisins qui ne s'échangent leurs messages qu'une unique 
fois
et aboutir à une contradiction en considérant un chemin qui lie ces deux paires
de voisins.

I. Arbres binomiaux
1 L'arbre dessiné ci-dessous est un arbre binomial d'ordre 4, dans lequel les 
noeuds
ont été indexés en suivant un parcours postfixe de l'arbre.
15

7

3

1

5

2

11

6

9

4

13

10

14

12

8

0

Le sujet n'exige pas d'expliquer la manière dont les noeuds sont étiquetés,
mais un correcteur aura sans doute une meilleure appréciation de la copie si
le candidat est d'ores et déjà capable de justifier une certaine cohérence dans
son choix.

2 Un arbre binomial d'ordre 0 étant réduit à sa racine, il possède un unique 
noeud
qui est externe. Montrons par récurrence forte que la propriété :
P(k) :

« Bk possède 2k noeuds, dont 2k-1 noeuds externes. »

est vraie pour tout k > 1.
· P(1) : un arbre binomial d'ordre 1 consiste en une racine avec un unique fils,
qui est un noeud externe. Ainsi B1 possède 2 noeuds, dont 1 externe.
· P(k - 1) = P(k) : par définition, un arbre binomial d'ordre k est de la forme
(rk , (Bk-1 , . . . , B1 , B0 )). En utilisant l'hypothèse de récurrence, on 
sait que pour
tout j  {1, . . . , k - 1}, l'arbre Bj possède 2j noeuds dont 2j-1 sont 
externes.
Par ailleurs, on a vu précédemment que B0 possède un unique noeud, qui est
externe. Ainsi, en comptant la racine qui est un noeud interne, Bk possède
k-1
k-1
P j
P j-1
1+
2 = 2k noeuds dont 1 +
2
= 2k-1 noeuds externes.
j=0

j=1

· Conclusion :
Pour tout k > 0, Bk possède 2k noeuds, donc 2k-1 noeuds
externes, sauf pour B0 qui possède 1 noeud externe.