Arbres et arborescences
157
Définition II Définition III, car si
est quasi fortement connexe, c'est qu'il a une
racine, d'après le théorème ci-dessus. Par ailleurs, étant connexe et ayant
arcs,
c'est un arbre.
Définition III Définition I, car si admet une racine il est quasi fortement connexe,
et s'il est un arbre, il n'a pas de cycle.
Ces trois définitions sont donc équivalentes. Parmi les autres définitions, dont nous ne
démontrerons pas l'équivalence avec les définitions précédentes, citons :
Définition IV : une arborescence est un graphe tel qu'un sommet est relié à tout autre
sommet par un chemin unique issu de (qui est donc une racine).
Définition V : une arborescence est un graphe connexe tel que les demi-degrés
intérieurs de tous les sommets sont égaux à 1 sauf pour un sommet pour lequel le
demi-degré intérieur est nul.
Si l'on tient compte de ces définitions, le dessin d'une arborescence dans le plan est très
classique :
Exemple d'arborescence : est la racine
Ce type de dessin apparaît dans de multiples applications : arbres généalogiques, ordres
hiérarchiques, classifications, théorie des questionnaires, etc.
7.3.3. Ordres définis sur une arborescence
On peut définir sur une arborescence plusieurs ordres et préordres : parmi ceux-ci,
citons:
a) l'ordre associé
Dans un graphe quelconque
, la relation définie sur par
(s'il existe un
chemin entre et
constitue un préordre : en effet, cette relation est réflexive si l'on
admet que est relié à lui-même et elle est évidemment transitive.
Pour une arborescence, cette relation est antisymétrique : elle définit donc un ordre, qui
est d'ailleurs partiel. Pour cet ordre, est minorant de tous les sommets.
a
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 8
x 9
x 10 x 11 x 12