"'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
Exercices corrigés
B
Figure 6.30
ldlJ1 Un sommet n ' a pas de prédécesseur et chaque sommet n'a qu'un seul prédécesseur. Ainsi chaque sommet est relié à Epar un chemin unique. Le graphe est donc
une arborescence dont la racine est E.
Tableau 6.31
Sommets
A
B
c D
E
F
G
H
I
J
K
Successeurs
B,L
D,K
----- A,) C,G,I
--F
--Prédécesseurs
E
A
F
B
--J
F
L
F
E
B
S 0 ={E} , S 1 ={A; J}, S 2 ={B; F; L} , S 3 ={C; D; G; H ; I; K}
E
~
A
]~
L
B
F
l
A
~
H
D
K
c
G
l
Figure 6.31
L
H
A
ldllij a) A reçoit la marque O. C, D et E sont de niveau 1, chacun d'eux n ' a qu'un
prédécesseur, donc on leur attribue respectivement les marques 8, 3 et 4.
Deux chemins arrivent sur B, de durées 3 + 4 = 7 et 4 + 2 = 6 donc on attribue la
marque 6 au sommet B. On attribue la marque 7 à F.
Quatre chemins arrivent sur G : (marque de C) + 8 = 12 ; (marque de B) + 4 = 10 ;
(marque de E) + 7 = 11 ; (marque de F) + 5 = 12. La marque de G est donc 10 et c'est
la durée minimale du traj et pour relier A à G.
179