Arbre (graphe)

Page d'aide sur l'homonymie Pour les articles homonymes, voir Arbre (homonymie).

En théorie des graphes, un arbre est un graphe non orienté, acyclique et connexe [1]. 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 [2], 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.

Définitions

Un arbre avec 4 feuilles (les sommets nos 1, 3, 5, 7) et 3 nœuds internes (les sommets nos 2, 4 et 6).

On distingue deux types de sommets dans un arbre :

  • Les feuilles dont le degré est 1 ;
  • Les nœuds internes dont le degré est supérieur à 1.

Dans le cas des arbres finis, on peut remarquer que :

  • Un arbre fini est un graphe connexe non orienté dont le nombre de sommets excède le nombre d'arêtes d'une unité exactement ;
  • Un arbre fini est un graphe non orienté sans cycles dont le nombre de sommets excède le nombre d'arêtes d'une unité exactement.

Il est possible de définir inductivement l'ensemble des arbres finis de sommets parmi un ensemble donné E (infini ou non) :

  • si s est un élément de E , ({s},∅) est un arbre ;
  • si (S, A) 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.

Dit autrement, l'ensemble de arbres dont les sommets sont parmi les éléments de E est le plus petit ensemble de graphes qui vérifie les deux premières règles.

Other Languages