Graphes, « plus court chemin »
Ens. de spécialité
34
matT_1706_02_06C
Amérique du Nord • Juin 2017
Exercice 3 • 5 points • ⏱ 45 min
Trajets entre lieux remarquables d'Islande : étude à l'aide d'un graphe
Les thèmes clés
Graphe pondéré • Plus court chemin.
Sarah, une jeune étudiante en géologie, souhaite partir en voyage en Islande avec des amis. Elle a loué une voiture tout-terrain pour pouvoir visiter les lieux remarquables qu'elle a sélectionnés.
Sarah a construit le graphe ci-dessous dont les sommets représentent les lieux à visiter et les arêtes représentent les routes ou pistes :
▶ 1. Dans cette question, chaque réponse sera justifiée.
a) Déterminer l'ordre du graphe. (0,5 point)
b) Déterminer si le graphe est connexe. (0,5 point)
c) Déterminer si le graphe est complet. (0,25 point)
▶ 2. Sarah désire emprunter toutes les routes une et une seule fois. Déterminer, en justifiant, si cela est possible. (1 point)
▶ 3. On appelle M la matrice associée au graphe précédent sachant que les sommets sont placés dans l'ordre alphabétique. On donne ci-après une partie de la matrice M ainsi que la matrice .
.
a) Il manque certains coefficients de la matrice M. Compléter et recopier uniquement la partie manquante de cette matrice. (0,75 point)
b) Donner, en le justifiant, le nombre de chemins de longueur 4 permettant d'aller de B à D. (0,5 point)
▶ 4. Sur le graphe pondéré ci-dessous, on a indiqué sur les arêtes les distances en kilomètre entre les différents lieux :
Déterminer à l'aide de l'algorithme de Dijkstra la distance minimale permettant d'aller du sommet B (Lagon bleu) au sommet D (Chute d'eau de Dettifoss).
Préciser alors le trajet à emprunter. (1,5 point)
Les clés du sujet
▶ 2. Appliquez le théorème d'Euler.
▶ 3. b) Le nombre de trajets de longueur donnée entre deux sommets d'un graphe est l'un des coefficients d'une puissance de la matrice associée au graphe.
Corrigé
▶ 1. a) Déterminer l'ordre d'un graphe
Le graphe comporte 9 sommets, donc le graphe est d'ordre 9.
b) Déterminer si un graphe est connexe
La chaîne D – M – H – R – B – V – J – L – G par exemple permet de relier deux sommets quelconques, donc le graphe est connexe.
c) Déterminer si un graphe est complet
Les sommets H et G par exemple ne sont pas adjacents, ils ne sont pas reliés par une arête, donc le graphe n'est pas complet.
▶ 2. Déterminer s'il existe sur un graphe un trajet empruntant une fois et une seule chaque arête
Le graphe est connexe.
On étudie le degré de chacun des sommets, on résume les résultats dans un tableau :
| Sommet | B | D | G | H | J | L | M | R | V |
| Degré | 2 | 1 | 3 | 2 | 3 | 4 | 5 | 3 | 5 |
Le graphe est connexe et possède 6 sommets (D, G, J, M, R V) de degré impair. D'après le théorème d'Euler, il n'existe pas de chaîne eulérienne, c'est-à-dire de trajet empruntant une fois et une seule chaque route.
▶ 3. a) Compléter la matrice associée à un graphe
notez bien
La matrice associée à un graphe est une matrice carrée qui ne comporte que des 0 et des 1. Le coefficient situé à l'intersection de la ligne i et de la colonne j est égal à 1 si les sommets i et j sont adjacents.
Le bloc 3 × 3 complétant la matrice M donnée (lignes 7 à 9, colonnes 1 à 3) est :
b) Déterminer sur un graphe le nombre de trajets de longueur donnée
Le nombre de chemins de longueur 4 entre B (« sommet 1 ») et D (« sommet 2 ») est le coefficient de la matrice situé à l'intersection de la ligne 1 et de la colonne 2, soit 3.
Donc il existe 3 chemins de longueur 4 de B à D.
▶ 4. Déterminer sur un graphe un trajet de distance minimale
Pour déterminer le trajet le plus court du sommet B (Lagon Bleu) au sommet D (Chute d'eau de Dettifoss), on utilise l'algorithme de Dijkstra, qui peut être résumé par le tableau suivant :
| B | G | H | J | L | M | R | V | D | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| ∞ | ∞ | ∞ | ∞ | ∞ | 50 (B) | 220 B | ∞ | B (0) | |
| 150 R | 272 R | ∞ | ∞ | ∞ | 220 B | ∞ | R (50) | ||
| 272 R | ∞ | 291 G | ∞ | 220 B | ∞ | G 150 | |||
| 272 R | 412 V | 291 G | 670 V | ∞ | V (220) | ||||
| 412 V | 291 G | 567 H | ∞ | H (272) | |||||
| 412 V | 567 H | ∞ | L (291) | ||||||
| 567 H | ∞ | J (412) | |||||||
| 617 M | M (567) |
Donc la distance minimale du sommet B (Lagon bleu) au sommet D (Chute d'eau de Dettifoss) est 617 km, et que le trajet à emprunter est B – R – H – M – D, c'est-à-dire Lagon bleu – Reykjavik – Rocher Hvitserkur – Lac de Mývatn – Chute d'eau de Dettifoss.