Trajets entre lieux remarquables d’Islande : étude à l’aide d’un graphe

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2017 | Académie : Amérique du Nord


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 :

002_matT_1706_02_00C_exo_3

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 M4.

M=(000000011000000100000001011000000110000001101001010101111001100000011100)

M4=(12316814131521035569116312165241123212652086111013149314149231328292983013112114293832154015626929324314342353815141521101220143040342149).

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 :

matT_1706_02_00C_04

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.