A comme arbre

Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).

Un arbre (tree) est un graphe connexe acyclique non orienté : il n’est donc pas possible en partant d’un sommet de parcourir des liens pour revenir à ce sommet (voir C comme cycle). Ajouter un lien à un arbre crée nécessairement un cycle. Une forêt (forest) est un graphe acyclique non orienté composé de plusieurs arbres.

Un arbre de n sommets comprend nécessairement n – 1 liens.

L’image ci-dessous montre une forêt composée de deux arbres. Celui de gauche comprend 5 sommets et donc 4 liens ; celui de droite 3 sommets et donc 2 liens.

Exemple de forêt

Les sommets ayant un degré égal à 1 sont appelés des feuilles (leaves). Si un sommet est considéré comme étant à l’origine du graphe, il est appelé racine (root)  et le graphe est considéré comme une arborescence (rooted tree). Dans une arborescence, la profondeur d’un sommet est définie par sa distance à la racine. Par convention, la racine de l’arbre est placée en haut de la figure et les feuilles en bas.

Tous les arbres sont des graphes planaires.

L’une des grandes utilisations des arbres est la recherche dans un graphe connexe de l’arbre recouvrant (spanning tree) c’est-à-dire l’arbre (ou l’un des arbres) permettant d’inclure tous les sommets et une partie des liens du graphe étudié. On peut souhaiter chercher l’arbre recouvrant comprenant un minimum de liens et on parle alors du graphe couvrant minimum (minimum spanning tree). L’arbre couvrant peut également servir pour représenter de manière simplifiée des graphes comprenant plusieurs milliers de sommets et de  liens. Dans la figure ci-dessous, les liens en rouge représentent l’un des arbres couvrants du graphe connexe de gauche. Si on examine uniquement l’arbre couvrant (à droite), on retrouve bien tous les sommets du graphe de départ.

Arbre couvrant d'un graphe connexe

Billets liés : C comme cycle, P comme (graphe) planaire.

Retour au glossaire


Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *