128
Recherche opérationnelle
Cette représentation est dite « en niveaux » (numéroté ici de 0 à VII de droite à gauche) :
chaque sommet
d'un niveau donné est tel que tous les sommets
qui le suivent
immédiatement (existence d'un arc
) se trouvent dans les niveaux de numéro
inférieur et au moins un dans le niveau de numéro immédiatement inférieur.
On renumérote alors les sommets du graphe (de haut en bas et de gauche à droite). On
obtient :
Figure 11
Sur un tel graphe, on n'a pas d'arc
avec
. En conséquence il est exclu que
l'algorithme de Ford conduise à des retours en arrière.
La méthode utilisée pour réécrire le graphe par niveaux est remarquablement simple. Il
suffit de prendre la matrice binaire associée au graphe, c'est-à-dire si l'on considère
l'exemple traité :
Matrice binaire associée au graphe
La colonne immédiatement à droite de la matrice représente les demi-degrés extérieurs
de chaque sommet. Dans la classe de niveau 0, on place les sommets de demi-degré
extérieur nul (ici 10). On barre les lignes et colonnes correspondant à ces sommets (c'està-dire qu'on enlève au graphe le sous-graphe constitué par ces sommets) et on recalcule
les demi-degrés extérieurs sur la nouvelle matrice. Dans la classe de niveau 1, on place
les sommets de demi-degrés extérieurs nuls dans la nouvelle matrice (ici 8), on barre les
lignes et les colonnes correspondantes, on recalcule les demi-degrés extérieurs, etc. On
trouve bien ainsi sur le graphe considéré les 8 classes de la figure 10.
Remarque : l'algorithme de Ford peut être facilement adapté au cas où l'on recherche
dans un graphe sans circuit le - ou les - chemins de valeur maximale (et non plus le
1
2
4
5
6
7
9
10
8
3
Niveaux Sommets 1
2
3
4
5
6
7
8
9
10
7
1
1
1
1
3
3
3
3
3
3
2
0
6
2
1
1
1
3
3
3
2
1
1
0
5
3
1
1
2
2
2
2
1
0
6
4
1
1
2
2
2
2
2
1
0
2
5
1
1
1
0
3
6
1
1
1
3
3
1
0
4
7
1
1
2
2
2
1
0
1
8
1
1
0
2
9
1
1
2
1
0
0
10
0
Demi-degrés ext. Successifs