"'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 supplémentaires
A
b) Calculer la matrice M de la fermeture transitive. Quels arcs faut-il ajouter au
graphe pour faire sa fermeture transitive ?
@t11 Un graphe est défini par le tableau 6.42. Déterminer le niveau de chaque
sommet et représenter le graphe en tenant compte des niveaux.
Tableau 6.42
Sommets
A
B
c
D
E
F
G
H
Successeurs
C,E,F
--B
A,G
--E
C,H
B,F
CllJ Un graphe est défini par le tableau 6.43. Déterminer le niveau de chaque
sommet et représenter le graphe en tenant compte des niveaux.
Tableau 6.43
Sommets
A
B
c
D
E
F
G
H
I
J
Successeurs
F,H
F
A,B,D
G
C,J
G,I
----- H
A
ld@ll Un graphe est défini par le tableau 6.44. Déterminer le niveau de chaque
sommet et représenter le graphe en tenant compte des niveaux.
Tableau 6.44
Sommets
A
B
c
D
E
F
G
H
Successeurs
C,E,F
--B
A,G
--E
C,H
B,F
@Il Sur le graphe de la fig. 6.36, déterminer le chemin de longueur minimale
reliant A à H, puis le chemin de longueur maximale reliant A à H (voir exercice
corrigé 6. 16).
B
15
20
15
- - - E
Figure 6.36
18
289