Arbre (mathématiques)

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 1, les treillis Nk et Zk n'ont pas de structure d'arbre naturelle. 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. On obtient alors un arbre enraciné. Un arbre enraciné permet de définir une relation d'ordre sur l'ensemble de ses sommets. Si xRy, on regarde l'unique chemin injectif reliant la racine à x, si ce chemin passe par y on oriente y→x (y est le prédécesseur de x), sinon x→y. On définit ainsi une orientation sur les arêtes de l'arbre. La fermeture transitive de la relation → définit une relation d'ordre : x < y signifie que x est l'un des sommets du chemin reliant la racine à y. L'ensemble des x tels que x < y est ici fini. Mais on peut étendre la notion d'arbre de la façon suivante. Un ensemble ordonné (E,