Arbre (Mathématiques)

Arbre (mathématiques)

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

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 une seule géodésique finie : il existe un unique plus court chemin de x à y, un chemin de longueur n de x à y étant une suite de n+1 points z0,...,zn de E vérifiant x=z0, ziRzi+1 pour i<n, zn=y. L'arbre (E,R) est dit fini ou infini selon que R est fini ou non. 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 distingue souvent dans un arbre un sommet particulier appelé racine ; par exemple N, muni de la relation xRy ssi x=Sy ou y=SxS est la fonction successeur, est un arbre infini admettant 0 comme racine naturelle, et cela s'étend à Z. Par contre, pour k>1, les treillis Nk et Zk n'ont pas de structure d'arbre naturelle.

Sommaire

Exemples d'arbres infinis

Arbre de Stern-Brocot

Arbre homogène de degré n

Dessins de Escher

Arbre sur un alphabet

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.

Frontière d'un arbre

Définition, topologie

Le lemme de König

Exemples

Ensemble de Cantor

En théorie des ensembles

Arbre bien fondé

Indice de Lusin-Sierpinski

En informatique

En probabilités et potentiel

En géométrie hyperbolique

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Arbre (math%C3%A9matiques) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre (Mathématiques) de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Arbre (mathématiques) — Pour les articles homonymes, voir Arbre (homonymie). Pour tout ce qui concerne les arbres en théorie des graphes voir ici. 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… …   Wikipédia en Français

  • Arbre (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « arbre », sur le Wiktionnaire (dictionnaire universel) Au sens premier, le mot arbre, désigne en… …   Wikipédia en Français

  • Arbre (probabilité) — Pour les articles homonymes, voir Arbre (homonymie). En théorie des probabilités un arbre aléatoire est un arbre défini en utilisant une loi de probabilité sur un ensemble d arbres (au sens de graphe). Par exemple, un arbre aléatoire à n nœuds… …   Wikipédia en Français

  • Arbre de Galton-Watson — Pour les articles homonymes, voir Arbre (homonymie). Simulation d un arbre de Galton Watson avec une loi de Poisson de paramètre 1 pour loi de rep …   Wikipédia en Français

  • Arbre (graphe) — Pour les articles homonymes, voir Arbre (homonymie). Un arbre avec 4 feuilles et 3 nœuds internes. En théorie des graphes, un arbre est un graphe non orienté …   Wikipédia en Français

  • Arbre enraciné — Pour les articles homonymes, voir Arbre (homonymie). Un arbre binaire En théorie des graphes, un arbre enraciné ou une arborescence est un graphe acy …   Wikipédia en Français

  • Arbre (combinatoire) — Pour les articles homonymes, voir Arbre (homonymie). Un arbre possède des propriété structurelles, par exemple enraciné ou non enraciné, plans ou non plans, labellisé ou non labellisé. En combinatoire, on compte le nombre de tels arbres possédant …   Wikipédia en Français

  • Arbre De Probabilité — Cet article fait partie de la série Mathématiques élémentaires Algèbre Logique Arithmétique Probabilités …   Wikipédia en Français

  • Arbre de probabilite — Arbre de probabilité Cet article fait partie de la série Mathématiques élémentaires Algèbre Logique Arithmétique Probabilités …   Wikipédia en Français

  • Arbre De Décision — Un arbre de décision est un outil d aide à la décision et à l exploration de données. Il permet de modéliser simplement, graphiquement et rapidement un phénomène mesuré plus ou moins complexe. Sa lisibilité, sa rapidité d exécution et le peu d… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”