En théorie des graphes, un arbre est un graphe acyclique et connexePlus généralement, les graphes non orientés acycliques, qui sont des réunions d'arbres disjoints, s'appellent des forêts.. Sa forme évoque en effet la ramification des branches d'un arbre. Par opposition aux arbres simples, arbres binaires, ou arbres généraux de l'analyse d'algorithme ou de la combinatoire analytiquecf. An Introduction to the Analysis of Algorithms, par Robert Sedgewick et Philippe Flajolet, Ch.6, particulièrement page 329., qui sont des plongements particuliers d'arbres (graphes) dans le plan, on appelle parfois les arbres (graphes) arbres de Cayley, car ils sont comptés par la formule de Cayley.
Une forêt est un graphe dont chacune de ses composantes connexes est un arbre, autrement dit un graphe acyclique.
Définition
Définition intuitive Un graphe représente un ensemble de points, appelés sommets ou nœuds, reliés ou non entre eux par des traits, appelés arêtes.
Il s'agit donc d'un concept très simple et d'un outil de modélisation très général, utile dans de nombreux domaines.
Par exemple une carte routière peut être modélisée par un graphe : les villes sont les sommets et on reliera deux sommets par un trait si et seulement si les villes qu'ils représentent ont une route les connectant directement. Un réseau social est un autre exemple : les utilisateurs sont les sommets et on reliera deux utilisateurs si et seulement s'ils sont chacun ami avec l'autre.
À noter que la disposition des sommets (position dans l'espace) n'a pas d'importance, ni même la forme des arêtes reliant éventuellement ces sommets (ligne droite, courbe etc). La seule chose qui compte est la relation entre les sommets.
Un arbre est un graphe qui vérifie les propriétés suivantes :
Connexité : il est possible d'aller de n'importe quel sommet à n'importe quel autre en "passant" par les arêtes du graphe. Dans le cas de la carte routière, cela revient à dire qu'il est toujours possible d'aller d'une ville à l'autre par la route. Acyclique : une fois parti d'un sommet, il n'existe aucune façon d'y revenir sans repasser par une arête déjà empruntée. Dans le cas de la carte routière, cela revient à dire qu'il est impossible de revenir à la ville de laquelle on est parti sans réemprunter à un moment donné la même portion de route entre deux villes.
Définition formelle Un graphe est un couple tel que
est un ensemble non vide quelconque dont les éléments sont appelés sommets ou nœuds. . Les éléments de sont appelés les arêtes.
Un arbre est un graphe tel que
(Connexité) . (Acyclicité) .
Définition par récurrence pour les arbres finis Dans le cas d'arbres finis, c'est-à-dire quand l'ensemble des sommets est fini, il existe une définition alternative. En effet, il est possible de définir par récurrence l'ensemble des arbres finis dont les sommets appartiennent à un ensemble non vide donné E (fini ou infini) : si s est un élément de E alors ({s},∅) est un arbre ; si est un arbre alors (S ∪ {x}, A ∪ { {x,s} }) est un arbre pour x quelconque dans E n'appartenant pas à S et s appartenant à S ; aucun autre graphe n'est un arbre. Autrement dit, l'ensemble des arbres dont les sommets appartiennent à E est le plus petit ensemble de graphes qui vérifie les deux premières règles ci-dessus.
Vocabulaire et notions associées Il existe plusieurs notions très utiles associées aux arbres dont certaines sont données dans le tableau ci-dessous. Les notions données ici sont en fait toutes valables dans le cadre général de graphes. Dans le tableau on se fixe un arbre (S,A). +NotionDéfinition intuitiveDéfinition formelleArêteUn trait qui relie deux sommets x et y (l'ordre ne comptant pas)Arc (arbres orientés)Une flèche qui relie deux sommets x et y (l'ordre compte)Sommets adjacentsDeux sommets x et y sont adjacents s'ils sont reliés par une arête.Arêtes adjacentesDeux arêtes a1 et a2 sont adjacentes si elles partagent une extrémité en commun.Degré d'un sommet xNombre de sommets adjacents à x.FeuilleSommet x dont le degré vaut 1.Sommet interneSommet x dont le degré est strictement supérieur à 1.Chaîne (élémentaire)Une suite d'arêtes mises "bout à bout" qui ne passe pas deux fois par le même sommet.tel que
où et Chemin (élémentaire) (arbres orientés)Une suite d'arcs mis "bout à bout" qui ne passe pas deux fois par le même sommet.tel que
où et Distance entre deux sommets x et yTaille de la plus courte chaîne reliant x et y.Si x et y sont distincts alors la distance d(x,y) vaut
et sinon la distance vaut 0. thumb|Un arbre fini avec 4 feuilles (les sommets , 3, 5, 7) et 3 sommets internes (les sommets , 4 et 6).
Types d'arbres Il existe plusieurs types d'arbres qui peuvent être des cas particuliers d'arbres ou alors des arbres sur lesquels de la structure a été rajoutée.
Arbre fini Un arbre fini est un arbre tel que l'ensemble de ses sommets est fini. Formellement, un arbre (S,A) est fini si S est de cardinal fini. Dans la suite, |S| est le nombre de sommets et |A| est le nombre d'arêtes.
On peut remarquer les propriétés suivantes :
Un arbre fini est un graphe connexe dont le nombre de sommets excède le nombre d'arêtes d'une unité exactement. Autrement dit le graphe (S,A) est un arbre si et seulement s'il est connexe et |S| = |A|+1.
Un arbre fini est un graphe sans cycles dont le nombre de sommets excède le nombre d'arêtes d'une unité exactement. Autrement dit le graphe (S,A) est un arbre si et seulement s'il est acyclique et |S| = |A|+1. Dans le cas particulier où S est l'ensemble des entiers entre 1 et n alors on dit que l'arbre (S,A) est un arbre de Cayley (avec n sommets).
Arbre localement fini Un arbre localement fini est un arbre tel que le degré de chaque sommet est fini. Formellement, un arbre (S,A) est localement fini si pour tout sommet x de S, deg(x) est fini.
Un arbre fini est toujours localement fini mais la réciproque n'est pas vraie. Le nombre de sommets d'un arbre localement fini est fini ou dénombrable.
Arbre enraciné
Un arbre enraciné est simplement un arbre dont un sommet porte le statut particulier de racine. Formellement, un arbre enraciné est un triplet (S,A,r) où (S,A) est un arbre et r est un élément de S appelé racine.
Cette notion de racine permet de se munir d'un ordre de type ancêtre/descendant entre les sommets de l'arbre. Les arbres enracinés sont utiles pour modéliser la généalogie d'une population. +NotionDéfinition intuitiveDéfinition formelleHauteur d'un sommet xDistance entre x et la racine r.Enfant (ou fils) d'un sommet xSommet adjacent à x dont la hauteur vaut celle de x plus 1.Parent d'un sommet xSommet tel que x est son enfant.Descendant d'un sommet xLa définition donnée ici implique qu'un sommet n'est pas son propre descendant mais certaines définitions incluent ce cas. Cette remarque reste valable pour la notion d'ancêtre.Sommet qui découle d'une lignée parent/enfant partant de x.Ancêtre d'un sommet xSommet tel que x est un descendant.Arête découlant d'un sommet xArête qui relie x à un de ses enfants.
Arbre étiqueté Un arbre étiqueté est un arbre dont les sommets (ou les arêtes) possèdent une étiquette, c'est-à-dire un élément d'un ensemble non vide quelconque (souvent les étiquettes sont des entiers ou des nombres réels).
Un arbre possède toujours un étiquetage de sommets canonique : chaque sommet reçoit lui-même en tant qu’étiquette. Ainsi un arbre de Cayley de n sommets peut être vu comme un arbre étiqueté de manière injective avec les entiers de 1 à n. Avec cet étiquetage canonique, les sommets ont tous des étiquettes différentes. L'avantage du concept d'étiquette est qu'il est possible de donner des étiquettes identiques à plusieurs sommets différents.
Arbre orienté
Un arbre orienté est un arbre où les arêtes sont orientées, c'est-à-dire qu'elles ont une direction (elles partent d'un sommet pour arriver à un autre). Formellement un arbre orienté est un couple tel que . Si on note alors est un arbre. Un arbre enraciné possède deux orientations canoniques :
les arêtes sont orientées du descendant le plus éloigné de la racine vers le descendant le plus proche. Formellement, on prend . les arêtes sont orientées du descendant le plus proche de la racine vers le descendant le plus éloigné. Formellement, on prend .
Un arbre orienté est toujours connexe par définition (on dit aussi faiblement connexe) mais n'est pas forcément fortement connexe. En fait le seul arbre orienté fortement connexe est l'arbre trivial qui ne possède qu'un seul sommet.
Arbre ordonné Un arbre ordonné est un arbre enraciné tel que pour chaque sommet, un ordre total a été spécifié pour l'ensemble des enfants de ce sommet.
Arbre régulier Un arbre régulier de degré est un arbre infini dont chaque sommet est de degré . Le graphe de Cayley d'un groupe libre ou l'arbre de Bruhat-Tits sont des exemples d'arbres réguliers.
Combinatoire des arbres
Formule de Cayley
On peut démontrer qu'il y a n arbres numérotés à n sommets. La découverte de cette formule a été attribuée un temps à Arthur Cayley. Pour cette raison, les arbres comme graphes sont parfois appelés arbres de Cayley. Parmi de nombreuses démonstrations, citons celle qui utilise la bijection de Joyal : pour compter les éléments de l'ensemble des arbres de Cayley à n sommets, Joyal établit une bijection entre et l'ensemble des applications de dans , noté usuellement . On a ainsi
Orientation Si on choisit un sommet r quelconque dans un arbre, il est possible d'enraciner l'arbre en r, c'est-à-dire orienter toutes les arêtes de sorte qu'il existe un chemin de r à tous les autres nœuds. On obtient alors un arbre enraciné.
Arbre comme carte Un arbre est un graphe planaire : un graphe qu'on peut dessiner dans le plan sans que ses arêtes ne se touchent, sauf à leurs extrémités. Un tel dessin est parfois appelé plongement d'un graphe. La plupart des graphes planaires ont plusieurs plongements non homéomorphes, au sens où, pour au moins deux de ces plongements, il n'existe pas d'homéomorphisme du plan entier vers lui-même qui envoie un plongement sur l'autre plongementEn fait, on plonge les graphes planaires dans la sphère, vue comme le plan plus un point à l'infini, et on discute l'existence d'homéomorphismes de la sphère envoyant un plongement sur l'autre plongement. : les classes d'homéomorphismes de ces plongements sont appelés cartes planaires. Les classes d'homéomorphismes des plongements des arbres (graphes) sont aussi appelés arbres (planaires, généraux, de Catalan). Pour le dénombrement, il est commode de les munir d'une racine, à savoir une arête orientée : on parle alors d'arbres planaires enracinés. Ainsi le nombre d'arbres planaires enracinés à n arêtes est le n-ième nombre de Catalan :
Exemple : arbres à 3 arêtes (et 4 sommets) thumb|upright=1.65|Les 5 arbres planaires à 3 arêtes, en haut, et les 16 arbres de Cayley à 3 arêtes, en bas. L'arête racine des arbres planaires va du point rouge au point bleu. Les arbres planaires sont non étiquetés, alors que les arbres de Cayley le sont (les n sommets sont étiquetés de 1 à n). Par exemple, il y a deux arbres non enracinés et non étiquetés à 3 arêtes, celui qui possède un sommet de degré 3 et 3 feuilles (étoile à 3 branches) et celui qui possède 2 sommets de degré 2 et deux feuilles (ligne).
L'étoile peut être étiquetée de 4 manières (en choisissant librement l'étiquette du centre, parmi 4 possibilités, le choix des étiquettes des 3 feuilles conduisant alors toujours au même arbre). La ligne peut être étiquetée de 4!=24 manières, équivalentes 2 par 2 (par exemple 1234 et 4321 sont équivalents), donc de 12 manières en réalité, ce qui donne 12 + 4 = 16 = 4 arbres de Cayley à 3 arêtes.