Exercices par capacités · BTS
Dernière mise à jour : 21 juin 2026
On considère le graphe non orienté ci-dessous.
Un graphe orienté à 4 sommets possède les arcs suivants : \(1 \to 2\), \(1 \to 3\), \(2 \to 4\), \(3 \to 4\), \(4 \to 1\). Construire sa matrice d'adjacence \(M\) (les lignes représentent l'origine, les colonnes la destination).
On place un 1 en case \((i,j)\) s'il existe un arc \(i \to j\).
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 0 | 1 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 1 | 0 | 0 | 0 |
La matrice est non symétrique, ce qui est normal pour un graphe orienté.
Un graphe non orienté connexe a tous ses sommets de degré pair. Admet-il un cycle eulérien ? Le problème des 7 ponts de Königsberg (graphe dont les 4 sommets sont de degré impair) admet-il un parcours eulérien ? Justifier à l'aide du critère d'Euler.
Critère : un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair ; il admet une chaîne eulérienne (sans retour au départ) si et seulement si il a exactement deux sommets de degré impair.
Premier graphe : tous les sommets de degré pair → il admet bien un cycle eulérien.
Königsberg : les 4 sommets sont de degré impair (plus de deux sommets impairs), donc il n'existe ni cycle ni chaîne eulérienne. Le parcours est impossible.
Un arbre est un graphe connexe sans cycle. Pour relier 8 sites par un réseau en arbre :
Un livreur part du dépôt A et veut rejoindre le client F. Le réseau (graphe orienté pondéré, poids = distance en km) comporte les arcs suivants :
| Arc | A→B | A→C | B→D | B→E | C→B | C→D | D→F | E→F |
|---|---|---|---|---|---|---|---|---|
| Poids | 4 | 2 | 5 | 1 | 1 | 8 | 2 | 3 |
Déterminer le plus court chemin de A à F et sa longueur par l'algorithme de Dijkstra.
On note dist[x] la distance provisoire la plus courte depuis A.
Plus court chemin : A → C → B → E → F, de longueur \(2+1+1+3 = 7\) km.
Sur un petit réseau, les arcs pondérés sont : A→B : 6, A→C : 1, C→B : 2, C→D : 5, B→D : 1. Déterminer la plus courte distance de A à D.
Plus court chemin : A → C → B → D, de longueur \(1+2+1 = 4\).
Pourquoi l'algorithme de Dijkstra ne peut-il pas être utilisé lorsque certaines arêtes ont des poids négatifs ? Quel algorithme faut-il alors utiliser ?
Dijkstra est un algorithme glouton : une fois un sommet traité (distance minimale), sa distance est considérée comme définitive. Avec des poids négatifs, un chemin passant plus tard par une arête négative pourrait raccourcir une distance déjà figée, ce qui invalide le principe.
Dans ce cas on utilise l'algorithme de Bellman-Ford (complexité \(O(|V|\cdot|E|)\)), qui accepte les poids négatifs et détecte les cycles absorbants négatifs.
On veut câbler un réseau reliant 5 sites. Les coûts (en milliers d'euros) des liaisons possibles sont :
| Arête | A-B | A-C | B-C | B-D | C-D | C-E | D-E |
|---|---|---|---|---|---|---|---|
| Poids | 4 | 2 | 5 | 10 | 3 | 8 | 7 |
Déterminer l'arbre couvrant minimal par l'algorithme de Kruskal et son coût total.
On trie les arêtes par poids croissant et on les ajoute si elles ne créent pas de cycle.
L'arbre compte 4 arêtes pour 5 sommets (c'est complet). ACM = {A-C, C-D, A-B, D-E}.
Coût total : \(2 + 3 + 4 + 7 = 16\) (soit 16 000 €).
Appliquer l'algorithme de Kruskal au graphe à 4 sommets dont les arêtes pondérées sont : A-B : 1, A-C : 3, B-C : 2, B-D : 5, C-D : 4. Donner l'arbre couvrant minimal et son poids.
Tri croissant : A-B(1), B-C(2), A-C(3), C-D(4), B-D(5).
L'arbre compte 3 arêtes pour 4 sommets (complet). ACM = {A-B, B-C, C-D}, poids total \(1+2+4 = 7\).
Dans l'algorithme de Kruskal, combien d'arêtes contient l'arbre couvrant minimal d'un graphe connexe à \(n\) sommets ? Pourquoi rejette-t-on une arête qui crée un cycle ?
L'arbre couvrant minimal est un arbre couvrant : il contient les \(n\) sommets et exactement \(n-1\) arêtes.
Une arête créant un cycle relie deux sommets déjà connectés dans l'arbre en construction : elle est inutile pour assurer la connexité et n'augmenterait que le coût total. On la rejette donc pour conserver une structure d'arbre (sans cycle) de poids minimal.
Un projet comporte 5 tâches enchaînées en séquence simple. Le tableau donne leur durée et leurs antériorités.
| Tâche | A | B | C | D | E |
|---|---|---|---|---|---|
| Durée (j) | 3 | 5 | 2 | 4 | 1 |
| Antérieures | — | A | B | C | D |
Les tâches étant en séquence, chaque tâche commence quand la précédente est terminée.
Durée totale du projet : 15 jours (somme des durées car tout est en série).
Un projet comporte les tâches suivantes. On note T⁺(début) la date de début au plus tôt.
| Tâche | Durée (j) | Antérieures |
|---|---|---|
| A | 4 | — |
| B | 3 | — |
| C | 5 | A |
| D | 2 | A, B |
| E | 4 | C, D |
Calculer les dates de début au plus tôt de C, D et E, puis la durée minimale du projet.
Propagation vers l'avant : la date de début au plus tôt d'une tâche est le maximum des dates de fin au plus tôt de ses antérieures.
Durée minimale du projet : 13 jours.
On reprend le projet de l'exercice 12 (durée totale 13 jours). On donne pour la tâche D : date de début au plus tôt \(T^+ = 4\), durée \(d = 2\). La tâche E (qui succède à D) a une date de début au plus tard de 9. Calculer la marge totale de la tâche D et indiquer si elle est critique.
La marge totale d'une tâche \(ij\) vaut \(MT = T^-_j - T^+_i - d_{ij}\), où \(T^-_j\) est la date au plus tard de la fin de la tâche.
La fin de D doit intervenir au plus tard quand E peut démarrer au plus tard, soit \(T^-_{\text{fin D}} = 9\).
\(MT_D = 9 - 4 - 2 = 3\) jours.
La marge totale est non nulle (\(MT_D = 3\)), donc la tâche D n'est pas critique : on peut la retarder jusqu'à 3 jours sans allonger le projet.
On donne le tableau PERT d'un projet (dates calculées) où MT désigne la marge totale.
| Tâche | Durée | T⁺ début | T⁻ début | MT |
|---|---|---|---|---|
| A | 3 | 0 | 0 | 0 |
| B | 5 | 3 | 3 | 0 |
| C | 3 | 3 | 5 | 2 |
| D | 4 | 8 | 8 | 0 |
| E | 2 | 8 | 10 | 2 |
Expliquer la différence entre la marge totale et la marge libre d'une tâche. Pour une tâche \(ij\) de durée \(d_{ij}=5\), on donne \(T^+_i = 10\), \(T^+_j = 20\) et \(T^-_j = 22\). Calculer ces deux marges.
Marge totale : retard maximal sur la tâche sans retarder la fin du projet.
\(MT = T^-_j - T^+_i - d_{ij} = 22 - 10 - 5 = 7\) jours.
Marge libre : retard maximal sans retarder le début au plus tôt des tâches suivantes.
\(ML = T^+_j - T^+_i - d_{ij} = 20 - 10 - 5 = 5\) jours.
On a toujours \(ML \leq MT\) : la marge libre (5 j) est inférieure ou égale à la marge totale (7 j).