Arbres et arborescences
159
Par exemple :
On a muni d'un ordre complet chaque ensemble de sommets d'un rang déterminé.
c) Ordre de Tarry
Supposons que nous ayons représenté l'arborescence comme sur les figures précédentes,
c'est-à-dire que :
- les sommets d'un même rang sont sur une même horizontale
- pour un rang donné, les sommets sont rangés suivant l'ordre transverse
précédent.
Imaginons alors un promeneur se déplaçant sur l'arborescence en appliquant les règles
suivantes :
1- il part de la racine
2- il quitte le sommet où il se trouve en prenant l'arc le plus à sa droite et dans le sens de
son orientation; si cette règle ne lui permet plus de progresser, il applique la règle 3.
3- il rebrousse chemin (en parcourant les arcs dans le sens contraire à leur orientation)
jusqu'à ce qu'il atteigne un sommet d'où parte un arc qu'il n'a pas encore emprunté; alors,
il respecte la règle 2.
L'ordre de Tarry est celui dans lequel le promeneur rencontre chaque sommet pour la
première fois.
Ainsi, sur l'arborescence suivante, on a déterminé la marche du promeneur de Tarry
(jusqu'au retour à la racine a) et numéroté les sommets suivant l'ordre trouvé.
1
2
3
1
2
3
4
5
6
7
8
a
1
2
3
4 5
7
8
9
10 11
6