Arbre (théorie des graphes)

En théorie des graphes, un arbre est un graphe acyclique et connexe. 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 analytique, 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. Un ensemble d'arbres est appelé une forêt. 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 toujours possible d'aller d'un sommet à l'autre par un chemin d'arêtes. 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 : il est impossible de partir d'un sommet et d'y revenir sans rebrousser chemin à un moment. 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é) . (Acyclique) . Dans le cas d'arbres finis, c'est-à-dire quand l'ensemble des sommets est fini, il existe une définition alternative.