158
Recherche opérationnelle
b) ordre transverse
D'après la définition IV des arborescences, le chemin reliant la racine à un sommet
quelconque du graphe est unique. Appelons alors rang du sommet la longueur (nombre
d'arcs) du chemin reliant à .
On peut classer les sommets suivant les rangs. Exemple :
Ce classement définit encore un ordre partiel. Pour compléter l'ordre, on peut penser à
ordonner les sommets de même rang, ce qui définit l'ordre transverse.
Pour un rang donné, cet ordre est donné tout simplement par la représentation que l'on
donne de l'arborescence, en ordonnant les sommets de ce rang de gauche à droite.
Plus précisément, d'après la définition V des arborescences, un sommet quelconque n'a
qu'un précédent. La relation ''avoir même précédent immédiat'' définit une relation
d'équivalence, donc des classes d'équivalence. Alors, l'ordre transverse défini sur
l'ensemble de sommets d'un rang donné obéit aux deux règles :
1) les sommets d'une même classe sont consécutifs
2) si deux sommets de même rang
appartiennent à deux classes d'équivalence
différentes
définies par deux sommets du rang inférieur et , l'ordre entre
est le même que celui entre et .
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 8
x 9
x 10 x 11 x 12
Rang 1
Rang 2
Rang 3
a