Arbre (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Arbre (homonymie).
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Cet article ou cette section concernant les mathématiques doit être recyclé. (décembre 2012)

Une réorganisation et une clarification du contenu est nécessaire. Discutez des points à améliorer en page de discussion.

Page d'aide sur l'homonymie Pour tout ce qui concerne les arbres en théorie des graphes, voir Arbre (graphe).

En mathématiques, un arbre est la donnée d'un ensemble E et d'une relation symétrique R sur E telle que deux points distincts quelconques x et y de E soient reliés par un seul chemin injectif fini, ie n+1 points z0,...,zn de E distincts vérifiant x=z0, ziRzi+1 pour i<n, zn=y.

L'arbre (E, R) est dit fini ou infini selon que E l'est. Par exemple si E est la réunion du bord d'un disque et de son centre c et si xRy est la relation x = c ou y = c, alors (E, R) est un arbre infini ; cependant la plupart des arbres infinis que l'on rencontre sont dénombrables. Pour les arbres finis, notre définition est équivalente à celle de la théorie des graphes dont nous utiliserons la terminologie.

On peut choisir n'importe quel sommet d'un arbre et orienter les arêtes à partir de lui ; ce sommet choisi est alors appelé racine. Si xRy, on regarde l'unique chemin injectif reliant la racine à x, si ce chemin passe par y on oriente yx, sinon xy.

Pour k > 1, les treillis Nk et Zk n'ont pas de structure d'arbre naturelle.

Exemples d'arbres infinis[modifier | modifier le code]

Arbre de Stern-Brocot[modifier | modifier le code]

Représentation (finie) de l'arbre de Stern-Brocot.
Article détaillé : arbre de Stern-Brocot.

L'arbre de Stern-Brocot est une représentation de tous les rationnels strictement positifs, sous forme de fractions irréductibles.

Chaque nœud est de degré 3, excepté les trois nœuds 0/1 = 0, 1/1 = 1 et 1/0 = . Considérons que 1 est la racine de l'arbre. L'arbre est défini par l'itération : deux nœuds et ont pour père  ; où et sont des entiers strictement positifs.

L'arbre de Calkin-Wilf est une alternative pour représenter sous forme d'arbre infini les rationnels strictement positifs, sous forme de fractions irréductibles : le nœud correspondant au rationnel a pour fils gauche et pour fils droit , la racine a pour unique fils . Chaque rationnel est ainsi représenté une seule fois dans l'arbre.

Arbre homogène de degré n[modifier | modifier le code]

Un arbre homogène de degré n est un arbre dont chaque nœud est de degré n, c'est-à-dire qu'il est relié à n autres sommets. Cet arbre est alors infini.

Arbre sur un alphabet[modifier | modifier le code]

Soit A un alphabet non nécessairement fini et A* l'ensemble des mots (finis) écrits à partir de A (mot vide ε compris), qui est un monoïde pour la concaténation. Définissons des relations P (pour prédécesseur) et S (pour successeur) entre mots par xSy, ou yPx, ssi x est obtenu à partir de y en lui ajoutant une lettre à droite ; alors (A*,T), où T est la symétrisée de P ou S, est un arbre. Nous appellerons arbre sur A tout arbre (E,R)E est une partie de A* stable par prise de prédécesseur (propriété voisine de celle d'un ensemble transitif) et où R est évidemment la restriction de T; un tel arbre a une racine naturelle, le mot vide. Cet exemple, lorsque A est égal à N ou NxN, sera développé ci-dessous en théorie des ensembles.

On en trouve cas particulier en probabilités appliquées à la dynamique des populations, plus précisément lors de l'étude des processus de Galton-Watson, sous le nom de notation de Neveu. Les arbres associés aux processus de Galton-Watson sont alors appelés arbres de Galton-Watson.

Frontière d'un arbre[modifier | modifier le code]

Exemples[modifier | modifier le code]

Ensemble de Cantor[modifier | modifier le code]

Article détaillé : Ensemble de Cantor.

L'ensemble de Cantor est un sous-ensemble remarquable de la droite réelle construit de manière itérative à partir du segment [0, 1] en enlevant le tiers central ; puis on réitère l'opération sur les deux segments restants, et ainsi de suite. On peut voir les six premières itérations du procédé sur le schéma suivant :

Cantordamm i sju iterationer.png

On dénote par l'opérateur « enlever le tiers central » :

On peut alors représenter chaque intervalle par les nœuds d'un arbre binaire. L'intervalle [0, 1] est la racine et les deux intervalles et sont les deux fils de l'intervalle [a, b]. L'arbre est infini et l'ensemble de Cantor est alors l'ensemble des feuilles de l'arbre. Ci-dessous une représentation des six générations de cet arbre. Les nœuds (ou ensembles) sont représentés par des lignes horizontales et les branches de l'arbre par des lignes verticales.

Cantordamm i sju iterationer arbre.png

En théorie des ensembles[modifier | modifier le code]

Arbre bien fondé[modifier | modifier le code]

Article détaillé : Relation bien fondée.

On dit que est un arbre bien fondé si la relation de prédécesseur n'admet pas de chaîne décroissante infinie c'est-à-dire il n'existe pas de suite infinie[pas clair].

Plus intuitivement, on peut dire qu'un arbre est bien fondé si on ne peut "boucler" indéfiniment de par , dans la relation de prédécesseur[pas clair].

Exemple : Si et , alors on est en présence d'un arbre qui n'est pas bien fondé. En effet, on peut facilement boucler indéfiniment en appliquant successivement et .

Voir aussi[modifier | modifier le code]

Terme