Graphes et ordonnancement | BTS | Mathématiques
Dernière mise à jour : 15 juin 2026
Un graphe a 5 sommets de degrés respectifs 2, 3, 3, 2, 4.
1. Calcule la somme des degrés. 2. En déduire le nombre d'arêtes.
1. \(2+3+3+2+4=14\). 2. Nombre d'arêtes \(=14/2=7\).
Dans un graphe, qu'est-ce qu'un cycle ? Qu'est-ce qu'une chaîne ?
Une chaîne est une suite d'arêtes reliant deux sommets. Un cycle est une chaîne fermée (qui revient à son sommet de départ) sans répéter d'arête.
Graphe pondéré : arêtes \(A\!-\!B=2\), \(A\!-\!C=5\), \(B\!-\!C=1\), \(B\!-\!D=4\), \(C\!-\!D=2\).
Détermine le plus court chemin de \(A\) à \(D\) et sa longueur.
Distances au plus court : \(A=0\), \(B=2\), \(C=\min(5,\ 2+1)=3\), \(D=\min(2+4,\ 3+2)=5\).
Chemin : \(A\to B\to C\to D\), longueur \(\mathbf{5}\).
Tâches : A (durée 3, sans antécédent), B (2, après A), C (4, après A), D (2, après B et C).
1. Calcule les dates de fin au plus tôt de chaque tâche.
2. Donne la durée minimale du projet et le chemin critique.
1. A finit à 3 ; B à \(3+2=5\) ; C à \(3+4=7\) ; D commence après B et C (donc à 7) et finit à \(7+2=9\).
2. Durée minimale = 9. Chemin critique : \(A\to C\to D\).
Pour relier 4 sites par fibre au moindre coût, on cherche un arbre couvrant minimal. Un arbre couvrant d'un graphe à \(n\) sommets possède combien d'arêtes ?
Un arbre couvrant à \(n\) sommets a exactement \(n-1\) arêtes. Ici \(4-1=3\) arêtes (les 3 liaisons de coût total minimal qui connectent tous les sites sans cycle).