Graphes et ordonnancement | BTS | Mathématiques
Dernière mise à jour : 15 juin 2026
Un graphe a 6 sommets de degrés 1, 2, 3, 3, 4, 5.
1. Somme des degrés ? (2 pts) 2. Nombre d'arêtes ? (3 pts)
1. \(1+2+3+3+4+5=18\). 2. \(18/2=9\) arêtes.
Arêtes pondérées : \(A\!-\!B=4\), \(A\!-\!C=2\), \(C\!-\!B=1\), \(B\!-\!D=5\), \(C\!-\!D=8\).
Détermine le plus court chemin de \(A\) à \(D\) et sa longueur.
\(A=0\) ; \(C=2\) ; \(B=\min(4,\ 2+1)=3\) ; \(D=\min(3+5,\ 2+8)=8\). Chemin : \(A\to C\to B\to D\), longueur 8.
Tâches : A (4, —), B (3, après A), C (5, après A), D (2, après B), E (3, après C et D).
1. Dates de fin au plus tôt. (4 pts)
2. Durée du projet et chemin critique. (3 pts)
1. A=4 ; B=4+3=7 ; C=4+5=9 ; D=7+2=9 ; E commence après C(9) et D(9) → 9, finit à \(9+3=12\).
2. Durée = 12. Chemins critiques : \(A\to C\to E\) (4+5+3=12) et \(A\to B\to D\to E\) (4+3+2+3=12).