arbre - graphe -

Imaginez cinq lieux reliés par quatre chemins : A–B, A–C, B–D et B–E. Tous les lieux communiquent, mais aucun trajet ne forme de boucle. Entre deux lieux, il n'existe donc qu'un seul chemin sans détour ni répétition. Ce réseau ramifié est un arbre. Ajouter le chemin C–E créerait une boucle ; retirer A–B couperait le réseau en deux.

En théorie des graphes, un arbre est un graphe non orienté qui satisfait simultanément deux conditions : il est connexe, donc tout sommet peut être rejoint depuis n'importe quel autre ; il est acyclique, donc il ne contient aucun cycle. Dans un graphe non orienté, les liaisons sont appelées des arêtes.

Ces conditions équivalent à une propriété utile : deux sommets distincts d'un arbre sont reliés par un unique chemin simple. Pour un arbre fini comportant n sommets, le nombre d'arêtes vaut n − 1. Cette égalité ne suffit cependant à caractériser un arbre que si l'on ajoute la connexité ou l'absence de cycle.

Un sommet choisi comme origine transforme l'objet en arbre enraciné et permet de parler de parent, d'enfant et de niveau. Ce choix organise la lecture, mais ne change ni les sommets ni les arêtes de l'arbre non orienté sous-jacent. Les arbres de choix ou de probabilités utilisent souvent cette organisation pour énumérer des issues successives.

Un arbre est constitué de sommets, qui représentent les objets, et d'arêtes, qui relient certaines paires de sommets. Un chemin enchaîne des arêtes sans interruption ; dans un arbre, il est unique entre deux sommets. Les sommets reliés par une seule arête sont voisins. Le nombre d'arêtes incidentes à un sommet est son degré, et un sommet de degré 1 est une feuille.

La connexité dépend de l'ensemble des chemins, tandis que l'absence de cycle dépend de la manière dont les arêtes se referment ou non. Les positions, les longueurs et les croisements du dessin ne définissent pas l'arbre : seule compte la liste des sommets et des arêtes. Ces données suffisent à retrouver les degrés, les feuilles et le chemin entre toute paire de sommets.

Considérons cinq lieux A, B, C, D et E. Les quatre chemins directs sont A–B, A–C, B–D et B–E. Il faut décider si le réseau représenté par ces données est un arbre.

1. Depuis A, on atteint B et C ; en passant par B, on atteint aussi D et E. Le graphe est donc connexe.
2. Les degrés de A, B, C, D et E valent respectivement 2, 3, 1, 1 et 1. Leur somme vaut 8, soit deux fois les 4 arêtes. Ce calcul contrôle la cohérence des données, mais ne suffit pas à établir que le graphe est un arbre.
3. Les 5 sommets et les 4 arêtes vérifient 4 = 5 − 1. Comme la connexité a déjà été établie, le graphe est un arbre.
4. Le chemin simple de C à E est C–A–B–E ; aucun second chemin simple ne relie ces deux sommets.

Le contrôle peut être refait en cherchant une boucle : aucune suite d'arêtes ne revient à son sommet de départ sans reprendre une arête. En revanche, l'ajout de C–E fermerait le cycle C–A–B–E–C.

Pour concevoir un réseau minimal entre plusieurs sites, un arbre relie tous les sites sans liaison redondante. Si les liaisons possibles forment déjà un graphe plus riche, on cherche plutôt un arbre couvrant, qui conserve tous les sommets en ne sélectionnant qu'une partie des arêtes.

Pour représenter une hiérarchie, on choisit une racine : les dossiers, catégories ou décisions se lisent alors par niveaux. Un graphe général est préférable lorsqu'un élément peut avoir plusieurs relations indépendantes qui créent des cycles.

En dénombrement et en probabilités, un arbre de choix sépare les étapes successives en branches. On suit chaque chemin depuis la racine pour énumérer une issue ; dans un arbre de probabilités, les branches peuvent en plus porter les probabilités conditionnelles utilisées dans le calcul.

Arbre et graphe connexe. Un graphe connexe peut contenir des cycles, contrairement à un arbre. Le triangle à trois sommets est connexe, mais ses trois arêtes forment un cycle : ce n'est pas un arbre.

Arbre et arbre couvrant. Un arbre est un graphe en lui-même. Un arbre couvrant est un sous-graphe acyclique et connexe qui conserve tous les sommets d'un graphe connexe plus grand. Dans un triangle, supprimer une arête produit un arbre couvrant.

Arbre de graphe et arbre de probabilités. Le premier est défini par la connexité et l'absence de cycle. Le second est une représentation enracinée d'expériences successives, dont les branches peuvent porter des probabilités. Leur forme ramifiée est commune, mais leur rôle ne l'est pas.

Un seul sommet. Le graphe formé d'un sommet et d'aucune arête est connexe et sans cycle : c'est un arbre. La relation n − 1 donne bien 0 arête lorsque n vaut 1.

Le bon nombre d'arêtes ne suffit pas. Un graphe à 4 sommets et 3 arêtes peut réunir un triangle et un sommet isolé. Il vérifie 3 = 4 − 1, mais il contient un cycle et n'est pas connexe. Il faut contrôler au moins l'une de ces deux propriétés en plus de l'égalité.

Le dessin peut tromper. Deux arêtes qui se croisent sur la page ne créent pas automatiquement un sommet. Un croisement ne compte comme sommet que si les données du graphe l'indiquent ; il faut examiner les extrémités déclarées, pas seulement l'apparence du tracé.

Une arête retirée coupe l'arbre. Chaque arête d'un arbre est un pont : sa suppression rend le graphe non connexe. À l'inverse, l'ajout d'une arête entre deux sommets déjà présents crée exactement un cycle, puisque ces sommets étaient déjà reliés par un unique chemin.

La fiche graphe connexe approfondit la condition qui garantit l'existence d'un chemin entre toute paire de sommets.

La fiche arbre couvrant montre comment extraire un arbre qui conserve tous les sommets d'un graphe connexe.