Exercices corrigés de graphes et d'ordonnancement type E3

1. Tableau des successeurs :

2. Matrice d'adjacence (8 arcs, dont la boucle (B, B)) :

3. a. On calcule d'abord la ligne A de M² : ligne A de M, (0 1 1 0 0), fois chaque colonne de M, ce qui revient à additionner les lignes B et C de M : (0 1 1 0 0) + (0 1 0 1 0) = (0 2 1 1 0). Puis (M³)_AE = ligne A de M² × colonne E de M = (0 2 1 1 0) · (0 0 0 1 0) = 1 × 1 = 1. Interprétation : il existe un seul chemin de longueur 3 de A vers E : un visiteur peut aller de l'accueil au paiement en exactement trois clics d'une seule façon, (A, C, D, E) : accueil, fiche produit, panier, paiement.

b. (M³)_AB = 3 : les trois chemins de longueur 3 de A vers B sont (A, B, B, B), (A, B, C, B) et (A, C, B, B).

4. a. (A, B, C, D, E) : les arcs A → B, B → C, C → D, D → E existent et chaque sommet apparaît une fois. (A est la seule page sans prédécesseur, elle doit commencer le chemin ; E est un puits, elle doit le finir.)

b. Un visiteur qui suit ce chemin passe une fois et une seule par chaque page : accueil, catalogue, fiche produit, panier, puis paiement. C'est le parcours d'achat « complet » sans retour en arrière.

5. a. Avec Roy-Warshall : k = A, aucune ligne n'a de 1 en colonne A ; k = B, les lignes A, B, C ont un 1 en colonne B et reçoivent la ligne B, (0 1 1 0 0) : seule la ligne C change, (0 1 0 1 0) ⊕ (0 1 1 0 0) = (0 1 1 1 0) ; k = C, les lignes A, B, C, D ont un 1 en colonne C et reçoivent la ligne C, (0 1 1 1 0) : A et B deviennent (0 1 1 1 0), D devient (0 1 1 1 1) ; k = D, les lignes A, B, C, D ont un 1 en colonne D et reçoivent la ligne D, (0 1 1 1 1) ; k = E, la ligne E est nulle.

b. M̂ a 4 × 4 = 16 coefficients égaux à 1 et M en a 8 : il faut ajouter 8 arcs, à savoir (A, D), (A, E), (B, D), (B, E), (C, C), (C, E), (D, B), (D, D).

c. La colonne A de M̂ ne contient que des 0 : aucune page ne permet de revenir à l'accueil, même indirectement. Un visiteur qui quitte l'accueil ne peut plus y retourner par les liens du site : il faudrait ajouter un lien vers l'accueil (un logo cliquable, par exemple) sur les autres pages.

1. Prédécesseurs : S : — ; A : S, B ; B : S ; C : A ; D : B, C ; E : C, D ; F : D, E.

N₀ = {S}. On raye S : B est libre (A attend encore B), N₁ = {B}. On raye B : N₂ = {A}. Puis N₃ = {C}, N₄ = {D} (D attendait B et C), N₅ = {E}, N₆ = {F}.

2. Le graphe est sans circuit (tous les sommets ont reçu un niveau) et chaque niveau contient un seul sommet : il admet un chemin hamiltonien, qui suit les niveaux, (S, B, A, C, D, E, F). Vérification : S → B, B → A, A → C, C → D, D → E, E → F sont des arcs.

3. Non : dans une arborescence, chaque sommet autre que la racine a un seul prédécesseur ; ici A a deux prédécesseurs (S et B), comme D, E et F.

4. En couches depuis S : A et B à 1 ; C et D à 2 ; E et F à 3. La plus petite longueur est 3, par (S, B, D, F) (le seul chemin de longueur 3).

5. a. Marques dans l'ordre des niveaux :

En remontant : F ← E ← C ← A ← B ← S. La mise à jour arrive en F au plus vite en 10 minutes, par (S, B, A, C, E, F). Ce chemin optimal en valeur a 5 arcs, alors que le plus court en longueur, (S, B, D, F), dure 2 + 7 + 5 = 14 minutes.

b. (S, B, A, C) est un sous-chemin du chemin optimal : il est optimal (principe d'optimalité). La durée minimale de S à C est 6 minutes.

6. On garde les arcs « vient de » : S → B, B → A, A → C, C → D, C → E, E → F. Chaque relais a un seul prédécesseur, S n'en a aucun, et tous sont atteints depuis S : on obtient une arborescence de racine S, l'arborescence des chemins les plus rapides.

1. Niveaux : N₀ = {A} ; N₁ = {B, C} ; N₂ = {D, E, G} ; N₃ = {F} ; N₄ = {H}.

2. Graphe : Début → A (0) ; A → B (4), A → C (4) ; B → D (3), B → G (3) ; C → E (5) ; D → F (6) ; E → F (7) ; F → H (3) ; G → H (2) ; H → Fin (2).

Au plus tôt : t(A) = 0 ; t(B) = t(C) = 4 ; t(D) = 4 + 3 = 7 ; t(G) = 7 ; t(E) = 4 + 5 = 9 ; t(F) = max [ 7 + 6 ; 9 + 7 ] = 16 ; t(H) = max [ 16 + 3 ; 7 + 2 ] = 19 ; t(Fin) = 19 + 2 = 21.

Au plus tard : T(Fin) = 21 ; T(H) = 19 ; T(F) = 19 − 3 = 16 ; T(G) = 19 − 2 = 17 ; T(D) = 16 − 6 = 10 ; T(E) = 16 − 7 = 9 ; T(C) = 9 − 5 = 4 ; T(B) = min [ T(D) ; T(G) ] − 3 = min [ 10 ; 17 ] − 3 = 7 ; T(A) = min [ 7 ; 4 ] − 4 = 0.

3. Durée minimale : 21 jours. Tâches critiques (t = T) : A, C, E, F, H. Chemin critique : Début → A → C → E → F → H → Fin, soit 4 + 5 + 7 + 3 + 2 = 21 jours.

4.

5. Avec 2 jours de retard : 2 ≤ ML(D) = 3, aucune conséquence (l'intégration attend de toute façon l'API jusqu'au jour 16). Avec 4 jours de retard : 4 > MT(D) = 3, le projet est retardé de 1 jour : D finit le jour 17, F commence le jour 17, la mise en ligne finit le jour 22.

6. Charge au plus tôt, période par période :

Du jour 7 au jour 9, il faudrait 6 personnes : la contrainte n'est pas respectée. On décale la documentation G, qui a une marge libre de 10 jours. Elle ne peut pas aller sur la période 9 à 13 (5 + 2 = 7 personnes), mais elle peut se placer du jour 13 au jour 15 (ou du jour 14 au jour 16), pendant que seule l'API est en cours : 3 + 2 = 5 personnes. La charge ne dépasse alors jamais 5 personnes, et G finit avant le jour 19 où commence H : le projet dure toujours 21 jours. (Au-delà du jour 16, G tomberait pendant l'intégration, qui mobilise déjà 4 personnes.)

1. b. Chaque coefficient égal à 1 est un arc ; ceux de la diagonale sont des boucles, qui sont des arcs comme les autres. 7 arcs, dont 2 boucles.
2. a. C'est le théorème du chapitre 3 : (Mᵖ)ᵢⱼ compte les chemins de longueur p de i vers j.
3. c. N₀ = {A}, N₁ = {B}, N₂ = {C} (C attend A et B), N₃ = {D}.
4. b. t(F) = max [ 5 + 2 ; 9 + 3 ] = max [ 7 ; 12 ] = 12 : F attend la fin de E.
5. a. ML = min [ 5 ; 7 ] − 3 − 2 = 0 : le moindre retard décale la première tâche suivante.
6. b. Il existe un chemin de X vers X : X est sur un circuit (qui peut être une boucle, mais pas forcément).
7. a. Il passe par 8 sommets, donc emprunte 7 arcs.
8. b. Le graphe peut avoir des circuits, mais les valeurs ne doivent pas être négatives.