Exercices – Graphes et ordonnancement
BTS SIO SISR 2e année – Préparer l'épreuve E3 – R4
Note
Comment travailler. Cherche sur papier (dessins et tableaux), puis compare. Trois niveaux : socle, format épreuve, pour aller plus loin (au-delà du programme de l'épreuve).
Niveau 1 – Socle
Exercice 1 – Représenter un graphe
Un réseau de six services est décrit par les arcs suivants : \(1 \to 2\), \(1 \to 3\), \(2 \to 4\), \(3 \to 4\), \(3 \to 5\), \(4 \to 6\), \(5 \to 6\).
- Dresser le tableau des successeurs et celui des prédécesseurs.
- Écrire la matrice d'adjacence \(M\) (sommets pris dans l'ordre 1 à 6).
Voir la réponse
1.
| Sommet | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Successeurs | 2, 3 | 4 | 4, 5 | 6 | 6 | — |
| Prédécesseurs | — | 1 | 1 | 2, 3 | 3 | 4, 5 |
- \(M = \begin{pmatrix} 0&1&1&0&0&0 \\ 0&0&0&1&0&0 \\ 0&0&0&1&1&0 \\ 0&0&0&0&0&1 \\ 0&0&0&0&0&1 \\ 0&0&0&0&0&0 \end{pmatrix}\), la ligne est le sommet de départ, la colonne le sommet d'arrivée.
Exercice 2 – Vocabulaire
Dans ce graphe (arcs \(1 \to 2\), \(2 \to 3\), \(3 \to 1\), \(3 \to 4\)), citer un chemin de longueur 3 de 1 à 4, un circuit, et dire s'il y a une boucle. Existe-t-il un chemin hamiltonien ?
Voir la réponse
Chemin de longueur 3 de 1 à 4 : \(1 \to 2 \to 3 \to 4\). Circuit : \(1 \to 2 \to 3 \to 1\) (longueur 3). Pas de boucle (aucun arc \((x, x)\)). Chemin hamiltonien : \(1 \to 2 \to 3 \to 4\) passe une fois par chacun des 4 sommets : oui.
Exercice 3 – Nombre de chemins
Pour le graphe de l'exercice 1, on donne \(M^2\) et \(M^3\) (seuls les coefficients non nuls sont indiqués) : \(M^2\) a pour coefficients non nuls \((1,4) = 2\), \((1,5) = 1\), \((2,6) = 1\), \((3,6) = 2\) ; \(M^3\) n'a qu'un coefficient non nul, \((1,6) = 3\).
- Combien y a-t-il de chemins de longueur 3 du sommet 1 au sommet 6 ? Les citer.
- Que signifie \((1,4) = 2\) dans \(M^2\) ?
- Que dire de \(M^4\) ?
Voir la réponse
- 3 chemins : \(1 \to 2 \to 4 \to 6\), \(1 \to 3 \to 4 \to 6\), \(1 \to 3 \to 5 \to 6\).
- Il y a 2 chemins de longueur 2 de 1 à 4 : \(1 \to 2 \to 4\) et \(1 \to 3 \to 4\).
- Le plus long chemin a une longueur 3, donc \(M^4 = 0\) : le graphe n'a pas de circuit.
Exercice 4 – Niveaux
Déterminer les niveaux du graphe de l'exercice 1.
Voir la réponse
Niveau 0 : \(\{1\}\) (aucun prédécesseur). On retire 1 : niveau 1 : \(\{2, 3\}\). On retire 2 et 3 : niveau 2 : \(\{4, 5\}\). Niveau 3 : \(\{6\}\). Tous les sommets sont placés : pas de circuit. Chaque arc va d'un niveau vers un niveau supérieur.
Niveau 2 – Format épreuve
Exercice 5 – Fermeture transitive
Pour le graphe de l'exercice 2, donner la matrice de la fermeture transitive et la décrire par des phrases.
Voir la réponse
Les sommets 1, 2, 3 forment un circuit : chacun atteint les deux autres et lui-même, ainsi que 4. Le sommet 4 n'a aucun successeur.
Les 1 sur la diagonale des lignes 1 à 3 traduisent l'existence d'un circuit passant par ces sommets.
Exercice 6 – Ordonnancement MPM
Une migration de messagerie est découpée en 7 tâches (durées en jours).
| Tâche | Désignation | Durée | Prédécesseurs |
|---|---|---|---|
| A | Cadrage | 2 | — |
| B | Sauvegarde | 3 | A |
| C | Installation du serveur | 4 | A |
| D | Migration des comptes | 5 | B, C |
| E | Formation des utilisateurs | 3 | C |
| F | Tests | 2 | D |
| G | Bascule | 1 | E, F |
- Déterminer les dates au plus tôt, la durée minimale du projet, puis les dates au plus tard.
- Calculer les marges totales. En déduire les tâches critiques et le chemin critique.
- Calculer la marge libre et la marge certaine de B et de E. Interpréter pour E.
Voir la réponse
- Dates au plus tôt \(t\) : A 0 ; B 2 ; C 2 ; D \(\max(2+3,\ 2+4) = 6\) ; E 6 ; F \(6 + 5 = 11\) ; G \(\max(6 + 3,\ 11 + 2) = 13\). Fin : \(13 + 1 = \mathbf{14}\) jours. Dates au plus tard \(T\) (en remontant depuis 14) : G \(14 - 1 = 13\) ; F \(13 - 2 = 11\) ; E \(13 - 3 = 10\) ; D \(11 - 5 = 6\) ; C \(\min(6,\ 10) - 4 = 2\) ; B \(6 - 3 = 3\) ; A \(\min(3,\ 2) - 2 = 0\). 2.
| Tâche | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| \(t\) | 0 | 2 | 2 | 6 | 6 | 11 | 13 |
| \(T\) | 0 | 3 | 2 | 6 | 10 | 11 | 13 |
| \(M_T = T - t\) | 0 | 1 | 0 | 0 | 4 | 0 | 0 |
Tâches critiques (\(M_T = 0\)) : A, C, D, F, G. Chemin critique : A → C → D → F → G (\(2 + 4 + 5 + 2 + 1 = 14\)). 3. B : \(M_L = t(D) - t(B) - d(B) = 6 - 2 - 3 = 1\) ; \(M_C = \max(0,\ 6 - (T(A) + d(A)) - 3) = 6 - 2 - 3 = 1\). E : \(M_L = t(G) - t(E) - d(E) = 13 - 6 - 3 = 4\) ; \(M_C = \max(0,\ 13 - (T(C) + d(C)) - 3) = 13 - 6 - 3 = 4\). La formation (E) peut glisser de 4 jours sans retarder la bascule, même si l'installation (C) se termine au plus tard.
Exercice 7 – Lire et construire un PERT
Quatre tâches : A (3 jours, sans prédécesseur), B (2 jours, après A), C (4 jours, après A), D (1 jour, après B et C).
- Représenter le projet en PERT (étapes numérotées). Justifier l'arc fictif.
- Calculer la durée du projet et le chemin critique.
Voir la réponse
- Étapes : 1 (début), 2 (fin de A), 3 (fin de B), 4 (fin de C), 5 (fin du projet). Arcs : A : \(1 \to 2\) ; B : \(2 \to 3\) ; C : \(2 \to 4\) ; D : \(4 \to 5\) ; arc fictif \(3 \to 4\) de durée 0, car D ne peut commencer qu'après B et C : B et C se terminent en deux étapes différentes, et le fictif impose que l'étape 4 attende aussi la fin de B.
- Dates des étapes : 1 : 0 ; 2 : 3 ; 3 : \(3 + 2 = 5\) ; 4 : \(\max(3 + 4,\ 5 + 0) = 7\) ; 5 : \(7 + 1 = 8\). Durée : 8 jours. Chemin critique : \(A \to C \to D\) (\(3 + 4 + 1 = 8\)). La tâche B a 2 jours de marge.
Exercice 8 – Chemin de valeur minimale (Dijkstra)
Un réseau relie six sites. Valeurs des arcs (en ms) : A→B 4, A→C 2, B→C 1, B→D 5, C→B 1, C→D 8, C→E 10, D→E 2, D→F 6, E→F 3.
- Appliquer la méthode de Dijkstra depuis A.
- Donner le chemin de valeur minimale de A à F et sa valeur.
Voir la réponse
- On fixe un sommet à chaque étape (valeur provisoire entre parenthèses) :
| Étape | Sommet fixé | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 0 | A (0) | 4 | 2 | — | — | — |
| 1 | C (2) | 3 | 10 | 12 | — | |
| 2 | B (3) | 8 | 12 | — | ||
| 3 | D (8) | 10 | 14 | |||
| 4 | E (10) | 13 | ||||
| 5 | F (13) |
- En remontant les prédécesseurs : F ← E ← D ← B ← C ← A. Chemin A → C → B → D → E → F, de valeur \(2 + 1 + 5 + 2 + 3 = \mathbf{13}\) ms.
Niveau 3 – Pour aller plus loin
Note
Hors programme de l'épreuve : algorithme de Warshall et parcours en largeur. Ils sont au programme des cours d'algorithmique de licence.
Exercice 9 – L'algorithme de Warshall
La fermeture transitive peut se calculer sans puissances de matrices.
def warshall(M):
n = len(M)
R = [ligne[:] for ligne in M]
for k in range(n):
for i in range(n):
for j in range(n):
R[i][j] = R[i][j] or (R[i][k] and R[k][j])
return R
- Exécuter
warshallsur la matrice du graphe de l'exercice 2. Que retrouve-t-on ? - Quel est le nombre d'opérations en fonction de \(n\) ? Comparer avec le calcul de \(M^p\) pour \(p = 1, \dots, n\).
- Que signifie la valeur
R[i][k] and R[k][j]?
Voir la réponse
- Sur \(M = \begin{pmatrix} 0&1&0&0 \\ 0&0&1&0 \\ 1&0&0&1 \\ 0&0&0&0 \end{pmatrix}\), on obtient \(\begin{pmatrix} 1&1&1&1 \\ 1&1&1&1 \\ 1&1&1&1 \\ 0&0&0&0 \end{pmatrix}\), la matrice de l'exercice 5.
- Trois boucles imbriquées de \(n\) tours : \(n^3\) opérations. Calculer \(M^2, \dots, M^n\) demande \(n - 1\) produits de \(n^3\) opérations chacun, soit de l'ordre de \(n^4\) : Warshall est plus économe.
- Il existe un chemin de \(i\) à \(j\) passant par le sommet intermédiaire \(k\) : un chemin de \(i\) à \(k\), puis un chemin de \(k\) à \(j\). À l'étape \(k\), on autorise \(0, \dots, k\) comme intermédiaires.
Exercice 10 – Parcours en largeur
from collections import deque
def parcours_largeur(succ, depart):
dist = {depart: 0}
file = deque([depart])
while file:
x = file.popleft()
for y in succ[x]:
if y not in dist:
dist[y] = dist[x] + 1
file.append(y)
return dist
- Exécuter
parcours_largeursur le graphe de l'exercice 1 avecsucc = {1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: []}depuis le sommet 1. - Que représente
dist[y]? Le comparer aux niveaux de l'exercice 4.
Voir la réponse
- Le résultat est
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2, 6: 3}. dist[y]est le nombre minimal d'arcs d'un chemin de 1 à \(y\). Ici ils coïncident avec les niveaux, parce que tous les chemins de 1 vers un sommet ont la même longueur. En général, ce n'est pas le cas : dans un graphe sans circuit, le niveau d'un sommet est la longueur du plus long chemin qui y arrive, la distance en largeur celle du plus court.
Auto-évaluation
- Je passe sans erreur entre dessin, tableaux et matrice d'adjacence.
- Je lis dans \(M^p\) le nombre de chemins de longueur \(p\).
- Je calcule les niveaux d'un graphe sans circuit.
- Je construis le tableau MPM complet (\(t\), \(T\), marges) et le chemin critique.
- Je traduis un projet en PERT avec un arc fictif.
- J'applique la méthode de Dijkstra et je justifie le chemin obtenu.