"'O
0
c
:J
0
LI)
..--t
0
N
@
.......
..c
O'l
·;::::
>Q.
0
u
Chapitre 6 • Graphes et ordonnancement
170
lftlll a) Écrire la matrice d'adjacence M du graphe de la fig. 6.23.
b) Quels arcs doit-on rajouter pour faire la fermeture transitive du graphe?
c) Calculer la matrice M de la fermeture transitive.
Figure 6.23
Clt;.J Calculer la matrice M de la fermeture transitive du graphe de la fig. 6.24.
Quels arcs doit-on ajouter pour la réaliser?
A
B
c
E
D
Figure 6.24
CllJ Un graphe est défini par le tableau 6.15. Déterminer le niveau de chaque
sommet et représenter le graphe en tenant compte des niveaux.
Tableau 6.1 5
Sommets
A
B
c
D
E
F
G
Successeurs
C, E
--F, G
--B, F
D
D
CIEi Un graphe est défini par le tableau 6.16. Déterminer le niveau de chaque
sommet et représenter le graphe en tenant compte des niveaux.
Tableau 6.16
Sommets
A
B
c
D
E
F
G
H
Successeurs
E, G
--A,H
F
--G
--B, D