Annale corrigée Exercice Ancien programme

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

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.

Corrigé

1. a) Déterminer s'il existe sur un graphe un trajet ­empruntant une fois et une seule chaque arête

Le graphe est connexe : en effet, la chaîne A – C – B – N – W – M par exemple permet de relier deux sommets quelconques du graphe.

On étudie le degré de chacun des sommets, on résume les résultats dans un tableau :

Sommet

A

B

C

M

N

W

Degré

2

2

4

3

3

4

Le graphe est connexe et possède exactement deux sommets, M et N, de degré impair. D'après le théorème d'Euler, il existe une chaîne eulérienne, c'est-à-dire un trajet empruntant une fois et une seule chaque arête, d'extrémités M et N.

b) Donner un exemple de trajet sur un graphe empruntant une fois et une seule chaque arête

D'après la question précédente, un trajet empruntant une fois et une seule chaque liaison aérienne a nécessairement comme extrémités Miami et New York.

Un exemple de tel trajet est M – C – B – N – W – C – A – W – M – N.

2. Déterminer sur un graphe un trajet de coût minimal

Pour déterminer le trajet le moins cher de Boston à Miami, on utilise l'algorithme de Dijkstra, qui peut être résumé par le tableau suivant :

A

B

C

M

N

W

0

130 (B)

170 (B)

B(0)

230 (C)

280 (C)

170 (B)

250 (C)

C (130)

230 (C)

280 (C)

250 (C)

N (170)

280 (C)

250 (C)

A (230)

280 (C)

W (250)

Le trajet le moins cher de Boston à Miami est donc B – C – M, c'est-à-dire Boston – Chicago – Miami, son coût est 280 $.

3. a) Déterminer la matrice d'adjacence d'un graphe

La matrice d'adjacence du graphe précédent est :

P=(001001001010110101001011010101101110)

b) Déterminer les trajets formés d'un nombre donné d'arêtes

Il n'existe aucune liaison aérienne directe entre Atlanta et Boston.

On calcule P2 et P3 :

P2=(211211120202104132221312103131122214) et P3=(226346207263674939329477463728639786).

En considérant dans chacune de ces deux matrices le coefficient situé à l'intersection de la première ligne (pour Atlanta) et de la deuxième colonne (pour Boston), on voit qu'il existe, d'Atlanta à Boston, un trajet utilisant deux liaisons aériennes (d'après la matrice P2) et deux trajets utilisant trois liaisons aériennes (d'après la matrice P3). Ces trajets sont :

A – C – B (Atlanta – Chicago – Boston),

A – W – C – B (Atlanta – Washington – Chicago – Boston),

A – W – N – B (Atlanta – Washington – New York – Boston).

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