Arbre (mathématiques)
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
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 (En géométrie, une géodésique désigne le chemin le plus court, ou l'un des chemins s'il en existe plusieurs, entre deux points d'un espace une fois qu'on s'est donné un moyen de mesurer les distances,...) finie : il existe un unique plus court chemin de x à y, un chemin de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en...) n de x à y étant une suite de n+1 points z0,...,zn de E vérifiant x=z0, ziRzi+1 pour izn=y. L'arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres acquièrent une structure rigide composée d'un tronc qui peut...) (E,R) est dit fini ou infini selon que R est fini ou non. Par exemple si E est la réunion (La Réunion est une île française du sud-ouest de l'océan Indien située dans l'archipel des Mascareignes à environ 700 kilomètres...) du bord d'un disque (Le mot disque est employé, aussi bien en géométrie que dans la vie courante, pour désigner une forme ronde et régulière, à l'image d'un palet — discus en latin.) 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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions...) est équivalente à celle de Théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :) 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.

Exemples d'arbres infinis

Arbre de Stern-Brocot

Arbre homogène de degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) n

Dessins de Escher

Arbre sur un alphabet

Soit A un alphabet non nécessairement fini et A* l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être...) des mots (finis) écrits à partir de A (mot vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) ε compris), qui est un monoïde pour la concaténation (Le terme concaténation est issu du latin cum (avec) et catena (chaîne), il désigne l'action de mettre bout à bout deux chaînes.). 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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 (La théorie des ensembles est une branche des mathématiques créée initialement par le mathématicien allemand Georg Cantor à la fin du XIXe siècle.). == Frontière (Une frontière est une ligne imaginaire séparant deux territoires, en particulier deux États souverains. Le rôle que joue une frontière peut fortement varier suivant les...) d'un arbre ==iopipipiiii

Définition, topologie (La topologie est une branche des mathématiques concernant l'étude des déformations spatiales par des transformations continues (sans arrachages ni recollement...)

Le lemme de König

Exemples

Ensemble de Cantor (L'ensemble de Cantor (ou ensemble triadique de Cantor, ou poussière de Cantor) est un sous-ensemble remarquable de la droite réelle construit par le mathématicien allemand Georg Cantor.)

En théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur...) des ensembles

Arbre bien fondé

Indice de Lusin-Sierpinski

En informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par...)

En probabilités et potentiel

En géométrie (La géométrie est la partie des mathématiques qui étudie les figures de l'espace de dimension 3 (géométrie euclidienne) et, depuis le XVIIIe siècle, les figures d'autres types d'espaces (géométrie...) hyperbolique

Page générée en 0.051 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique