Annale corrigée Exercice Ancien programme

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

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.

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 :

010101101

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

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner