"'O
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
6.3 · Niveau des sommets d'un graphe sans circuit
Tableau 6.5
Niveaux
0
2
3
Sommets
B
A,D
E
c
On peut faire le graphe en alignant verticalement les sommets de même niveau
(fig. 6.10).
Niveau 0
Niveau 1
Niveau 2
Niveau 3
c
B
Figure 6.10
6.3.2 Arborescence
Une arborescence est un graphe orienté qui possède un sommet de niveau 0, appelé
racine, à partir duquel on peut atteindre tout autre sommet par un chemin unique.
Exemple
Le graphe de la fig. 6.11 est une arborescence dont la racine est A.
A
B
c
/\ /Î\
D
E
F
G
H
l
/\
I
J
K
Figure 6.11
157