Numérotation isotone à la main — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 7)

Numérotation isotone à la main

Graphes sans circuit et ordonnancement de projets · niveau 1 (application)

Énoncé

On a renuméroté les tâches du projet à 8 tâches du cours. Le graphe obtenu est $H$ :

$H [0] = (526), H [1] = (47), H [2] = (1347), H [3] = (47),$

$H [4] = (7), H [5] = (63), H [6] = (7), H [7] = () .$

Cette numérotation est-elle isotone ? Pourquoi est-ce gênant pour calculer les dates de début au plus tôt ?
Dérouler à la main l'algorithme de suppression des sources (les successeurs d'un sommet sont parcourus dans l'ordre de sa liste) et donner le tableau $N I$ des numéros isotones.

Non : les arcs $2 \to 1$ et $5 \to 3$ vont d'un numéro plus grand vers un plus petit. En calculant $t (3)$ par numéros croissants, on aurait besoin de $t (5)$ , pas encore calculé.
On calcule les degrés entrants $D E = [0, 1, 1, 2, 3, 1, 2, 5]$ . La seule source est $0$ , numéro $0$ .

Suppression de $0$ : $D E [5]$ , $D E [2]$ tombent à $0$ (numéros $1$ et $2$ , dans l'ordre de la liste), $D E [6] = 1$ .
Suppression de $5$ : $D E [6] = 0$ (numéro $3$ ), $D E [3] = 1$ .
Suppression de $2$ : $D E [1] = 0$ (numéro $4$ ), $D E [3] = 0$ (numéro $5$ ), $D E [4] = 2$ , $D E [7] = 4$ .
Suppression de $6$ : $D E [7] = 3$ . Suppression de $1$ : $D E [4] = 1$ , $D E [7] = 2$ .
Suppression de $3$ : $D E [4] = 0$ (numéro $6$ ), $D E [7] = 1$ . Suppression de $4$ : $D E [7] = 0$ (numéro $7$ ).

Le programme confirme :


NI(H) = [0, 4, 2, 5, 6, 1, 3, 7]


valeurs : 0 5 2 6 1 3 4 7
legende : sommets de H dans l'ordre de suppression, sous leur numéro


nom : NI
valeurs : 0 4 2 5 6 1 3 7
legende : NI[s] : numéro isotone du sommet s de H

On retrouve la numérotation d'origine du projet : le sommet $5$ de $H$ est l'ancienne tâche $1$ , le sommet $6$ l'ancienne tâche $3$ , etc.