"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
148
On peut représenter chaque flèche par un couple (X,Y) où X est le point de départ
de la flèche et Y son point d'arrivée. On obtient ainsi une liste de couples, qui est une
partie du produit cartésien S
2 : (A;C), (A;E), (B;A), (B;D), (C;B), (C;C), (D;C),
(E;A).
On peut aussi faire un tableau donnant, pour chaque page, les pages qui peuvent
être atteintes par un seul clic. On fait alors le tableau des successeurs (tableau 6.1, à
gauche). Une autre possibilité est de faire le tableau des prédécesseurs (tableau 6.1,
à droite), c'est-à-dire un tableau donnant, pour chaque page, les pages qui ont permis
d'y arriver avec un seul clic.
Tableau 6.1
Page (sommet)
Successeurs
Page (sommet)
Prédécesseurs
A
C, E
A
B, E
B
A,D
B
c
c
B, C
c
A,C,D
D
c
D
B
E
A
E
A
On peut aussi faire un tableau à double entrée en codant 1 s'il existe une possibilité en un seul clic, d'aller d' une page de départ (origine) à une page d'arrivée (extrémité), et en codant 0 s'il n' y a pas possibilité de passage.
Tableau 6.2
Extrémité
A
B
c
D
E
A
0
0
l
0
l
B
l
0
0
l
0
CU
c
OI
c
0
l
l
0
0
·.::::
0
D
0
0
l
0
0
E
l
0
0
0
0
De façon évidente, le tableau 6.2 peut être associé à la matrice carrée d' ordre 5
suivante, appelée matrice d'adjacence (fig. 6.2).
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
148
On peut représenter chaque flèche par un couple (X,Y) où X est le point de départ
de la flèche et Y son point d'arrivée. On obtient ainsi une liste de couples, qui est une
partie du produit cartésien S
2 : (A;C), (A;E), (B;A), (B;D), (C;B), (C;C), (D;C),
(E;A).
On peut aussi faire un tableau donnant, pour chaque page, les pages qui peuvent
être atteintes par un seul clic. On fait alors le tableau des successeurs (tableau 6.1, à
gauche). Une autre possibilité est de faire le tableau des prédécesseurs (tableau 6.1,
à droite), c'est-à-dire un tableau donnant, pour chaque page, les pages qui ont permis
d'y arriver avec un seul clic.
Tableau 6.1
Page (sommet)
Successeurs
Page (sommet)
Prédécesseurs
A
C, E
A
B, E
B
A,D
B
c
c
B, C
c
A,C,D
D
c
D
B
E
A
E
A
On peut aussi faire un tableau à double entrée en codant 1 s'il existe une possibilité en un seul clic, d'aller d' une page de départ (origine) à une page d'arrivée (extrémité), et en codant 0 s'il n' y a pas possibilité de passage.
Tableau 6.2
Extrémité
A
B
c
D
E
A
0
0
l
0
l
B
l
0
0
l
0
CU
c
OI
c
0
l
l
0
0
·.::::
0
D
0
0
l
0
0
E
l
0
0
0
0
De façon évidente, le tableau 6.2 peut être associé à la matrice carrée d' ordre 5
suivante, appelée matrice d'adjacence (fig. 6.2).