Arborescences

On appelle arborescence un arbre avec un sommet distingué, que l'on appelle la racine. On représente généralement une arborescence avec la racine en haut du dessin et les feuilles en bas. Sur l'arborescence ci-contre, la racine est le sommet 4. Les sommets 5, 6, 7 et 9 sont les feuilles. On peut, dans une arborescence, assigner un rang aux sommets. Le rang sera en fait la distance du sommet à la racine. Ainsi, dans l'exemple ci-contre, le sommet 4 (la racine) a rang 0, le sommet 1 a rang 1, les sommets 2 et 10 ont rang 2, les sommets 3, 5 et 8 ont rang 3 et les sommets 6, 7 et 9 ont rang 4. On dira que la hauteur de l'arborescence est le rang maximum (4 dans l'exemple ci-contre).

Une arborescence

Arborescences ordonnées

Une arborescence ordonnée est une arborescence dont les arêtes partant de chaque sommet sont ordonnées. On peut systématiquement étiqueter les sommets d'un tel arbre comme suit: on attribue 0 à la racine r, puis 1, 2, 3, ... aux sommets qui sont adjacents à r. Les étiquettes suivantes sont constituées de l'étiquette du sommet "père", suivie d'un chiffre obtenu comme précédemment. Ainsi, les sommets "fils" attachés au sommet 2 seront numérotés 2.1, 2.2, 2.3,... La figure ci-contre illustre le procédé.
Cet ordre (0, 1, 1.1, 1.2, 2, 2.1, 3, 3.1, 3.1.1, 3.1.2, 3.2, 3.3) est appelé ordre lexicographique, puisqu'il est semblable au classement des mots dans un dictionnaire. Il est identique à l'ordre obtenu en parcourant de haut en bas la branche la plus à gauche de l'arbre, puis la branche immédiatement à droite, et ainsi de suite jusqu'à la branche la plus à droite. On parle aussi de parcours en profondeur de l'arbre, par opposition au parcours en largeur qui serait l'ordre: 0, 1, 2, 3, 1.1, 1.2, 2.1, 3.1, 3.2, 3.3, 3.1.1, 3.1.2.

N'importe quelle expression algébrique comprenant des expressions binaires, telle que l'addition, la soustraction, la multiplication et la division, peut être représentée par une arborescence ordonnée. Par exemple, l'aborescence ci-dessous représente l'expression arithmétique (a - b) / ((c x d) + e):

               

On observe que les variables de l'expression (a, b, c, d et e) sont les feuilles et que les opérations sont les autres sommets. L'arbre doit être ordonné car a-b et b-a conduisent au même arbre, mais pas au même arbre ordonné.
Le mathématicien polonais Lukasiewicz a remarqué qu'en plaçant les symboles des opérations binaires avant les arguments, c'est-à-dire + ab au lieu de a+b ou /cd au lieu de c/d, nous n'avions plus besoin de parenthèses. Il s'agit de la notation polonaise dans sa forme préfixée ou directe (par analogie, en notation polonaise postfixée ou inverse, on place les symboles après les arguments; certaines calculatrices - notamment les HP - utilisent la notation polonaise inverse). L'expression (a - b) / ((c x d) + e) devient ainsi / - a b + x c d e (voir le chemin vert de l'arborescence ci-dessus).

Exercices

Exercice 1

Exercice 2

Étant donnée l'expression algébrique (2x + y)·(5a - b)³,

1. dessinez l'arborescence ordonnée correspondante;
2. trouvez la portée de l'exponentiation (la portée d'un sommet s dans une arborescence est le sous-arbre généré par s et les sommets qui le suivent avec s pour racine);
3. écrire l'expression en notation polonaise directe.

Didier Müller, 13.2.03