"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
156
6.3.1 Dessin d'un graphe par niveaux
On appelle sommet de niveau 0 tout sommet qui n'a pas de prédécesseur. Si on note
S 0 l'ensemble des sommets de niveau 0, alors on appelle sommet de niveau 1 tout
sommet qui n'a pas de prédécesseur dans S - S 0 (ensemble S privé des éléments de
S 0 ). On définit ensuite les sommets de niveau 2 et ainsi de suite ...
Exemple
Sur l'ensemble 5 = {A;B;C;D;E}, on définit un graphe par sa matrice d'adjacence M.
0 0 1 0 1
1 0 0 1 0
M= 0 0 0 0 0
0 0 0 0 1
0 0 1 0 0
Cherchons les sommets de niveau O.
Tableau 6.3
Sommets
A
B
c
D
E
Prédécesseurs
B
--A,E
B
A,D
Best le seul sommet qui n'a pas de prédécesseur, il est donc le seul sommet de
niveau O.
S 0 = {B}
On va maintenant chercher les sommets de niveau l : ce sont les sommets qui
n'ont pas de prédécesseurs dans 5 - 5 0 = {A;C;D;E}.
Tableau 6.4
Sommets
A
c
D
E
Prédécesseurs
--A,E
--A,D
A et D n'ont pas de prédécesseurs dans 5 - 5 0 , ils sont donc de niveau l .
S 1 = {A,D}
Les sommets de niveau 2 sont ceux qui n'ont pas de prédécesseurs dans
(5 - 5 0 ) - 5 1 = {C,f}.
E n'a plus de prédécesseur alors que Ca le sommet E comme prédécesseur. Donc
E est de niveau 2, et enfin C est de niveau 3. Les niveaux des sommets sont
résumés dans le tableau 6.5.