← Retour au sommaire

Interrogation — Ch24 : Graphes et ordonnancement

BTS | Mathématiques | Durée : 40 min | /20

Dernière mise à jour : 21 juin 2026

Nom : _____ Prénom : _____ Date : _____

Exercice 1 — Vocabulaire et degrés (4 pts)

On considère un graphe non orienté \(G\) à 4 sommets \(A, B, C, D\) et 5 arêtes : \(\{A,B\}\), \(\{A,C\}\), \(\{B,C\}\), \(\{B,D\}\), \(\{C,D\}\).

  1. Donner le degré de chacun des 4 sommets. (2 pts)
  2. Vérifier le lemme des poignées de mains \(\sum_v d(v) = 2|E|\). (1 pt)
  3. Le graphe admet-il une chaîne eulérienne ? Justifier à partir des degrés. (1 pt)

Exercice 2 — Matrice d'adjacence (3 pts)

Un graphe orienté à 4 sommets numérotés \(1, 2, 3, 4\) possède les arcs suivants : \(1 \to 2\), \(2 \to 3\), \(3 \to 1\), \(3 \to 4\).

  1. Écrire la matrice d'adjacence \(M\) (de taille \(4 \times 4\)). (2 pts)
  2. Cette matrice est-elle symétrique ? Expliquer pourquoi. (1 pt)

Exercice 3 — Plus court chemin (Dijkstra) (5 pts)

Un transporteur cherche le trajet le plus court du dépôt \(A\) au point de livraison \(E\). Le réseau routier pondéré (poids = distance en km, sens unique de gauche à droite indiqué) est donné par :

ArcA→BA→CC→BC→DB→DD→E
Poids623512
  1. Appliquer l'algorithme de Dijkstra depuis \(A\) : donner les distances minimales successives jusqu'à \(E\). (3,5 pts)
  2. En déduire le chemin le plus court de \(A\) à \(E\) et sa longueur. (1,5 pt)

Exercice 4 — Arbre couvrant minimal (Kruskal) (4 pts)

Pour câbler 4 sites \(A, B, C, D\) au coût minimal, on dispose des liaisons pondérées (coût en k€) :

ArêteA-BB-CC-DA-CB-D
Poids12345
  1. Appliquer l'algorithme de Kruskal : indiquer les arêtes retenues et celles rejetées. (3 pts)
  2. Donner le coût total de l'arbre couvrant minimal. (1 pt)

Exercice 5 — Ordonnancement PERT (4 pts)

Un projet comporte 5 tâches dont les durées (en jours) et antériorités sont :

TâcheABCDE
Durée43524
Antérieures—AAB, CD
  1. Calculer les dates de début au plus tôt de chaque tâche et la durée minimale du projet. (2,5 pts)
  2. Déterminer le chemin critique. (1,5 pt)

Correction

Exercice 1 (4 pts)

a) \(d(A) = 2\) (arêtes vers B, C) ; \(d(B) = 3\) (A, C, D) ; \(d(C) = 3\) (A, B, D) ; \(d(D) = 2\) (B, C). (2 pts)

b) \(\sum_v d(v) = 2 + 3 + 3 + 2 = 10\) et \(2|E| = 2 \times 5 = 10\). Égalité vérifiée. ✓ (1 pt)

c) Il y a exactement deux sommets de degré impair (\(B\) et \(C\)). Le graphe étant connexe, il admet une chaîne eulérienne (de \(B\) à \(C\)). (1 pt)

Exercice 2 (3 pts)

a) \(M_{ij} = 1\) s'il existe un arc \(i \to j\), 0 sinon : (2 pts)

\[M = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}\]

b) La matrice n'est pas symétrique : par exemple \(M_{12} = 1\) (arc \(1\to 2\)) mais \(M_{21} = 0\) (pas d'arc \(2 \to 1\)). Le graphe étant orienté, la matrice d'adjacence est en général non symétrique. (1 pt)

Exercice 3 (5 pts)

a) Dijkstra depuis \(A\) (\(\text{dist}[A]=0\), les autres \(=\infty\)) : (3,5 pts)

  • Choix de \(A\) (0) : voisins B = 6, C = 2.
  • Choix de \(C\) (2, plus petite) : voisin B = \(2+3 = 5 < 6\) → dist[B] = 5 ; voisin D = \(2+5 = 7\) → dist[D] = 7.
  • Choix de \(B\) (5) : voisin D = \(5+1 = 6 < 7\) → dist[D] = 6.
  • Choix de \(D\) (6) : voisin E = \(6+2 = 8\) → dist[E] = 8.
  • Choix de \(E\) (8) : terminé.

b) En remontant les parents : \(E \leftarrow D \leftarrow B \leftarrow C \leftarrow A\), soit le chemin \(A \to C \to B \to D \to E\) de longueur 8 km. (1,5 pt)

Exercice 4 (4 pts)

a) On trie les arêtes par poids croissant et on les ajoute si elles ne créent pas de cycle : (3 pts)

  • A-B : 1 → ajouter (pas de cycle).
  • B-C : 2 → ajouter.
  • C-D : 3 → ajouter (les 4 sommets sont alors reliés).
  • A-C : 4 → créerait le cycle A-B-C-A, rejeter.
  • B-D : 5 → créerait un cycle, rejeter (l'arbre est déjà complet, 3 arêtes pour 4 sommets).

b) ACM = {A-B, B-C, C-D}, coût total \(= 1 + 2 + 3 = \mathbf{6}\) k€. (1 pt)

Exercice 5 (4 pts)

a) Dates de début au plus tôt (propagation vers l'avant, on prend le maximum des prédécesseurs) : (2,5 pts)

  • A : début \(0\), fin \(0 + 4 = 4\).
  • B : début \(4\) (après A), fin \(4 + 3 = 7\).
  • C : début \(4\) (après A), fin \(4 + 5 = 9\).
  • D : début \(\max(7, 9) = 9\) (après B et C), fin \(9 + 2 = 11\).
  • E : début \(11\) (après D), fin \(11 + 4 = 15\).

Durée minimale du projet : 15 jours.

b) Le chemin critique est le plus long en durée : \(\mathbf{A \to C \to D \to E}\) (durée \(4 + 5 + 2 + 4 = 15\)). La tâche B dispose d'une marge (elle pourrait commencer jusqu'au jour 6 au lieu de 4 sans retarder D), elle n'est donc pas critique. (1,5 pt)

Total : 4 + 3 + 5 + 4 + 4 = 20 points.