Liaisons aériennes entre six villes des États-Unis

Merci !

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


Pondichéry • Avril 2017

Exercice 3 • 5 points • 45 min

Liaisons aériennes entre six villes des États-Unis

Les thèmes clés

Graphe pondéré • Plus court chemin.

 

matT_1704_12_00C_03

Alexis part en voyage dans l’Est des États-Unis. Il souhaite visiter les villes suivantes : Atlanta (A), Boston (B), Chicago (C), Miami (M), New York (N) et Washington (W).

Une compagnie aérienne propose les liaisons suivantes représentées par le graphe ci-contre.

Les nombres présents sur chacune des branches indiquent le tarif, en dollars, du vol en avion.

1. a) Quelles caractéristiques du graphe permettent d’affirmer qu’il existe un trajet qui permette à Alexis d’emprunter chaque liaison aérienne une et une seule fois ? (1 point)

b) Donner un exemple d’un tel trajet. (0,5 point)

2. Alexis veut relier Boston à Miami.

En utilisant un algorithme, déterminer le trajet le moins cher, ainsi que le coût de ce trajet. (1,5 point)

3. a) Donner la matrice d’adjacence P de ce graphe en classant les sommets dans l’ordre alphabétique. (0,5 point)

b) Alexis souhaite aller d’Atlanta à Boston en utilisant au maximum trois liaisons aériennes.

Combien y a-t-il de trajets possibles ? Justifier la démarche, puis décrire chacun de ces trajets. (1,5 point)

Les clés du sujet

1. a) Appliquez le théorème d’Euler.

2. Utilisez l’algorithme de Dijkstra.

3. a) La matrice d’adjacence d’un graphe est une matrice carrée qui ne comporte que des 0 et des 1. Si, comme ici, le graphe n’est pas orienté, la matrice est symétrique.

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 d’adjacence.