Dénombrement d'arbres binaires

par **Patastronch** » 30 Mai 2007, 13:36

Ce n'est pas une olympiade mais ca me semblait la meilleure section pour poster ce petit probleme. (je précise que je n'ai pas la solution)

La question est simple : combien y a t il d'abre binaire de profondeur maximum M possedant 2n+1 noeuds.

Petites precision : 2 arbres identiques par symétrie sur un noeud sont considérés différents.

Je me creuse la tete la dessus depuis quelques jours sans aucun résultat, si quelqu'un a une idée qu'il hésite pas :)

par **aviateurpilot** » 30 Mai 2007, 13:56

Patastronch a écrit:Ce n'est pas une olympiade mais ca me semblait la meilleure section pour poster ce petit probleme. (je précise que je n'ai pas la solution)

La question est simple : combien y a t il d'abre binaire de profondeur maximum M possedant 2n+1 noeuds.

Petites precision : 2 arbres identiques par symétrie sur un noeud sont considérés différents.

Je me creuse la tete la dessus depuis quelques jours sans aucun résultat, si quelqu'un a une idée qu'il hésite pas

dit moi d'abord, c'est quoi abre binaire ?profondeur maximum ? et un noeuds?
je ne sais meme pas de quoi tu parle "lol"

par **Patastronch** » 01 Juin 2007, 11:26

une recherche sur google de ce qu'est un arbre sera une réponse plus précise. Si tu n'as aucune notion de graphe il tefaudra t'ingurgiter toutes les bases de la théorie des graphes

En ce qui concerne la question initiale j'ai trouvé la réponse :

Soit

le nombre d'arbre de profondeur h et possedant n noeuds.

Alors on a :

Pour le raisonnement je vous laisse chercher, mais si vous le désirez vraiment je le mettrais.

par **aviateurpilot** » 01 Juin 2007, 12:14

Patastronch a écrit:une recherche sur google de ce qu'est un arbre sera une réponse plus précise. Si tu n'as aucune notion de graphe il tefaudra t'ingurgiter toutes les bases de la théorie des graphes

je vais voir cette théorie,
tu as un lien ou je peux trouver klk chose sur les graphe?

par **Patastronch** » 07 Juin 2007, 10:25

http://blog.christophelebot.fr/wp-content/uploads/2007/03/theorie_graphes.pdf

Mais en tpant "théorie des graphes" sur google tu trouveras des cours a foison sur le sujet.

par **aviateurpilot** » 07 Juin 2007, 12:19

merci bcp :happy2:

ici par exemple, la profondeur de (5) c'est 2,
la profondeur de (9) est 3.
il y a 9 noeud (1,2,3,4,5,6,7,8,9)
non?

si oui, tu veux dire par (de profondeur maximal M) qu'il exist un neoud dont la profondeur egale a M, et les profondeur des autre noeud

par **Patastronch** » 07 Juin 2007, 15:03

Exactement.

De profondeur maximum M <=> de hauteur M

Sauf que comme il s'agit d'un arbre binaire tous tes noeuds ont 2 fils ou 0. Hors dans ton exemple le noeud 6 n'a qu'un seul fils.
En fait ca dépends, les deux définitions peuvent etre admises, mais j'entendais celle ou chaque noeud a 0 ou 2 fils. (la raison est qu'une suite de sommet de degré 2 peut se contracter en unique sommet de degré 2 la plupart du temps selon le probleme. par exemple tes sommets 3, 6 et 9 aurait pu etre modélisé par un unique sommet.)

par **aviateurpilot** » 07 Juin 2007, 15:07

alors pour M=1 par exemple il se peux qu'on a un noeud relier a 2 noeud.et les autre ne sont pas reliés?

par **Patastronch** » 07 Juin 2007, 15:13

aviateurpilot a écrit:alors pour M=1 par exemple il se peux qu'on a un noeud relier a 2 noeud.et les autre ne sont pas reliés?

Pour M=1, on a un unique arbre connexe binaire : le sous arbre comprenant les noeuds 1, 2 et 3 dans ton exemple.

Ce qui correspond a

par **aviateurpilot** » 08 Juin 2007, 15:22

Patastronch a écrit:Pour M=1, on a un unique arbre connexe binaire : le sous arbre comprenant les noeuds 1, 2 et 3 dans ton exemple.

Ce qui correspond a

mais dans ce cas tu n'a travaille que par 3 noeud , donc il n'entre pas dans le cas de 2n+1 noeud.
saufsi tu veux dire les abres qui ont au plus 2n+1 noeuds non?

Dénombrement d'arbres binaires

Dénombrement d'arbres binaires

Qui est en ligne