Arbres

I/ Définitions

1) Graphes acycliques

Un graphe n'ayant aucun cycle s'appelle un arbre (définition dûe à Arthur Cayley en 1889).

2) Racine et feuilles

En informatique, on choisit un sommet particulier de l'arbre, à partir duquel on fera les parcours, et qu'on appelle racine :

Il est d'usage de dessiner la racine en haut et l'arbre de haut en bas :

Les sommets B, C, G, H, I, K, L s'appellent les feuilles de l'arbre. Les sommets comme A, D, E, F, J qui ne sont pas des feuilles, sont des nœuds de l'arbre. Le nombre de nœuds s'appelle la taille de l'arbre. La distance (nombre d'arêtes) entre la racine et la feuille qui en est la plus éloignée s'appelle la hauteur de l'arbre. Ci-dessus c'est 4.

3) Parcours

Avec le dessin ci-dessus, le parcours en largeur se fait comme la lecture d'un texte, de gauche à droite et de haut en bas : ABCDEFGHIJKL. Mais le parcours en profondeur n'est pas le même : ABCDEGHFIJKL. Ces algorithmes sont de complexité linéaire par rapport au nombre de nœuds (ou par rapport au nombre de branches).

II/ Dictionnaire

Dans les faits, la distinction entre racine et feuilles oriente l'arbre et on peut ne mettre chaque arête qu'une seule fois dans le dictionnaire :

{  'A': ['B','C','D'],
   'B': [],
   'C': [],
   'D': ['E','F'],
   'E': ['G','H'],
   'F': ['I','J'],
   'G': [],
   'H': [],
   'I': [],
   'J': ['K','L'],
   'K': [],
   'L': [] }

Un arbre est donc un dictionnaire dont les valeurs sont des listes d'adjacence (liste de clés) et tel que chaque clé n'apparaît au maximum que dans une seule liste d'adjacence.

Un seul sommet n'apparaît dans aucune liste d'adjacence, c'est la racine de l'arbre. Un sommet dont la valeur dans le dictionnaire est une liste vide, est une feuille de l'arbre. Si le sommet T est dans la liste d'adjacence de S, on dit que T est un enfant de S, ou que S est le parent de T.

On peut donc dire que les clés du dictionnaire sont les sommets (racine, nœuds, feuilles) de l'arbre et les valeurs du dictionnaire sont pour chaque sommet, la liste de ses enfants. Une feuille est un sommet n'ayant pas d'enfant, la racine est le seul sommet n'ayant pas de parent.

Variante (concours Centrale 2000) avec la représentation de la fonction père :

La racine est le seul sommet qui n'a pas de père (la fonction est dite partielle).

III/ Exemples

1) Labyrinthes

Le chemin qui passe entre les murs d'un labyrinthe est, dans le cas parfait, un arbre. Par exemple l'arbre précédent donne ce labyrinthe :

La méthode classique qu'on prend pour sortir du labyrinthe est un parcours en profondeur (Édouard Lucas, 1880).

2) DOM

Un fichier html est un arbre, dont la structure est désignée par l'abréviation DOM (Document Object Model). La racine de cet arbre s'appelle document et par exemple les li ont pour parent un ul ou un ol.

3) tree

La commande tree de bash affiche le contenu du dossier sous forme d'arborescence :

♟️ tree
.
├── css
│   ├── style1.css
│   └── style2.css
├── img
│   ├── favicon.ico
│   └── fond.png
├── index.html
└── javascript
    ├── script.js
    └── vendor
        └── coffeescript.js

4 directories, 7 files

Comme on le voit, les feuilles sont les fichiers, les nœuds sont les dossiers, et la racine est notée par un simple point. Dans un chemin complet de fichier, le caractère "slash" représente une branche, comme dans ./css/style1.css. Les enfants d'un dossier sont les fichiers (ou dossiers) qu'il contient.

La commande tree n'affiche qu'une partie de l'arborescence de fichiers, celle dont la racine est le dossier courant. Pour avoir toute l'arborescence de fichiers, il faut la lancer depuis le disque dur, appelé root (racine). Le nom de root est souvent utilisé pour désigner le seul utilisateur qui a accès à la racine. C'est la signification de la lettre r dans les droits d'accès des fichiers.

Des commandes bash permettent de modifier l'arbre :

• mkdir pour ajouter un nœud interne
• rmdir pour enlever un nœud interne
• touch pour ajouter une feuille
• rm pour enlever une feuille
• mv ou mount pour déplacer un sous-arbre vers une autre partie de l'arbre
• .. désigne le parent d'un nœud
• ls donne la liste des enfants du nœud

4) Arbre des processus

La commande pstree affiche un autre arbre : celui des processus. Le système d'exploitation ordonnance les processus dans un arbre.

5) Arbre phylogénétique

Le jeu phylo est lié à la notion d' arbre phylogénétique du vivant (Darwin, 1837).

6) Arbres couvrants

Un arbre couvrant d'un graphe est un arbre qui a les mêmes sommets que le graphe. On peut l'obtenir en enlevant au graphe les arêtes responsables de l'apparition de cycles.

Les parcours d'un graphe reviennent en fait à construire des arbres couvrants. Par exemple avec le graphe de Moser :

a) Parcours en largeur

Le parcours en largeur du graphe de Moser construit cet arbre couvrant :

On voit mieux sa structure d'arbre (et le fait que le parcours est parti de A) en l'orientant :

Comme tableau de valeurs de la fonction partielle père :

b) Parcours en profondeur

Dans le cas du graphe de Moser, l'arbre couvrant obtenu par le parcours en profondeur (à partir de A) est unaire :

Un graphe ayant un arbre couvrant en forme de liste (comme le graphe de Moser) est dit hamiltonien. Cette notion, ainsi que celle d'arbre couvrant, ne sont pas au programme.